C #: Implementierung des Siebes von Atkin

Dieser Code:

%Vor%

scheint keine getreue Übersetzung dieses Pseudocodes zu sein:

%Vor%

Ihr Code sieht so aus, als würde er für n * n, n ^ 4, n ^ 8 usw. laufen, d. h., er quadriert jedesmal, anstatt jedesmal n-squared zu addieren. Versuchen Sie Folgendes:

%Vor%     

Die letzte Antwort von Aaron Mugatroyd wie von der übersetzten Python-Quelle für ein Sieve of Atkin (SoA) ist nicht Schade, aber es kann in mehrfacher Hinsicht verbessert werden, da einige wichtige Optimierungen wie folgt fehlen:

1. Seine Antwort verwendet nicht die vollständige modulo 60 Original Atkin und Bernstein Version des Sieve, sondern eine etwas verbesserte Variante des Pseudocodes aus dem Wikipedia-Artikel, also verwendet etwa einen Faktor von 0,36 des numerischen Siebbereichs kombinierte Toggle- / Cull-Operationen; Mein Code unten verwendet den einigermaßen effizienten Nicht-Seitensegment-Pseudocode nach meinen Kommentaren in einer Antwort, die das Sieb von Atkin kommentiert die einen Faktor von etwa 0,26 mal den numerischen Bereich verwendet, um den Arbeitsaufwand auf etwa einen Faktor von etwa zwei Siebtel zu reduzieren.

2. Sein Code reduziert die Puffergröße, indem er nur ungerade Zahlendarstellungen hat, während mein Code weitere Bitpakete packt, um jede Darstellung der durch drei und fünf teilbaren Zahlen sowie der durch zwei teilbaren Zahlen, die durch "Odds-Only" impliziert sind, zu eliminieren "; Dies reduziert den Speicherbedarf um einen weiteren Faktor von fast der Hälfte (auf 8/15) und trägt dazu bei, die CPU-Caches für eine weitere Erhöhung der Geschwindigkeit aufgrund der verringerten durchschnittlichen Speicherzugriffszeit besser zu nutzen.

3. Mein Code zählt die Anzahl der Primzahlen unter Verwendung einer schnellen Nachschlagtabellen- (LUT) Pop-Count-Technik, um fast keine Zeit zum Zählen zu nehmen, verglichen mit der ungefähr 1 Sekunde, wobei er die Bit-für-Bit-Technik verwendet; In diesem Beispielcode wird jedoch selbst diese kleine Zeit aus dem zeitgesteuerten Teil des Codes entfernt.

4. Schließlich optimiert mein Code die Bitmanipulationsoperationen für ein Minimum an Code pro innerer Schleife. Zum Beispiel wird keine kontinuierliche Rechtsverschiebung um Eins verwendet, um den ungeraden Darstellungsindex und tatsächlich überhaupt eine Bitverschiebung zu erzeugen, indem alle inneren Schleifen als konstante Modulo (gleich Bitposition) -Operationen geschrieben werden. Außerdem ist der übersetzte Code von Aaron in Operationen ziemlich ineffizient, da er zum Beispiel beim Primary Square Culling das Quadrat des Primes zum Index hinzufügt und dann nach einem ungeraden Ergebnis sucht, anstatt einfach das Zweifache des Quadrats zu addieren, um die Überprüfung nicht zu erfordern ; dann macht es sogar die Überprüfung überflüssig, indem es die Zahl um eins (durch zwei dividierend) verschiebt, bevor die Auswertoperation in der inneren Schleife ausgeführt wird, genau wie für alle Schleifen. Dieser ineffiziente Code macht keinen großen Unterschied in der Ausführungszeit für große Bereiche, die diese "große Siebpufferarray" -Technik verwenden, da die meiste Zeit pro Operation im RAM-Speicherzugriff verwendet wird (ungefähr 37 CPU-Taktzyklen oder mehr für a Bereich von einer Milliarde), wird aber die Ausführungszeit viel langsamer machen, als es für kleinere Bereiche sein muss, die in die CPU-Caches passen; Mit anderen Worten, es wird eine zu hohe Untergrenze für die Ausführungsgeschwindigkeit pro Operation festgelegt.

