Frage Warum ist dieser C ++ - Code schneller als meine handgeschriebene Assembly zum Testen der Collatz-Vermutung?


Ich habe diese zwei Lösungen für geschrieben Projekt Euler Q14, in Assembly und in C ++. Sie sind die gleiche identische Brute-Force-Ansatz zum Testen der Collatz-Vermutung. Die Montagelösung wurde zusammengebaut

nasm -felf64 p14.asm && gcc p14.o -o p14

Das C ++ wurde mit kompiliert

g++ p14.cpp -o p14

Versammlung, p14.asm

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++, p14.cpp

#include <iostream>

using namespace std;

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n*3 + 1;

        ++count;
    }

    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }

    cout << maxi << endl;
}

Ich kenne die Compiler-Optimierungen, um die Geschwindigkeit und alles zu verbessern, aber ich sehe nicht viele Möglichkeiten, meine Assembly-Lösung weiter zu optimieren (programmatisch nicht mathematisch gesprochen).

Der C ++ - Code hat jeden Ausdruck und jede Division für jeden geraden Term, wobei die Assemblierung nur eine Division pro geradem Term ist.

Aber die Assembly dauert durchschnittlich 1 Sekunde länger als die C ++ Lösung. Warum ist das? Ich frage hauptsächlich nach Neugier.

Ausführungszeiten

Mein System: 64 Bit Linux auf 1,4 GHz Intel Celeron 2955U (Haswell Mikroarchitektur).


737
2017-11-01 06:12


Ursprung


Antworten:


Wenn Sie glauben, dass ein 64-Bit-DIV-Befehl eine gute Möglichkeit ist, ihn durch zwei zu teilen, ist es kein Wunder, dass der asm-Ausgang des Compilers Ihren handgeschriebenen Code sogar mit -O0 (Kompilieren Sie schnell, keine zusätzliche Optimierung, und speichern / neu laden in den Speicher nach / vor jeder C-Anweisung, damit ein Debugger Variablen ändern kann).

Sehen Agner Fogs Optimierungsanleitung um zu lernen, wie man effizient asm schreibt. Er hat auch Anweisungstabellen und einen Microarch-Leitfaden für spezifische Details für bestimmte CPUs. Siehe auch die  Tag-Wiki für mehr Perf-Links.

Siehe auch diese allgemeinere Frage zum Überschlagen des Compilers mit handgeschriebenem asm: Ist die Inline-Assemblersprache langsamer als nativer C ++ - Code?. TL: DR: Ja, wenn du es falsch machst (wie diese Frage).

Normalerweise ist es gut, wenn der Compiler sein Ding macht, besonders wenn Sie es tun Versuchen Sie, C ++ zu schreiben, das effizient kompilieren kann. Siehe auch ist Assembly schneller als kompilierte Sprachen?. Eine der Antworten verweist auf diese sauberen Folien zeigen, wie verschiedene C-Compiler einige wirklich einfache Funktionen mit coolen Tricks optimieren.


even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

Auf Intel Haswell, div r64 ist 36 UPS, mit einem Latenz von 32-96 Zyklenund einen Durchsatz von einem pro 21-74 Zyklen. (Plus die 2 UPs, um RBX und Null RDX einzurichten, aber Out-of-Order-Ausführung kann diese früh ausführen). High-Uop-Count-Anweisungen wie DIV sind mikroskodiert, was auch Front-End-Engpässe verursachen kann. In diesem Fall ist die Latenz der wichtigste Faktor, da sie Teil einer loop-getragenen Abhängigkeitskette ist.

shr rax, 1 Hat die gleiche unsigned Division: Es ist 1 Uop, mit 1c Latenzund kann 2 pro Taktzyklus laufen.

Zum Vergleich, 32-Bit-Division ist schneller, aber immer noch schrecklich gegenüber Verschiebungen. idiv r32 ist 9 Ups, 22-29c Latenz und ein pro 8-11c Durchsatz auf Haswell.


Wie Sie sehen können, wenn Sie gcc's betrachten -O0 Asm-Ausgabe (Godbolt Compiler Explorer), es verwendet nur Verschiebebefehle. klingeln -O0 kompiliert naiv wie Sie dachten, sogar mit 64-Bit-IDIV zweimal. (Bei der Optimierung verwenden Compiler beide Ausgaben von IDIV, wenn die Quelle Division und Modulus mit denselben Operanden durchführt, wenn sie IDIV überhaupt verwenden)

GCC hat keinen völlig naiven Modus; Es wird immer durch GIMPLE transformiert, was bedeutet, dass einige "Optimierungen" nicht deaktiviert werden können. Dies beinhaltet die Erkennung von Division-by-Konstante und die Verwendung von Shifts (Potenz von 2) oder ein Fixpunkt-multiplikatives Inverse (keine Potenz von 2) um IDIV zu vermeiden (siehe div_by_13 in der obigen godbolt Verbindung).

gcc -Os (für die Größe optimieren) tut benutze IDIV für Nicht-Power-of-2 Division, leider sogar in Fällen, wo der multiplikative inverse Code nur geringfügig größer, aber viel schneller ist.


Den Compiler unterstützen

(Zusammenfassung für diesen Fall: verwenden uint64_t n)

Zunächst einmal ist es nur interessant, die optimierte Compilerausgabe zu betrachten. (-O3). -O0 Geschwindigkeit ist im Grunde bedeutungslos.

Schau auf deinen Asm-Output (auf Godbolt, oder siehe Wie "Rauschen" aus GCC / Clang Montage-Ausgang zu entfernen?). Wenn der Compiler keinen optimalen Code erstellt: Das Schreiben Ihrer C / C ++ - Quelle in einer Weise, die den Compiler zu besserem Code führt, ist normalerweise der beste Ansatz. Sie müssen asm wissen und wissen, was effizient ist, aber Sie wenden dieses Wissen indirekt an. Compiler sind auch eine gute Quelle von Ideen: manchmal wird clang etwas Cooles tun, und Sie können gcc in die gleiche Sache bringen: sehen Sie diese Antwort und was ich mit der nicht abgerollten Schleife in @ Veedrac's Code unten gemacht habe.)

Dieser Ansatz ist portabel und in 20 Jahren kann ein zukünftiger Compiler ihn zu dem zusammenstellen, was auf zukünftiger Hardware (x86 oder nicht) effizient ist, möglicherweise unter Verwendung einer neuen ISA-Erweiterung oder einer automatischen Vektorisierung. Handschriftliche x86-64 Asm von vor 15 Jahren wären normalerweise nicht optimal auf Skylake abgestimmt. z.B. compare & branch macro-fusion existierte damals nicht. Was jetzt für eine handgefertigte Hülle für eine Mikroarchitektur optimal ist, ist möglicherweise nicht optimal für andere aktuelle und zukünftige CPUs.  Kommentare zu @ Johnfounds Antwort diskutieren die großen Unterschiede zwischen AMD Bulldozer und Intel Haswell, die einen großen Einfluss auf diesen Code haben. Aber in der Theorie, g++ -O3 -march=bdver3 und g++ -O3 -march=skylake wird das Richtige tun. (Oder -march=native.) Oder -mtune=... einfach tunen, ohne Anweisungen zu verwenden, die andere CPUs möglicherweise nicht unterstützen.

Mein Gefühl ist, dass das Führen des Compilers zu asm, das für eine gegenwärtige CPU gut ist, die Ihnen interessiert, kein Problem für zukünftige Compiler sein sollte. Sie sind hoffentlich besser als aktuelle Compiler bei der Suche nach Möglichkeiten, Code zu transformieren, und können einen Weg finden, der für zukünftige CPUs funktioniert. Nichtsdestoweniger wird zukünftiges x86 wahrscheinlich bei allem, was auf dem aktuellen x86 gut ist, nicht schrecklich sein, und der zukünftige Compiler wird jegliche asm-spezifischen Fallstricke vermeiden, während etwas wie die Datenbewegung aus Ihrer C-Quelle implementiert wird, wenn es nichts Besseres sieht.

Handgeschriebenes asm ist eine black-box für das Optimierungsprogramm, so dass die konstante Propagierung nicht funktioniert, wenn Inlining eine Eingabe zu einer Kompilierzeitkonstante macht. Andere Optimierungen sind ebenfalls betroffen. Lesen https://gcc.gnu.org/wiki/DontUseInlineAsm bevor Sie asm benutzen. (Und vermeiden Sie MSVC-Stil Inline-Asm: Eingänge / Ausgänge müssen durch den Speicher gehen was zusätzlichen Aufwand verursacht.)

In diesem Fall: Ihre n hat einen signierten Typ und gcc verwendet die SAR / SHR / ADD-Sequenz, die die korrekte Rundung ergibt. (IDIV und arithmetische Verschiebung "round" unterschiedlich für negative Eingänge, siehe SAR Insn set ref manuelle Eingabe). (IDK, wenn gcc versucht hat und es versäumt hat, dies zu beweisen n kann nicht negativ oder was sein. Signed-overflow ist undefiniertes Verhalten, also hätte es möglich sein sollen.)

Du hättest verwenden sollen uint64_t n, so kann es nur SHR. Und so ist es zu Systemen übertragbar, wo long ist nur 32-Bit (z. B. x86-64 Windows).


BTW, gcc's optimiert asm output sieht ziemlich gut aus (using unsigned long n): Die innere Schleife, in die es einläuft main() macht dies:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

Die innere Schleife ist zweiglos und der kritische Pfad der Schleifen-getragenen Abhängigkeitskette ist:

  • 3-Komponenten-LEA (3 Zyklen)
  • cmov (2 Zyklen auf Haswell, 1c auf Broadwell oder später).

Insgesamt: 5 Zyklen pro Iteration, Latenzengpass. Out-of-Order-Ausführung erledigt alles andere parallel dazu (theoretisch: Ich habe nicht mit perf-Zählern getestet, um zu sehen, ob es wirklich bei 5c / iter läuft).

Der FLAGS-Eingang von cmov (produziert von TEST) ist schneller zu produzieren als der RAX-Eingang (von LEA-> MOV), also ist es nicht auf dem kritischen Pfad.

In ähnlicher Weise ist der MOV-> SHR, der den CMV-RDI-Eingang erzeugt, vom kritischen Pfad entfernt, da er auch schneller als der LEA ist. MOV auf IvyBridge und später hat keine Latenz (behandelt bei Register-Umbenennen Zeit). (Es dauert immer noch ein Uop, und ein Slot in der Pipeline, so ist es nicht frei, nur keine Latenz). Der zusätzliche MOV in der LEA dep-Kette ist Teil des Engpasses bei anderen CPUs.

Das cmp / jne ist auch nicht Teil des kritischen Pfades: Es wird nicht durch die Schleife übertragen, da Steuerabhängigkeiten mit Verzweigungsvorhersage + spekulative Ausführung behandelt werden, im Gegensatz zu Datenabhängigkeiten auf dem kritischen Pfad.


Den Compiler schlagen