Der Code lautet wie folgt:

%Vor%

Dieser Code läuft etwa doppelt so schnell wie Aarons Code (etwa 2,7 Sekunden im 64-Bit- oder 32-Bit-Modus auf einem i7-2700K (3,5 GHz) mit dem Puffer etwa 16,5 Megabyte und etwa 0,258 Milliarden kombinierter Toggle / Primzahl-Quadrat) freie cull-Operationen (die durch Auskommentieren der "++ this.opcnt" -Anweisungen angezeigt werden können) für einen Siebelbereich von einer Milliarde, verglichen mit 5,4 / 6,2 Sekunden (32-Bit / 64-Bit) für seinen Code ohne die Zählung Zeit und fast doppelt so viel Speicherverbrauch mit etwa 0,359 Milliarden kombinierten Toggle / Cull-Operationen für das Sieben von bis zu einer Milliarde.

Obwohl es schneller ist als seine optimalste naive Odds-Only-Implementierung des nicht-gesickerten Sievers von Eratosthenes (SoE), macht das Sieb von Atkin nicht schneller als das Sieb von Eratosthenes als ob man ähnliche Techniken anwendet, wie sie in der obigen SoA-Implementierung für das SoE verwendet werden, und verwendet eine maximale Radfaktorisierung, so wird das SoE etwa die gleiche Geschwindigkeit wie dieses haben.

Analyse: Obwohl die Anzahl der Operationen für den vollständig optimierten SoE in etwa der Anzahl der Operationen für den SoA für einen Siebbereich von einer Milliarde entspricht, ist dies der größte Engpass für diese nicht ausgelagerten Prozesse Implementierungen ist Speicherzugriff, sobald die Siebpuffergröße die CPU - Cachegrößen überschreitet (32 KiloBytes L1 - Cache bei einem Taktzykluszugriff, 256 Kilobyte L2 - Cache bei etwa vier Taktzyklen Zugriffszeit und 8 Megabyte L3 - Cache bei etwa 20 Taktzyklen Zugriffszeit für meine i7), wonach der Speicherzugriff hundert Taktzyklen überschreiten kann.

Jetzt haben beide einen Faktor von etwa acht Verbesserungen der Speicherzugriffsgeschwindigkeiten, wenn man die Algorithmen an die Seitensegmentierung anpasst, so dass man Bereiche absieben kann, die sonst nicht in den verfügbaren Speicher passen würden.Der SoE gewinnt jedoch weiterhin über die SoA, da der Siebbereich aufgrund der Schwierigkeiten bei der Implementierung des "Primes-Quadrat-frei" -Teils des Algorithmus sehr groß wird, aufgrund der großen Schritte bei Culling-Scans, die schnell auf viele hundert Male anwachsen die Größe der Seitenpuffer. Ebenso, und vielleicht noch gravierender, wird es sehr speicher- und / oder rechenintensiv, den neuen Startpunkt für jeden Wert von 'x' in Bezug auf den Wert von 'y' bei der niedrigsten Darstellung jedes Seitenpuffers für ein weiteres recht zu berechnen großer Verlust an Effizienz der ausgelagerten SoA im Vergleich zum SoE, wenn der Bereich wächst.

EDIT_ADD: Das Odds-Only-SoE, wie es von Aaron Murgatroyd verwendet wird, verwendet etwa 1.026 Milliarden Cull-Operationen für eine Siebweite von einer Milliarde, also etwa viermal so viele Operationen wie die SoA und sollte daher laufen viermal langsamer, aber die SoA, wie sie hier implementiert wird, hat eine komplexere innere Schleife und vor allem aufgrund eines viel höheren Anteils der Quoten - nur SoE-Culls haben einen viel kürzeren Schritt in den Culling-Scans als die Fortschritte der SoA die naiven Quoten -nur SoE hat viel bessere durchschnittliche Speicherzugriffszeiten, obwohl der Siebpuffer die CPU-Cachegrößen weit überschreitet (bessere Verwendung der Cache-Assoziativität). Dies erklärt, warum das obige SoA nur etwa doppelt so schnell ist wie das Odds-Only SoE, obwohl es theoretisch nur ein Viertel der Arbeit zu tun scheint.