GCC hat hier einen ziemlich guten Job gemacht. Es könnte ein Code-Byte speichern, indem Sie verwenden inc edx Anstatt von add edx, 1, weil sich niemand für P4 und seine falschen Abhängigkeiten für Befehle zum Ändern partieller Flags interessiert.

Es könnte auch alle MOV-Anweisungen speichern, und der TEST: SHR legt CF fest = das ausgeschobene Bit, also können wir es verwenden cmovc Anstatt von test / cmovz.

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

Siehe @ johnfounds Antwort für einen weiteren cleveren Trick: Entferne den CMP, indem du das Flag-Ergebnis von SHR verzweigst und für CMOV verwendest: Null, wenn n 1 (oder 0) ist, um damit zu beginnen. (Lustige Tatsache: SHR mit count! = 1 auf Nehalem oder früher verursacht einen Stall, wenn Sie die Flag-Ergebnisse lesen. So haben sie es einfach gemacht. Die Shift-by-1-Spezialcodierung ist jedoch in Ordnung.

Das Vermeiden von MOV hilft nicht mit der Latenz von Haswell (Kann der MOV von x86 wirklich "frei" sein? Warum kann ich das überhaupt nicht reproduzieren?). Es hilft bedeutend auf CPUs wie Intel Pre-IvB und AMD Bulldozer-Familie, wo MOV nicht Null-Latenz ist. Die vergeudeten MOV-Anweisungen des Compilers wirken sich auf den kritischen Pfad aus. BD's Komplex-LEA und CMOV haben beide eine niedrigere Latenz (2c bzw. 1c), also ist es ein größerer Teil der Latenz. Außerdem werden Durchsatzengpässe zu einem Problem, da es nur zwei ganzzahlige ALU-Pipes gibt. Siehe @ johnfounds Antwort, wo er Timing-Ergebnisse von einer AMD-CPU hat.

Selbst bei Haswell kann diese Version ein wenig helfen, indem sie gelegentliche Verzögerungen vermeidet, bei denen ein nicht-kritischer Uop einen Ausführungsport von einem auf dem kritischen Pfad stiehlt und die Ausführung um einen Zyklus verzögert. (Dies wird als Ressourcenkonflikt bezeichnet). Es speichert auch ein Register, das beim Ausführen von mehreren helfen kann n Werte parallel in einer verschachtelten Schleife (siehe unten).

Die Latenzzeit hängt vom Adressierungsmodus ab, auf Intel SnB-Familien-CPUs. 3c für 3 Komponenten ([base+idx+const], die zwei separate Adds benötigt), aber nur 1c mit 2 oder weniger Komponenten (ein Add). Einige CPUs (wie Core2) machen sogar eine 3-Komponenten-LEA in einem einzigen Zyklus, die SnB-Familie jedoch nicht. Schlechter, Die Intel SnB-Familie standardisiert Latenzen, so dass es keine 2c-Ups gibtsonst wäre 3-Komponenten-LEA nur 2c wie Bulldozer. (3-Komponenten-LEA ist auch bei AMD langsamer, nur nicht so viel).

Damit lea rcx, [rax + rax*2] / inc rcx ist nur 2c Latenz, schneller als lea rcx, [rax + rax*2 + 1], auf Intel SnB-Familien-CPUs wie Haswell. Break-even bei BD und schlechter bei Core2. Es kostet einen zusätzlichen UOP, was sich normalerweise nicht lohnt, um 1c Latenz zu sparen, aber Latenz ist der größte Engpass hier und Haswell hat eine ausreichend breite Pipeline, um den zusätzlichen Durchsatz zu bewältigen.

Weder gcc, icc oder clang (auf godbolt) verwendeten SHRs CF-Ausgabe, immer mit einem AND oder TEST. Dumme Compiler. Sie sind großartige Teile komplexer Maschinen, aber ein kluger Mensch kann sie oft bei kleinen Problemen schlagen. (Tausend bis Millionen Mal länger, um darüber nachzudenken, natürlich! Compiler verwenden keine erschöpfenden Algorithmen, um nach allen möglichen Arten zu suchen, Dinge zu tun, denn das würde zu lange dauern, wenn viel Inline-Code optimiert wird sie tun es am besten. Sie modellieren auch nicht die Pipeline in der Zielmikroarchitektur, sie verwenden nur einige Heuristiken.)


Einfaches Loop-Abrollen hilft nicht; Diese Schleife führt zu Engpässen bei der Latenz einer Loop-getragenen Abhängigkeitskette, nicht beim Schleifenoverhead / Durchsatz. Dies bedeutet, dass es mit Hyperthreading (oder jeder anderen Art von SMT) gut tun würde, da die CPU viel Zeit hat, Befehle von zwei Threads zu verschachteln. Dies würde eine Parallelisierung der Schleife bedeuten main, aber das ist in Ordnung, weil jeder Thread nur einen Bereich von überprüfen kann n Werte und produzieren ein Paar von ganzen Zahlen als Ergebnis.

Interleaving von Hand in einem einzigen Thread könnte auch lebensfähig sein. Vielleicht berechnen Sie die Reihenfolge für ein Paar von Zahlen parallel, da jeder nur ein paar Register benötigt, und sie können alle dasselbe aktualisieren max / maxi. Dies schafft mehr Parallelität auf Anweisungsebene.

Der Trick ist zu entscheiden, ob bis alle warten sollen n Werte haben erreicht 1 bevor Sie ein weiteres Startpaar bekommen n Werte, oder ob sie ausbrechen und einen neuen Startpunkt für nur einen bekommen, der die Endbedingung erreicht hat, ohne die Register für die andere Sequenz zu berühren. Wahrscheinlich ist es am besten, jede Kette an nützlichen Daten arbeiten zu lassen, sonst müssten Sie ihren Zähler bedingt erhöhen.


Sie könnten dies vielleicht sogar mit SSE-Packed-Compare-Sachen tun, um den Zähler für Vektorelemente wo zu erhöhen n hatte nicht erreicht 1 noch. Und um dann die noch längere Latenz einer SIMD bedingten Inkrement-Implementierung zu verbergen, müssten Sie mehr Vektoren von n Werte in der Luft. Vielleicht nur wert mit 256b Vektor (4x uint64_t).

Ich denke, die beste Strategie, um eine Entdeckung zu machen 1 "sticky" bedeutet, den Vektor aller Einsen zu maskieren, den Sie hinzufügen, um den Zähler zu erhöhen. Also nachdem du eine gesehen hast 1 In einem Element wird der Inkrement-Vektor eine Null haben, und + = 0 ist ein No-Op.

Nicht getestete Idee für die manuelle Vektorisierung

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vprllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure.  Probably worth it
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

Sie können und sollten dies mit intrinsics anstelle von handschriftlicher asm implementieren.


Algorithmische / Implementierungsverbesserung:

Neben der Implementierung der gleichen Logik mit effizienteren asm, suchen Sie nach Möglichkeiten, um die Logik zu vereinfachen oder redundante Arbeit zu vermeiden. z.B. memoize, um gemeinsame Endungen für Sequenzen zu erkennen. Oder noch besser, schauen Sie sich 8 aufeinanderfolgende Bits auf einmal an (Gnashers Antwort)

@EOF weist darauf hin tzcnt (oder bsf) könnte verwendet werden, um mehrere zu tun n/=2 Iterationen in einem Schritt. Das ist wahrscheinlich besser als die SIMD-Vektorisierung, weil keine SSE- oder AVX-Anweisung das kann. Es ist immer noch kompatibel mit mehreren Skalaren ns parallel in verschiedenen Integer-Registern.

So könnte die Schleife so aussehen:

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

Dies kann zu deutlich weniger Iterationen führen, aber Verschiebungen mit variabler Anzahl sind bei Intel SnB-Familien-CPUs ohne BMI2 langsam. 3 Ups, 2c Latenz. (Sie haben eine Eingangsabhängigkeit von den FLAGS, weil count = 0 bedeutet, dass die Flags nicht modifiziert sind. Sie behandeln dies als Datenabhängigkeit und nehmen mehrere uops, weil ein uop nur zwei Eingänge haben kann (sowieso vor HSW / BDW). Dies ist die Art, auf die sich Leute beschweren, die sich über das crazy-CISC-Design von x86 beschweren. Es macht x86-CPUs langsamer als sie es wären, wenn die ISA heute von Grund auf neu entworfen würde, selbst auf eine weitgehend ähnliche Weise. (Das ist ein Teil der "x86-Steuer", die Geschwindigkeit / Leistung kostet.) SHRX / SHLX / SARX (BMI2) sind ein großer Gewinn (1 uop / 1c Latenzzeit).

Es setzt auch tzcnt (3c auf Haswell und später) auf den kritischen Pfad, so dass es die Gesamtlatenz der Loop-getragenen Abhängigkeitskette signifikant verlängert. Es macht keine Notwendigkeit für eine CMOV oder für die Vorbereitung einer Registerhaltung n>>1obwohl. @ Veedrac's Antwort überwindet all dies, indem die tzcnt / shift für mehrere Iterationen verschoben wird, was sehr effektiv ist (siehe unten).

Wir können sicher verwenden BSF oder TZCNT austauschbar, weil n kann zu diesem Zeitpunkt nie Null sein. Der Maschinencode von TZCNT dekodiert als BSF auf CPUs, die BMI1 nicht unterstützen. (Bedeutungslose Präfixe werden ignoriert, daher läuft REP BSF als BSF).

TZCNT schneidet auf AMD-CPUs, die es unterstützen, wesentlich besser ab als BSF, daher kann es eine gute Idee sein, es zu verwenden REP BSF, auch wenn es nicht wichtig ist, ZF einzustellen, wenn die Eingabe Null ist und nicht die Ausgabe. Einige Compiler tun dies, wenn Sie sie verwenden __builtin_ctzll sogar mit -mno-bmi.

Sie machen dasselbe auf Intel-CPUs, also speichern Sie das Byte, wenn das alles zählt. TZCNT auf Intel (vor Skylake) hat immer noch eine falsche Abhängigkeit vom angeblich nur schreibenden Ausgabeoperanden, genau wie BSF, um das undokumentierte Verhalten zu unterstützen, dass BSF mit Eingabe = 0 sein Ziel unverändert lässt. Sie müssen also umgehen, wenn Sie nicht nur für Skylake optimieren, so dass Sie vom zusätzlichen REP-Byte nichts gewinnen können. (Intel geht oft über das hinaus, was das x86-ISA-Handbuch erfordert, um zu vermeiden, dass weit verbreiteter Code, der von etwas abhängt, was er nicht sollte oder der rückwirkend nicht erlaubt ist, gebrochen wird. Windows 9x setzt kein spekulatives Vorabholen von TLB-Einträgen voraus, das war sicher, als der Code geschrieben wurde, bevor Intel die TLB-Verwaltungsregeln aktualisiert hat.)

Wie auch immer, LZCNT / TZCNT auf Haswell haben die gleiche falsche dep als POPCNT: siehe dieses Q & A. Dies ist der Grund, warum Sie in gcc's asm-Ausgabe für @ Veedracs Code sehen Brechen der Dep-Kette mit Xor-Nullstellung auf dem Register wird es als Ziel von TZCNT verwendet, wenn es nicht dst = src verwendet. Da TZCNT / LZCNT / POPCNT ihr Ziel niemals undefiniert oder unmodifiziert verlassen, ist diese falsche Abhängigkeit von der Ausgabe auf Intel-CPUs nur ein Leistungsfehler / eine Einschränkung. Vermutlich ist es ein paar Transistoren wert, sich wie andere Ups zu verhalten, die zur selben Ausführungseinheit gehen. Das einzige software-sichtbare Upside ist in der Interaktion mit einer anderen mikroarchitektonischen Beschränkung: Sie können einen Speicheroperanden mit einem indizierten Adressierungsmodus mikrofusionieren auf Haswell, aber auf Skylake, wo Intel die falsche Abhängigkeit für LZCNT / TZCNT entfernt hat, "entpacken" sie indizierte Adressierungsmodi, während POPCNT immer noch jeden Adr-Modus mikrofusionieren kann.


Verbesserungen an Ideen / Code aus anderen Antworten:

@ hidefromkgbs Antwort hat eine nette Beobachtung, dass Sie garantiert eine Rechtsverschiebung nach 3n + 1 machen können. Sie können dies noch effizienter berechnen, als nur die Prüfungen zwischen den Schritten auszulassen. Die asm-Implementierung in dieser Antwort ist jedoch gebrochen (sie hängt von OF ab, was nach SHRD mit einer Zählung> 1 nicht definiert ist), und langsam: ROR rdi,2 ist schneller als SHRD rdi,rdi,2und die Verwendung von zwei CMOV-Anweisungen auf dem kritischen Pfad ist langsamer als ein zusätzlicher TEST, der parallel ausgeführt werden kann.

Ich habe aufgeräumt / verbessert C (was den Compiler führt, um bessere asm zu produzieren), und getestet + arbeitet schneller asm (in den Kommentaren unterhalb der C) bis Godbolt: siehe den Link in @ hidefromkgbs Antwort. (Diese Antwort trifft das 30k Char Limit von den großen Godbolt URLs, aber Kurzlinks können verrotten und waren sowieso zu lang für goo.gl.)

Verbesserte auch die Ausgabe-Druck in eine Zeichenfolge zu konvertieren und zu machen write() anstatt ein Zeichen gleichzeitig zu schreiben. Dies minimiert die Auswirkungen auf das Timing des gesamten Programms mit perf stat ./collatz (um Leistungszähler aufzuzeichnen), und ich entschleierte einige der unkritischen asm.


@ Veedracs Code

Ich habe eine sehr kleine Beschleunigung von rechts-verlagern so viel wie wir kennt tun müssen, und überprüfen, um die Schleife fortzusetzen. Von 7.5s für Limit = 1e8 runter bis 7.275s, auf Core2Duo (Merom), mit einem Unroll-Faktor von 16.

Code + Kommentare auf Godbolt. Verwenden Sie diese Version nicht mit Klängen; Es macht etwas albern mit der Defer-Schleife. Einen tmp-Zähler verwenden k und dann fügen Sie es hinzu count später ändert sich was clang tut, aber das leicht tut weh gcc.

Siehe Diskussion in Kommentaren: Veedrac's Code ist Ausgezeichnet auf CPUs mit BMI1 (d. h. nicht Celeron / Pentium)


1747
2017-11-01 07:04



Zu behaupten, dass der C ++ - Compiler mehr optimalen Code produzieren kann als ein kompetenter Assembler, ist ein sehr schlechter Fehler. Und besonders in diesem Fall. Der Mensch kann den Code immer besser machen als der Compiler, und diese besondere Situation ist eine gute Illustration dieser Behauptung.

Die Zeitdifferenz, die Sie sehen, liegt daran, dass der Assembler-Code in der Frage in den inneren Schleifen sehr weit von optimal ist.

(Der folgende Code ist 32-Bit, kann aber leicht in 64-Bit konvertiert werden)

Zum Beispiel kann die Sequenzfunktion auf nur 5 Anweisungen optimiert werden:

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

Der ganze Code sieht so aus:

include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"

start:
        InitializeAll
        mov ecx, 999999
        xor edi, edi        ; max
        xor ebx, ebx        ; max i

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

        cmp     edi, esi
        cmovb   edi, esi
        cmovb   ebx, ecx

        dec     ecx
        jnz     .main_loop

        OutputValue "Max sequence: ", edi, 10, -1
        OutputValue "Max index: ", ebx, 10, -1

        FinalizeAll
        stdcall TerminateAll, 0

Um diesen Code zu kompilieren, FreshLib wird gebraucht.

In meinen Tests, (1 GHz AMD A4-1200 Prozessor), ist der obige Code ungefähr viermal schneller als der C ++ Code von der Frage (wenn er mit kompiliert wird) -O0: 430 ms vs. 1900 ms) und mehr als zweimal schneller (430 ms vs. 830 ms), wenn der C ++ - Code kompiliert wird -O3.

Die Ausgabe beider Programme ist gleich: max sequence = 525 auf i = 837799.


93
2017-11-01 08:29



Für mehr Leistung: Eine einfache Änderung ist, dass nach n = 3n + 1, n gerade ist, so dass Sie sofort durch 2 teilen können. Und n wird nicht 1 sein, du musst es also nicht testen. Sie können also einige if-Anweisungen speichern und schreiben:

while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
    n = (3*n + 1) / 2;
    if (n % 2 == 0) {
        do n /= 2; while (n % 2 == 0);
        if (n == 1) break;
    }
}