Wenn man einen ähnlichen Algorithmus verwenden würde, der konstante Modulo-Innenschleifen wie für das obige SoA verwendet und die gleiche 2/3/5 Radfaktorisierung implementiert, würde das SoE die Anzahl der Cull-Operationen auf etwa 0,405 Milliarden Operationen reduzieren, also nur etwa 50% mehr Operationen als die SoA und würde theoretisch nur etwas langsamer als die SoA laufen, aber möglicherweise mit etwa der gleichen Geschwindigkeit laufen, da die Ausreißerschritte im Durchschnitt für diesen "naiven" großen Speicher immer noch etwas kleiner sind als für die SoA Puffer verwenden. Eine Erhöhung der Wheel-Faktorisierung auf das 2/3/5/7 Rad bedeutet, dass die SoE-Cull-Operationen auf etwa 0,314 für einen Cull-Bereich von einer Milliarde reduziert werden und dass diese Version des SoE ungefähr die gleiche Geschwindigkeit für diesen Algorithmus ausführen kann. p>

Eine weitere Verwendung der Scheibenfaktorisierung kann durch Vorabkeulen der Siebanordnung (Kopieren in einem Muster) für die 2/3/5/7/11/13/17/19 Primfaktoren nahezu ohne Kosten in der Ausführungszeit erfolgen um die Gesamtanzahl von Cull-Operationen auf etwa 0,251 Milliarden für eine Siebbandbreite von einer Milliarde zu reduzieren, wird das SoE schneller oder ungefähr genauso schnell laufen wie diese optimierte Version des SoA, selbst für diese großen Speicherpufferversionen mit dem SoE immer noch viel weniger Code Komplexität als die oben genannten.

Es kann somit gesehen werden, dass die Anzahl von Operationen für den SoE von einer naiven oder sogar nur Quoten- oder 2/3/5 Radfaktorisierungsversion stark reduziert werden kann, so dass die Anzahl von Operationen ungefähr gleich ist wie für die SoA, während gleichzeitig die Zeit pro Operation aufgrund weniger komplexer innerer Schleifen und eines effizienteren Speicherzugriffs tatsächlich geringer sein kann. END_EDIT_ADD

EDIT_ADD2: Ich füge hier den Code für ein SoE mit einer ähnlichen konstanten Modulo / Bit-Positionstechnik für die innersten Schleifen wie für die SoA oben gemäß dem Pseudocode hinzu weiter unten die Antwort wie oben verlinkt . Der Code ist ein wenig weniger komplex als das obige SoA, obwohl eine hohe Radfaktorisierung und Vorauswahl angewendet wird, so dass die Gesamtanzahl von Ausleseoperationen tatsächlich geringer ist als die kombinierten Toggle / Cull-Operationen für die SoA bis zu einem Siebebereich von etwa zwei Milliarden. Der Code lautet wie folgt:

EDIT_FINAL Korrigierter Code unten und Kommentare dazu END_EDIT_FINAL

%Vor%

Dieser Code läuft tatsächlich ein paar Prozent schneller als das obige SoA, da es etwas weniger Operationen gibt, und der Haupt-Engpass für diese große Array-Größe für einen Bereich von einer Milliarde ist Speicherzugriffszeit von etwa 40 bis über 100 CPU-Taktzyklen abhängig von CPU- und Speicherspezifikationen; Dies bedeutet, dass Code-Optimierungen (abgesehen von der Reduzierung der Gesamtzahl der Operationen) unwirksam sind, da die meiste Zeit damit verbracht wird, auf den Speicherzugriff zu warten. Auf jeden Fall ist die Verwendung eines riesigen Speicherpuffers nicht der effizienteste Weg, um große Bereiche zu sieben, mit einer bis zu achtfachen Verbesserung für den SoE unter Verwendung der Seitensegmentierung mit der gleichen maximalen Radfaktorisierung (die auch den Weg ebnet) Mehrfachverarbeitung).