Hier ist ein groß win: Wenn Sie sich die niedrigsten 8 Bits von n ansehen, werden alle Schritte, bis Sie acht mal durch zwei geteilt haben, vollständig durch diese acht Bits bestimmt. Zum Beispiel, wenn die letzten acht Bits 0x01 sind, das ist im Binärformat ist Ihre Nummer ??? 0000 0001 dann sind die nächsten Schritte:

3n+1 -> ???? 0000 0100
/ 2  -> ???? ?000 0010
/ 2  -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2  -> ???? ???0 0010
/ 2  -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2  -> ???? ???? ?010
/ 2  -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2  -> ???? ???? ???0
/ 2  -> ???? ???? ????

So können alle diese Schritte vorhergesagt werden, und 256k + 1 wird durch 81k + 1 ersetzt. Etwas Ähnliches wird für alle Kombinationen passieren. So können Sie eine Schleife mit einer großen switch-Anweisung erstellen:

k = n / 256;
m = n % 256;

switch (m) {
    case 0: n = 1 * k + 0; break;
    case 1: n = 81 * k + 1; break; 
    case 2: n = 81 * k + 1; break; 
    ...
    case 155: n = 729 * k + 425; break;
    ...
}

Führen Sie die Schleife bis n ≤ 128, da an diesem Punkt n 1 mit weniger als 8 Divisionen von 2 werden könnte, und acht oder mehr Schritte gleichzeitig tun würden Sie den Punkt verpassen, wo Sie zum ersten Mal 1 erreichen. Dann fahre mit der "normalen" Schleife fort - oder lasse dir eine Tabelle erstellen, die dir sagt, wie viele weitere Schritte nötig sind, um 1 zu erreichen.

PS. Ich vermute stark, dass der Vorschlag von Peter Cordes es noch schneller machen würde. Es gibt keine bedingten Verzweigungen außer einer, und diese wird korrekt vorhergesagt, außer wenn die Schleife tatsächlich endet. Also wäre der Code etwas wie

static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }

while (n > 128) {
    size_t lastBits = n % 256;
    n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}

In der Praxis würden Sie messen, ob die Verarbeitung der letzten 9, 10, 11, 12 Bits von n gleichzeitig schneller wäre. Für jedes Bit würde sich die Anzahl der Einträge in der Tabelle verdoppeln, und ich würde eine Verlangsamung bemerken, wenn die Tabellen nicht mehr in den L1-Cache passen.

PPS. Wenn Sie die Anzahl der Operationen benötigen: In jeder Iteration machen wir genau acht Divisionen und eine variable Anzahl von (3n + 1) -Operationen, so dass eine naheliegende Methode zum Zählen der Operationen ein anderes Array wäre. Aber wir können tatsächlich die Anzahl der Schritte berechnen (basierend auf der Anzahl der Iterationen der Schleife).

Wir könnten das Problem leicht neu definieren: Ersetzen Sie n durch (3n + 1) / 2 falls ungerade, und ersetzen Sie n durch n / 2 wenn gerade. Dann macht jede Iteration genau 8 Schritte, aber Sie könnten das betrügen :-) Nehmen wir an, es gäbe r Operationen n <- 3n + 1 und s Operationen n <- n / 2. Das Ergebnis wird ziemlich genau n '= n * 3 ^ r / 2 ^ s sein, weil n <- 3n + 1 bedeutet n <- 3n * (1 + 1 / 3n). Unter Verwendung des Logarithmus finden wir r = (s + log2 (n '/ n)) / log2 (3).