Bei der Implementierung der Seitensegmentierung und Mehrfachverarbeitung ist der SoA für Bereiche weit über vier Milliarden im Vergleich zum SoE wirklich defizitär, da jegliche Gewinne aufgrund der reduzierten asymptotischen Komplexität des SoA schnell durch Seitenverarbeitungsaufwand aufgefressen werden Faktoren, die sich auf die freie Verarbeitung des Primzahlquadrats beziehen und die viel größere Anzahl von Seitenstartadressen berechnen; alternativ überwindet man dies durch Speichern von Markern im RAM-Speicher zu enormen Kosten beim Speicherverbrauch und weiteren Ineffizienzen beim Zugriff auf diese Markerstrukturen. END_EDIT_ADD2

Kurz gesagt, das SoA ist nicht wirklich ein praktisches Sieb im Vergleich zu dem vollradfaktorisierten SoE, da gerade der Gewinn an asymptotischer Komplexität beginnt, die Leistung an das vollständig optimierte SoE heranzuführen, und beginnt an Effizienz zu verlieren aufgrund der Details der praktischen Implementierung hinsichtlich der relativen Speicherzugriffszeit und der Seitensegmentierungskomplexität sowie allgemein komplexer und schwieriger zu schreiben. Meiner Meinung nach ist es eher ein interessantes intellektuelles Konzept und geistige Übung als ein praktisches Sieb im Vergleich zum SoE.

Eines Tages werde ich diese Techniken an ein multi-threaded-seitiges Sieb von Eratosthenes anpassen, um ungefähr so ​​schnell in C # zu sein wie Atkin und Bernsteins "primegen" Implementierung der SoA in 'C' und es aus dem Wasser blasen wird für große Bereiche über etwa vier Milliarden sogar single-threaded, mit einer zusätzlichen Steigerung der Geschwindigkeit von bis zu etwa vier, wenn Multi-Threading auf meinem i7 (acht Kerne einschließlich Hyper Threading).

    

Hier ist eine weitere Implementierung. Es verwendet BitArray, um Speicher zu sparen. Die Parallel.For muss. NET Framework 4.

%Vor%     

Hier ist eine schnellere Implementierung des Sieve von Atkin, ich habe den Algorithmus aus diesem Python-Skript hier gestohlen (ich nehme keine Anerkennung für den Algorithmus):

Ссылка

%Vor%

Es ist in der Geschwindigkeit zu meiner am besten optimierten Version des Sievers von Eratosthenes, aber es ist immer noch langsamer um etwa 20%, es kann hier gefunden werden:

Ссылка

    

Heres meins, es verwendet eine Klasse namens CompartmentalisedParallel, die es Ihnen ermöglicht, parallele for-Schleifen auszuführen, aber die Anzahl der Threads zu steuern, so dass die Indizes gruppiert werden. Aufgrund der Threading-Probleme müssen Sie entweder das BitArray bei jeder Änderung sperren oder ein separates BitArray für jeden Thread erstellen und diese dann am Ende XOR-verknüpft werden. Die erste Option war ziemlich langsam, da die Anzahl der Sperren die zweite war Option schien schneller für mich!

%Vor%

Und die CompartmentalisedParallel-Klasse:

%Vor%

Primes Basisklasse:

%Vor%

Verwenden Sie es wie folgt:

%Vor%

Ich fand jedoch, dass die Eratosthenes in allen Fällen schneller waren, sogar mit einer Vierkern-CPU, die im Multithread-Modus für Atkin läuft:

%Vor%

Wenn Sie die Atkin schneller laufen lassen, lassen Sie es mich wissen!

    

Hier ist eine Verbesserung des Siets von Eratosthenes mit benutzerdefinierten FixBitArrays und unsicheren Code für Geschwindigkeitsergebnisse, das ist etwa 225% schneller als mein vorheriger Eratosthenes Algorithmus, und die Klasse ist Standalone (das ist kein Multithread - Eratosthenes ist nicht kompatibel mit Multi Threading), Auf einem AMD Phenom II X4 965 Prozessor kann ich Primes auf 1.000.000.000 limit in 9.261 ms berechnen:

%Vor%

Primzahlen gefunden in 1.000.000.000: 50.847.534 in 9.261 ms