Wenn wir die Schleife bis n ≤ 1.000.000 durchführen und eine vorberechnete Tabelle haben, wie viele Iterationen von jedem Startpunkt n ≤ 1.000.000 benötigt werden, ergibt die Berechnung von r wie oben, gerundet auf die nächste ganze Zahl, das richtige Ergebnis, wenn s nicht wirklich groß ist.


19
2017-11-02 10:04



Zu einem eher unzusammenhängenden Hinweis: mehr Performance-Hacks!

  • [Die erste «Vermutung» wurde von @ShreevatsaR endgültig entlarvt; entfernt]

  • Wenn wir die Sequenz durchlaufen, können wir nur 3 mögliche Fälle in der 2-Nachbarschaft des aktuellen Elements erhalten N (zuerst gezeigt):

    1. [gerade ungerade]
    2. [ungerade gerade]
    3. [gerade] [sogar]

    Über diese zwei Elemente zu springen bedeutet zu berechnen (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1 und N >> 2, beziehungsweise.

    Lassen Sie uns beweisen, dass es für beide Fälle (1) und (2) möglich ist, die erste Formel zu verwenden, (N >> 1) + N + 1.

    Fall (1) ist offensichtlich. Fall (2) impliziert (N & 1) == 1, wenn wir annehmen (ohne Verlust der Allgemeinheit), dass N 2 Bit lang ist und seine Bits sind ba von den meisten bis zu den wenigsten a = 1und folgendes gilt:

    (N << 1) + N + 1:     (N >> 1) + N + 1:
    
            b10                    b1
             b1                     b
           +  1                   + 1
           ----                   ---
           bBb0                   bBb
    

    woher B = !b. Rechtsverschiebung des ersten Ergebnisses gibt uns genau das, was wir wollen.

    Q. E.D .: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1.

    Wie bewiesen, können wir die Elemente der Sequenz 2 auf einmal durchlaufen, indem wir eine einzige ternäre Operation verwenden. Eine weitere 2 × Zeitreduzierung.

Der resultierende Algorithmus sieht folgendermaßen aus:

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

Hier vergleichen wir n > 2 weil der Prozess bei 2 statt 1 anhalten kann, wenn die Gesamtlänge der Sequenz ungerade ist.

[BEARBEITEN:]

Lassen Sie uns das in Assembly übersetzen!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

Verwenden Sie diese Befehle zum Kompilieren:

nasm -f elf64 file.asm
ld -o file file.o

Siehe das C und eine verbesserte / Bugfixed Version des Asms von Peter Cordes auf Godbolt. (Anmerkung des Redakteurs: Entschuldigung dafür, dass ich meine Sachen in deine Antwort geschrieben habe, aber meine Antwort traf das 30k Char-Limit von Godbolt Links + Text!)


17
2017-11-01 19:35



C ++ - Programme werden während der Generierung von Maschinencode aus dem Quellcode in Assemblerprogramme übersetzt. Es wäre praktisch falsch zu sagen, Assembly ist langsamer als C ++. Darüber hinaus unterscheidet sich der erzeugte Binärcode von Compiler zu Compiler. Also ein schlauer C ++ - Compiler kann produzieren binären Code optimaler und effizienter als ein dummer Assembler-Code.

Ich glaube jedoch, dass Ihre Profilierungsmethode gewisse Mängel aufweist. Die folgenden allgemeinen Richtlinien gelten für das Profiling:

  1. Stellen Sie sicher, dass sich Ihr System im Normal- / Leerlaufzustand befindet. Stoppen Sie alle laufenden Prozesse (Anwendungen), die Sie gestartet haben oder die CPU intensiv nutzen (oder über das Netzwerk abfragen).
  2. Ihre Datengröße muss größer sein.
  3. Ihr Test muss länger als 5-10 Sekunden dauern.
  4. Verlassen Sie sich nicht auf nur eine Probe. Führen Sie Ihren Test N-mal durch. Sammeln Sie Ergebnisse und berechnen Sie den Mittelwert oder Median des Ergebnisses.

5
2017-11-01 06:26



Von Kommentaren:

Aber dieser Code hört nie auf (wegen Integer-Überlauf)!?! Yves Daoust

Für viele Zahlen wird es nicht Überlauf.

Wenn es werden Überlauf - für einen dieser unglücklichen Anfangssamen wird die überflogene Zahl sehr wahrscheinlich gegen 1 ohne einen weiteren Überlauf konvergieren.

Dennoch wirft dies eine interessante Frage auf, gibt es eine Überlauf-zyklische Keimzahl?

Jede einfache letzte konvergierende Serie beginnt mit einem Zweierpotenzwert (offensichtlich genug?).

2 ^ 64 wird auf Null überlaufen, was eine undefinierte Endlosschleife gemäß dem Algorithmus ist (endet nur mit 1), aber die optimalste Lösung in Antwort wird aufgrund von enden shr rax ZF = 1 erzeugen.

Können wir 2 ^ 64 produzieren? Wenn die Startnummer ist 0x5555555555555555es ist ungerade Zahl, nächste Zahl ist dann 3n + 1, was ist 0xFFFFFFFFFFFFFFFF + 1 = 0. Theoretisch im undefinierten Zustand des Algorithmus, aber die optimierte Antwort von johnfound wird durch das Verlassen von ZF = 1 wiederhergestellt. Das cmp rax,1 von Peter Cordes wird in Endlosschleife enden (QED-Variante 1, "cheapo" durch undefined 0 Nummer).

Wie wäre es mit einer komplexeren Zahl, die ohne Zyklus entsteht? 0? Ehrlich gesagt, ich bin nicht sicher, meine Mathetheorie ist zu unklar, um eine ernsthafte Idee zu bekommen, wie man ernsthaft damit umgeht. Aber intuitiv würde ich sagen, dass die Reihe für jede Zahl zu 1 konvergieren wird: 0 <Zahl, da die 3n + 1 Formel langsam jeden Nicht-2 Primfaktor der ursprünglichen Zahl (oder Zwischenstufe) früher oder später in eine Potenz von 2 umwandelt . So müssen wir uns keine Sorgen um die Endlosschleife für die Originalserie machen, nur der Überlauf kann uns behindern.

Also habe ich nur ein paar Zahlen in das Blatt gelegt und mir die abgeschnittenen 8-Bit-Zahlen angesehen.

Es gibt drei überlaufende Werte 0: 227, 170 und 85 (85 direkt zu gehen 0Die anderen beiden kommen voran 85).

Aber es gibt keinen Wert, der zyklische Überlaufkeime erzeugt.

Lustigerweise habe ich einen Scheck, der die erste Nummer ist, die unter 8-Bit-Kürzung leidet, und schon 27 ist betroffen! Es erreicht einen Wert 9232 in richtigen nicht abgeschnittenen Reihen (erster abgeschnittener Wert ist 322 im 12. Schritt), und der maximale Wert, der für eine der 2-255 Eingangsnummern in nicht abgeschnittener Weise erreicht wird, ist 13120 (für die 255 selbst), maximale Anzahl der Schritte zu konvergieren 1 handelt von 128 (+ -2, nicht sicher, ob "1" zählt, etc ...).

Interessanterweise (für mich) die Nummer 9232 ist Maximum für viele andere Quellen, was ist das Besondere daran? :-O 9232 = 0x2410 ... hmmm .. keine Ahnung.

Leider kann ich diese Serie nicht verstehen, warum konvergiert sie und was bedeutet das für eine Abkürzung? k Bits, aber mit cmp number,1 Abbruchbedingung es ist sicherlich möglich, den Algorithmus in eine Endlosschleife mit einem bestimmten Eingabewert zu stellen, der mit endet 0 nach dem Abschneiden.

Aber der Wert 27 Überlauf für 8 Bit Fall ist eine Art Alarmierung, das sieht aus wie wenn Sie die Anzahl der Schritte zählen, um den Wert zu erreichen 1, erhalten Sie ein falsches Ergebnis für die Mehrheit der Zahlen aus dem gesamten k-Bit-Satz von ganzen Zahlen. Für die 8-Bit-Integer haben die 146 Zahlen von 256 die Folgen durch Abschneiden beeinflusst (einige von ihnen können vielleicht immer noch die richtige Anzahl von Schritten treffen, vielleicht bin ich zu faul, dies zu überprüfen).


4
2017-11-01 17:18



Du hast den vom Compiler generierten Code nicht gepostet, also gibt es hier ein Rätselraten, aber auch ohne es gesehen zu haben, kann man sagen:

test rax, 1
jpe even

... hat eine Chance von 50%, die Branche falsch einzuschätzen, und das wird teuer werden.

Der Compiler führt mit hoher Wahrscheinlichkeit beide Berechnungen durch (was weniger kostbar ist, da div / mod eine ziemlich lange Latenz hat, also ist die Multiplikation add "frei") und folgt mit einem CMOV. Was natürlich hat Null Prozent Wahrscheinlichkeit, falsch vorhergesagt zu werden.


4
2017-11-01 19:50



Selbst ohne die Montage zu betrachten, ist der offensichtlichste Grund das /= 2 ist wahrscheinlich optimiert als >>=1 und viele Prozessoren haben eine sehr schnelle Schiebeoperation. Aber auch wenn ein Prozessor keine Shift-Operation hat, ist die Ganzzahl-Division schneller als die Gleitkomma-Division.

Bearbeiten:  Ihr Kilometerstand kann variieren, je nachdem, ob die obige Anweisung "Ganzzahlige Division ist schneller als Gleitkomma Division" ist. Die folgenden Kommentare zeigen, dass die modernen Prozessoren die Optimierung der fp-Division gegenüber der Integer-Division priorisiert haben. Wenn also jemand nach dem wahrscheinlichsten Grund für die Beschleunigung sucht, nach der die Frage dieses Threads fragt, dann wird der Compiler optimiert /=2 wie >>=1 wäre der beste 1. Platz zum schauen.


Auf einem nicht zusammenhängende Notiz, ob n ist seltsam, der Ausdruck n*3+1 wird immer gleich sein. Es besteht also keine Notwendigkeit zu überprüfen. Sie können diesen Zweig zu ändern

{
   n = (n*3+1) >> 1;
   count += 2;
}

So wäre die ganze Aussage dann

if (n & 1)
{
    n = (n*3 + 1) >> 1;
    count += 2;
}
else
{
    n >>= 1;
    ++count;
}

4
2017-11-01 21:16



Als allgemeine Antwort, die nicht speziell auf diese Aufgabe ausgerichtet ist: In vielen Fällen können Sie jedes Programm erheblich beschleunigen, indem Sie Verbesserungen auf hohem Niveau vornehmen. So können Sie Daten einmal statt mehrmals berechnen, unnötige Arbeit vollständig vermeiden, Caches optimal einsetzen und so weiter. Diese Dinge sind viel einfacher in einer höheren Sprache zu tun.

Schreiben Assembler-Code ist es möglich um zu verbessern, was ein optimierender Compiler tut, aber es ist harte Arbeit. Sobald es fertig ist, ist der Code viel schwieriger zu modifizieren, daher ist es viel schwieriger, algorithmische Verbesserungen hinzuzufügen. Manchmal verfügt der Prozessor über Funktionen, die Sie nicht in einer höheren Programmiersprache verwenden können. In diesem Fall ist eine Inline-Assemblierung häufig hilfreich und Sie können trotzdem eine höhere Programmiersprache verwenden.

Bei den Euler-Problemen gelingt es dir meistens, etwas aufzubauen, herauszufinden, warum es langsam ist, etwas besser aufzubauen, herauszufinden, warum es langsam ist, und so weiter und so fort. Das ist sehr, sehr schwer mit Assembler. Ein besserer Algorithmus bei der Hälfte der möglichen Geschwindigkeit schlägt normalerweise einen schlechteren Algorithmus bei voller Geschwindigkeit, und es ist nicht trivial, die volle Geschwindigkeit in Assembler zu bekommen.


3
2017-11-04 17:15



Für das Collatz-Problem können Sie eine deutliche Leistungssteigerung erzielen, indem Sie die "Schwänze" zwischenspeichern. Dies ist ein Zeit / Speicher-Kompromiss. Siehe: Memo (https://en.wikipedia.org/wiki/Memoization). Sie könnten auch in dynamische Programmierlösungen für andere Zeit- / Speicher-Kompromisse schauen.

Beispiel für eine Python-Implementierung:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))

3
2017-11-05 18:49



Die einfache Antwort:

  • macht einen MOV RBX, 3 und MUL RBX ist teuer; ADD einfach RBX, RBX zweimal

  • ADD 1 ist hier wahrscheinlich schneller als INC

  • MOV 2 und DIV ist sehr teuer; Verschiebe einfach nach rechts

  • 64-Bit-Code ist normalerweise merklich langsamer als 32-Bit-Code und die Ausrichtungsprobleme sind komplizierter; Bei kleinen Programmen wie diesem müssen Sie sie packen, damit Sie parallel rechnen können, um schneller als 32-Bit-Code zu sein

Wenn Sie das Assembly-Listing für Ihr C ++ - Programm generieren, können Sie sehen, wie es sich von Ihrer Assembly unterscheidet.


-2
2017-11-07 01:03