Ich habe diese beiden Lösungen für Project Euler Q14 in Assembly und in C ++ geschrieben. Sie sind der gleiche identische Brute-Force-Ansatz zum Testen der Collatz-Vermutung . Die Montagelösung wurde mit 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 zur Verbesserung der Geschwindigkeit und alles, aber ich sehe nicht viele Möglichkeiten, meine Assembly-Lösung weiter zu optimieren (programmatisch nicht mathematisch gesprochen).

Der C ++ - Code hat einen Modul für jeden Term und eine Division für jeden geraden Term, wobei die Assembly nur eine Division pro geraden Term ist.

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

Ausführungszeiten

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

• g++ (nicht optimiert): durchschnittlich 1272 ms

• g++ -O3 Durchschnitt 578 ms

• Original asm (div) durchschnittlich 2650 ms

• Asm (shr) Durchschnitt 679 ms

• @johnfound asm , zusammengesetzt mit nasm avg 501 ms

• @hidefromkgb asm durchschnittlich 200 ms

• @hidefromkgb asm optimiert von @Peter Cordes durchschnittlich 145 ms

• @Veedrac C ++ durchschnittlich 81 ms mit -O3, 305 ms mit-O0

Wenn Sie der Meinung sind, dass ein 64-Bit-DIV-Befehl eine gute Möglichkeit ist, durch zwei zu teilen, ist es kein Wunder, dass die ASM-Ausgabe des Compilers Ihren handgeschriebenen Code übertrifft, selbst mit -O0(schnell kompilieren, keine zusätzliche Optimierung und Speichern / Neuladen in den Speicher nach / vor jeder C-Anweisung, damit ein Debugger Variablen ändern kann).

In Agner Fogs Handbuch zur Optimierung der Baugruppe erfahren Sie, wie Sie effizientes asm schreiben. Er hat auch Anweisungstabellen und eine Mikroarchivanleitung für spezifische Details für bestimmte CPUs. Siehe auch diex86 Tag Wiki für mehr Perf Links.

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

Normalerweise ist es in Ordnung, den Compiler seine Sache machen zu lassen, besonders wenn Sie versuchen, C ++ zu schreiben, das effizient kompiliert werden kann . Sehen Sie auch, ist Assemblierung schneller als kompilierte Sprachen? . Eine der Antworten enthält Links zu diesen übersichtlichen Folien, die zeigen, wie verschiedene C-Compiler einige wirklich einfache Funktionen mit coolen Tricks optimieren. Matt Godbolts CppCon2017-Vortrag „ Was hat mein Compiler in letzter Zeit für mich getan? Das Lösen des Compilerdeckels “ist ähnlich.

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

Bei Intel Haswell sind div r64es 36 Uops mit einer Latenz von 32-96 Zyklen und einem Durchsatz von einem pro 21-74 Zyklen. (Plus die 2 Uops, um RBX und Null-RDX einzurichten, aber die Ausführung außerhalb der Reihenfolge kann diese früh ausführen). High-Uop-Count-Anweisungen wie DIV sind mikrocodiert, was auch zu Front-End-Engpässen führen kann. In diesem Fall ist die Latenz der wichtigste Faktor, da sie Teil einer durch Schleifen übertragenen Abhängigkeitskette ist.

shr rax, 1macht die gleiche vorzeichenlose Division: Es ist 1 uop mit 1c Latenz und kann 2 pro Taktzyklus ausführen.

Zum Vergleich: Die 32-Bit-Division ist schneller, aber im Vergleich zu Verschiebungen immer noch schrecklich. idiv r32beträgt 9 Uops, 22-29c Latenz und einen pro 8-11c Durchsatz bei Haswell.

Wie Sie aus der -O0asm-Ausgabe von gcc ( Godbolt-Compiler-Explorer ) ersehen können , werden nur Verschiebungsanweisungen verwendet . clang -O0kompiliert naiv, wie Sie gedacht haben, selbst wenn Sie 64-Bit-IDIV zweimal verwenden. (Bei der Optimierung verwenden Compiler beide IDIV-Ausgänge, wenn die Quelle eine Division und einen Modul mit denselben Operanden ausführt, wenn sie überhaupt IDIV 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 das Erkennen der Division durch Konstante und das Verwenden von Verschiebungen (Potenz von 2) oder einer multiplikativen Festkomma-Inverse (Nicht-Potenz von 2), um IDIV zu vermeiden (siehe div_by_13im obigen Godbolt-Link).

gcc -Os(Optimale Größe) macht Gebrauch IDIV für Nicht-Power-of-2 - Abteilung, leider auch in Fällen , in denen der multiplikative Inverse - Code ist nur etwas größer , aber viel schneller.

Hilfe für den Compiler

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

Zunächst ist es nur interessant, die optimierte Compilerausgabe zu betrachten. ( -O3). -O0Geschwindigkeit ist grundsätzlich bedeutungslos.

Sehen Sie sich Ihre ASM-Ausgabe an (auf Godbolt oder sehen Sie, wie Sie "Rauschen" von der Ausgabe der GCC / Clang-Baugruppe entfernen? ). Wenn der Compiler überhaupt keinen optimalen Code erstellt: Das Schreiben Ihrer C / C ++ - Quelle auf eine Weise, die den Compiler dazu führt, besseren Code zu erstellen, ist normalerweise der beste Ansatz . Sie müssen asm kennen und wissen, was effizient ist, aber Sie wenden dieses Wissen indirekt an. Compiler sind auch eine gute Quelle für Ideen: Manchmal macht Clang etwas Cooles, und Sie können gcc dazu bringen, dasselbe zu tun: Sehen Sie sich diese Antwort an und was ich mit der nicht abgewickelten Schleife in @ Veedracs Code unten gemacht habe.)

Dieser Ansatz ist portabel, und in 20 Jahren kann ein zukünftiger Compiler ihn zu allem kompilieren, was auf zukünftiger Hardware (x86 oder nicht) effizient ist, möglicherweise mithilfe einer neuen ISA-Erweiterung oder einer automatischen Vektorisierung. Handgeschriebene x86-64 asm von vor 15 Jahren wären normalerweise nicht optimal auf Skylake abgestimmt. zB Vergleich & Verzweigung Makro-Fusion gab es damals noch nicht. Was jetzt für handgefertigte asm für eine Mikroarchitektur optimal ist, ist für andere aktuelle und zukünftige CPUs möglicherweise nicht optimal. In den Kommentaren zu @ johnfounds Antwort werden wichtige Unterschiede zwischen AMD Bulldozer und Intel Haswell erörtert , die einen großen Einfluss auf diesen Code haben. Aber theoretisch g++ -O3 -march=bdver3und g++ -O3 -march=skylakewird das Richtige tun. (Or -march=native.) Oder -mtune=...um einfach zu optimieren, ohne Anweisungen zu verwenden, die andere CPUs möglicherweise nicht unterstützen.

Meiner Meinung nach sollte es für zukünftige Compiler kein Problem sein, den Compiler zu einem ASM zu führen, der für eine aktuelle CPU, die Ihnen wichtig ist, gut ist. Sie sind hoffentlich besser als aktuelle Compiler darin, Wege zur Transformation von Code zu finden, und können einen Weg finden, der für zukünftige CPUs funktioniert. Unabhängig davon wird zukünftiges x86 bei nichts, was auf aktuellem x86 gut ist, wahrscheinlich schrecklich sein, und der zukünftige Compiler wird asm-spezifische Fallstricke vermeiden, während er so etwas wie die Datenbewegung von Ihrer C-Quelle implementiert, wenn er nichts Besseres sieht.

Handgeschriebener ASM ist eine Blackbox für den Optimierer, sodass die Konstantenausbreitung nicht funktioniert, wenn Inlining eine Eingabe zu einer Konstante für die Kompilierungszeit macht. Andere Optimierungen sind ebenfalls betroffen. Lesen Sie https://gcc.gnu.org/wiki/DontUseInlineAsm, bevor Sie asm verwenden. (Und vermeiden Sie Inline-Asm im MSVC-Stil: Ein- / Ausgänge müssen durch den Speicher gehen, was den Overhead erhöht .)

In diesem Fall : Ihr nhat einen vorzeichenbehafteten Typ, und gcc verwendet die SAR / SHR / ADD-Sequenz, die die richtige Rundung ergibt. (IDIV und Arithmetikverschiebung "rund" für negative Eingaben unterschiedlich, siehe den manuellen Eintrag SAR insn set ref ). (IDK, wenn gcc versucht hat und nicht beweisen konnte, dass ndies nicht negativ sein kann, oder was. Signed-Overflow ist ein undefiniertes Verhalten, daher hätte es möglich sein müssen.)

Sie sollten verwendet haben uint64_t n, damit es nur SHR kann. Und so ist es auf Systeme portierbar, auf denen longnur 32-Bit verfügbar ist (z. B. x86-64 Windows).

Übrigens, die optimierte ASM-Ausgabe von gcc sieht ziemlich gut aus (mit unsigned long n) : Die innere Schleife, in die sie inline ist, 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 verzweigungslos, und der kritische Pfad der schleifengetragenen Abhängigkeitskette lautet:

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

Gesamt: 5 Zyklen pro Iteration, Latenzzeitengpass . Die Ausführung außerhalb der Reihenfolge kümmert sich parallel dazu um alles andere (theoretisch: Ich habe nicht mit Perf-Zählern getestet, um festzustellen, ob es wirklich mit 5 c / iter läuft).

Der FLAGS-Eingang von cmov(von TEST erzeugt) ist schneller zu erzeugen als der RAX-Eingang (von LEA-> MOV), befindet sich also nicht auf dem kritischen Pfad.

In ähnlicher Weise befindet sich der MOV-> SHR, der den RDI-Eingang des CMOV erzeugt, außerhalb des kritischen Pfads, da er auch schneller als der LEA ist. MOV auf IvyBridge und höher hat keine Latenz (wird beim Umbenennen des Registers behandelt). (Es braucht immer noch ein UOP und einen Slot in der Pipeline, also 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 Pfads: Es wird nicht in einer Schleife übertragen, da Steuerungsabhängigkeiten im Gegensatz zu Datenabhängigkeiten auf dem kritischen Pfad mit Verzweigungsvorhersage + spekulativer Ausführung behandelt werden.

Den Compiler schlagen

GCC hat hier ziemlich gute Arbeit geleistet. Es könnte ein Codebyte speichern, indem es inc edxanstelle von verwendet wirdadd edx, 1 , da sich niemand um P4 und seine falschen Abhängigkeiten für Anweisungen zum Ändern von Teilflags kümmert.

Es könnten auch alle MOV-Anweisungen gespeichert werden, und TEST: SHR setzt CF = das herausgeschobene Bit, sodass wir cmovcanstelle von test/ verwenden können 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: Entfernen Sie das CMP, indem Sie das SHR-Flag-Ergebnis verzweigen und es für CMOV: Null verwenden, nur wenn n zu Beginn 1 (oder 0) war. (Unterhaltsame Tatsache: SHR mit count! = 1 bei Nehalem oder früher führt zu einem Stillstand, wenn Sie die Flag-Ergebnisse lesen .

Das Vermeiden von MOV hilft bei der Latenz bei Haswell überhaupt nicht ( Kann der MOV von x86 wirklich "kostenlos" sein? Warum kann ich das überhaupt nicht reproduzieren? ). Es hilft erheblich bei CPUs wie Intel Pre-IvB und der AMD Bulldozer-Familie, bei denen MOV keine Latenz von Null aufweist. Die verschwendeten MOV-Anweisungen des Compilers wirken sich auf den kritischen Pfad aus. Die komplexe LEA und CMOV von BD weisen beide eine geringere Latenz auf (2c bzw. 1c), sodass sie einen größeren Teil der Latenz ausmacht. Durchsatzengpässe werden ebenfalls zu einem Problem, da nur zwei ganzzahlige ALU-Pipes vorhanden sind. Siehe @ johnfounds Antwort , in der er Timing-Ergebnisse von einer AMD-CPU hat.

Selbst auf Haswell kann diese Version ein wenig helfen, indem sie gelegentliche Verzögerungen vermeidet, bei denen ein unkritischer UOP einen Ausführungsport von einem auf dem kritischen Pfad stiehlt und die Ausführung um 1 Zyklus verzögert. (Dies wird als Ressourcenkonflikt bezeichnet.) Außerdem wird ein Register gespeichert, was hilfreich sein kann, wenn mehrere nWerte in einer verschachtelten Schleife parallel ausgeführt werden (siehe unten).

Die Latenz von LEA hängt vom Adressierungsmodus der CPUs der Intel SnB-Familie ab. 3c für 3 Komponenten (für [base+idx+const]die zwei separate Adds erforderlich sind), aber nur 1c für 2 oder weniger Komponenten (eine Add). Einige CPUs (wie Core2) führen sogar eine 3-Komponenten-LEA in einem einzigen Zyklus durch, die SnB-Familie jedoch nicht. Schlimmer noch, die Intel SnB-Familie standardisiert Latenzen, sodass es keine 2c-Uops gibt , andernfalls wäre 3-Komponenten-LEA nur 2c wie Bulldozer. (3-Komponenten-LEA ist auch bei AMD langsamer, nur nicht so viel).

So lea rcx, [rax + rax*2]/ inc rcxist nur 2c Latenz, schneller als lea rcx, [rax + rax*2 + 1]auf Intel SnB-Familie CPUs wie Haswell. Break-Even bei BD und noch schlimmer bei Core2. Es kostet einen zusätzlichen UOP, was sich normalerweise nicht lohnt, um 1c Latenz zu sparen, aber die Latenz ist hier der größte Engpass, und Haswell verfügt über eine ausreichend breite Pipeline, um den zusätzlichen UOP-Durchsatz zu bewältigen.

Weder gcc, icc noch clang (auf godbolt) verwendeten die CF-Ausgabe von SHR, immer mit einem UND oder TEST . Dumme Compiler. : P Sie sind großartige Teile komplexer Maschinen, aber ein kluger Mensch kann sie oft bei kleinen Problemen schlagen. (Natürlich Tausende bis Millionen Mal länger, um darüber nachzudenken! Compiler verwenden keine erschöpfenden Algorithmen, um nach allen möglichen Methoden zu suchen, da dies zu lange dauern würde, wenn viel Inline-Code optimiert wird Sie modellieren die Pipeline auch nicht in der Zielmikroarchitektur, zumindest nicht im gleichen Detail wie IACA oder andere statische Analysewerkzeuge. Sie verwenden lediglich einige Heuristiken.)

Ein einfaches Abrollen der Schleife hilft nicht weiter . Diese Schleifenengpässe wirken sich auf die Latenz einer von Schleifen übertragenen Abhängigkeitskette aus, nicht auf den Schleifen-Overhead / Durchsatz. Dies bedeutet, dass es gut für Hyperthreading (oder jede andere Art von SMT) geeignet ist, da die CPU viel Zeit hat, um Anweisungen von zwei Threads zu verschachteln. Dies würde bedeuten main, dass die Schleife parallelisiert wird , aber das ist in Ordnung, da jeder Thread nur einen Wertebereich überprüfen nund als Ergebnis ein Paar von Ganzzahlen erzeugen kann.

Das Verschachteln von Hand innerhalb eines einzelnen Threads kann ebenfalls sinnvoll sein . Berechnen Sie möglicherweise die Sequenz für ein Zahlenpaar parallel, da jedes nur ein paar Register benötigt und alle das gleiche max/ aktualisieren können maxi. Dies schafft mehr Parallelität auf Befehlsebene .

Der Trick besteht darin, zu entscheiden, ob Sie warten sollen, bis alle nWerte erreicht sind, 1bevor Sie ein weiteres Paar von nStartwerten erhalten, oder ob Sie ausbrechen und einen neuen Startpunkt für nur einen erhalten, 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 zu arbeiten, sonst müssten Sie ihren Zähler bedingt erhöhen.

Sie könnten dies vielleicht sogar mit SSE-gepackten Vergleichsdaten tun, um den Zähler für Vektorelemente, die nnoch nicht erreicht wurden , bedingt zu erhöhen 1. Und um die noch längere Latenz einer SIMD-Implementierung mit bedingtem Inkrement zu verbergen, müssten Sie mehr Wertevektoren nin der Luft halten. Vielleicht nur mit 256b Vektor (4x uint64_t) wert .

Ich denke, die beste Strategie, um ein 1"klebriges" zu erkennen, besteht darin, den Vektor aller Einsen zu maskieren, die Sie hinzufügen, um den Zähler zu erhöhen. Nachdem Sie ein 1in einem Element gesehen haben, hat der Inkrement-Vektor eine Null und + = 0 ist ein No-Op.

Ungetestete Idee zur manuellen 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

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    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 handgeschriebenem ASM implementieren.

Verbesserung des Algorithmus / der Implementierung:

Suchen Sie nicht nur nach der Implementierung derselben Logik mit effizienterem asm, sondern auch nach Möglichkeiten, die Logik zu vereinfachen oder redundante Arbeiten zu vermeiden. zB merken, um gemeinsame Endungen von Sequenzen zu erkennen. Oder noch besser, schauen Sie sich 8 nachfolgende Bits gleichzeitig an (Gnashers Antwort)

@EOF weist darauf hin, dass tzcnt(oder bsf) verwendet werden können, um mehrere n/=2Iterationen in einem Schritt durchzuführen . Das ist wahrscheinlich besser als SIMD-Vektorisierung. Das kann kein SSE- oder AVX-Befehl. Es ist jedoch immer noch kompatibel mit der nparallelen Ausführung mehrerer Skalare in verschiedenen Ganzzahlregistern.

Die Schleife könnte also 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 führt möglicherweise zu erheblich weniger Iterationen, aber bei CPUs der Intel SnB-Familie ohne BMI2 sind Verschiebungen mit variabler Anzahl langsam. 3 Uops, 2c Latenz. (Sie haben eine Eingabeabhängigkeit von den FLAGS, da count = 0 bedeutet, dass die Flags unverändert sind. Sie behandeln dies als Datenabhängigkeit und nehmen mehrere Uops, da ein UOP nur 2 Eingänge haben kann (ohnehin vor HSW / BDW).) Dies ist die Art, auf die sich Leute beziehen, die sich über das verrückte CISC-Design von x86 beschweren. Dadurch werden x86-CPUs langsamer als wenn der ISA heute von Grund auf neu entwickelt würde, auch wenn dies größtenteils ähnlich ist. (dh dies ist Teil der "x86-Steuer", die Geschwindigkeit / Leistung kostet.) SHRX / SHLX / SARX (BMI2) sind ein großer Gewinn (1 uop / 1c Latenz).

Außerdem wird tzcnt (3c in Haswell und höher) auf den kritischen Pfad gesetzt, sodass die Gesamtlatenz der schleifengetragenen Abhängigkeitskette erheblich verlängert wird. Es ist jedoch keine CMOV oder Vorbereitung eines Registerbestands erforderlich n>>1. Die Antwort von @ Veedrac überwindet all dies, indem die tzcnt / shift für mehrere Iterationen verschoben wird, was sehr effektiv ist (siehe unten).

Wir können BSF oder TZCNT sicher austauschbar verwenden, da nes zu diesem Zeitpunkt niemals Null sein kann. Der Maschinencode von TZCNT wird auf CPUs, die BMI1 nicht unterstützen, als BSF dekodiert. (Bedeutungslose Präfixe werden ignoriert, daher wird REP BSF als BSF ausgeführt.)

TZCNT bietet auf AMD-CPUs, die es unterstützen, eine viel bessere Leistung als BSF. Daher kann es eine gute Idee sein, es zu verwenden REP BSF, auch wenn Sie ZF nicht einstellen möchten, wenn der Eingang Null und nicht der Ausgang ist. Einige Compiler tun dies, wenn Sie __builtin_ctzllsogar mit verwenden -mno-bmi.

Sie arbeiten auf Intel-CPUs gleich, speichern Sie also nur das Byte, wenn das alles ist, was zählt. TZCNT unter Intel (vor Skylake) ist wie BSF immer noch falsch vom angeblich schreibgeschützten Ausgabeoperanden abhängig, um das undokumentierte Verhalten zu unterstützen, dass BSF mit input = 0 sein Ziel unverändert lässt. Sie müssen das also umgehen, es sei denn, Sie optimieren nur für Skylake. Das zusätzliche REP-Byte bietet also nichts. (Intel geht oft über das hinaus, was das x86 ISA-Handbuch verlangt, um zu vermeiden, dass weit verbreiteter Code beschädigt wird, der von etwas abhängt, das es nicht sollte, oder das rückwirkend nicht zulässig ist. Beispielsweise geht Windows 9x nicht davon aus, dass TLB-Einträge spekulativ vorab abgerufen werden , was sicher war als der Code geschrieben wurde, bevor Intel die TLB-Verwaltungsregeln aktualisierte .)

Wie auch immer, LZCNT / TZCNT auf Haswell haben die gleiche falsche Dep wie POPCNT: siehe diese Fragen und Antworten . Aus diesem Grund sehen Sie in der asm-Ausgabe von gcc für den Code von @ Veedrac, dass die dep- Kette durch xor-zeroing in dem Register unterbrochen wird, das als Ziel von TZCNT verwendet werden soll, wenn dst = src nicht verwendet wird. Da TZCNT / LZCNT / POPCNT ihr Ziel niemals undefiniert oder unverändert lassen, ist diese falsche Abhängigkeit von der Ausgabe auf Intel-CPUs ein Leistungsfehler / eine Leistungsbeschränkung. Vermutlich ist es einige Transistoren / Leistung wert, wenn sie sich wie andere Uops verhalten, die zur gleichen Ausführungseinheit gehen. Der einzige Vorteil ist die Interaktion mit einer anderen Uarch-Einschränkung: Sie können einen Speicheroperanden mit einem indizierten Adressierungsmodus mikroverschmelzen auf Haswell, aber auf Skylake, wo Intel die falsche Dep für LZCNT / TZCNT entfernt hat, "laminieren" sie indizierte Adressierungsmodi, während POPCNT weiterhin jeden Adr-Modus mikroverschmelzen kann.

Verbesserungen an Ideen / Code aus anderen Antworten:

Die Antwort von @ hidefromkgb hat eine nette Beobachtung, dass Sie nach 3n + 1 garantiert eine Rechtsschicht machen können. Sie können dies noch effizienter berechnen, als nur die Überprüfungen zwischen den Schritten wegzulassen. Die asm-Implementierung in dieser Antwort ist jedoch fehlerhaft (dies hängt von OF ab, das nach SHRD mit einer Anzahl> 1 undefiniert ist) und langsam: ROR rdi,2ist schneller als SHRD rdi,rdi,2und die Verwendung von zwei CMOV-Anweisungen auf dem kritischen Pfad ist langsamer als ein zusätzlicher TEST das kann parallel laufen.

Ich habe aufgeräumtes / verbessertes C (das den Compiler dazu anleitet, besseres asm zu erzeugen) und Godbolt getestet + schnelleres asm (in Kommentaren unter dem C) getestet: siehe den Link in der Antwort von @ hidefromkgb . (Diese Antwort hat das 30.000-Zeichen-Limit der großen Godbolt-URLs erreicht, aber Shortlinks können verrotten und waren für goo.gl sowieso zu lang.)

Außerdem wurde der Ausgabedruck verbessert, um ihn in einen String zu konvertieren und einen zu erstellen, write()anstatt jeweils ein Zeichen zu schreiben. Dies minimiert die Auswirkungen auf das Timing des gesamten Programms mit perf stat ./collatz(um Leistungsindikatoren aufzuzeichnen), und ich habe einige der unkritischen Aspekte verschleiert.

@ Veedrac Code

Ich habe eine geringfügige Beschleunigung erhalten, weil ich so viel nach rechts verschoben habe, wie wir wissen , und überprüft habe, ob die Schleife fortgesetzt werden soll. Von 7,5 s für Limit = 1e8 bis 7,275 s bei Core2Duo (Merom) mit einem Abrollfaktor von 16.

Code + Kommentare zu Godbolt . Verwenden Sie diese Version nicht mit Clang. es macht etwas Dummes mit der Defer-Schleife. Wenn Sie einen tmp-Zähler verwenden kund ihn countspäter hinzufügen, ändert sich die Funktion von clang, aber das tut gcc leicht weh.

Siehe Diskussion in den Kommentaren: Der Code von Veedrac ist hervorragend auf CPUs mit BMI1 (dh nicht Celeron / Pentium).

Die Behauptung, dass der C ++ - Compiler optimaleren Code erzeugen kann als ein kompetenter Assembler-Programmierer, ist ein sehr schwerer Fehler. Und vor allem in diesem Fall. Der Mensch kann den Code immer besser machen als der Compiler, und diese besondere Situation ist ein gutes Beispiel für diese Behauptung.

Der Zeitunterschied, den Sie sehen, liegt darin, dass der Assembler-Code in der Frage in den inneren Schleifen bei weitem nicht optimal ist.

(Der folgende Code ist 32-Bit, kann aber problemlos 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 gesamte Code sieht aus wie:

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, wird FreshLib benötigt.

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

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

Für mehr Leistung: Bei einer einfachen Änderung wird beobachtet, dass nach n = 3n + 1 n gerade ist, sodass Sie sofort durch 2 teilen können. Und n wird nicht 1 sein, sodass Sie nicht darauf testen müssen. 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ßer Gewinn: Wenn Sie sich die niedrigsten 8 Bits von n ansehen, werden alle Schritte, bis Sie acht Mal durch 2 geteilt haben, vollständig durch diese acht Bits bestimmt. Wenn zum Beispiel die letzten acht Bits 0x01 sind, ist Ihre Zahl binär ???? 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  -> ???? ???? ????

Alle diese Schritte können also vorhergesagt werden, und 256k + 1 wird durch 81k + 1 ersetzt. Ähnliches passiert für alle Kombinationen. Sie können also 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 aus, bis n ≤ 128 ist, da an diesem Punkt n mit weniger als acht Teilungen durch 2 zu 1 werden kann. Wenn Sie acht oder mehr Schritte gleichzeitig ausführen, verpassen Sie den Punkt, an dem Sie zum ersten Mal 1 erreichen. Setzen Sie dann die "normale" Schleife fort - oder lassen Sie eine Tabelle erstellen, aus der hervorgeht, wie viele weitere Schritte erforderlich sind, um 1 zu erreichen.

PS. Ich vermute sehr, dass der Vorschlag von Peter Cordes es noch schneller machen würde. Es gibt überhaupt keine bedingten Verzweigungen außer einer, und diese wird korrekt vorhergesagt, außer wenn die Schleife tatsächlich endet. Der Code wäre also so 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 erwarte eine Verlangsamung, wenn die Tabellen nicht mehr in den L1-Cache passen.

PPS. Wenn Sie die Anzahl der Operationen benötigen: In jeder Iteration führen wir genau acht Teilungen durch zwei und eine variable Anzahl von (3n + 1) Operationen durch. Eine naheliegende Methode zum Zählen der Operationen wäre also ein anderes Array. Wir können jedoch 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, wenn ungerade, und ersetzen Sie n durch n / 2, wenn gerade. Dann macht jede Iteration genau 8 Schritte, aber Sie könnten dieses Betrügen in Betracht ziehen :-) Nehmen wir also an, es gab r Operationen n <- 3n + 1 und s Operationen n <- n / 2. Das Ergebnis ist ziemlich genau n '= n * 3 ^ r / 2 ^ s, weil n <- 3n + 1 n <- 3n * (1 + 1 / 3n) bedeutet. Aus dem Logarithmus ergibt sich 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 einem Startpunkt n ≤ 1.000.000 benötigt werden, ergibt die Berechnung von r wie oben, auf die nächste ganze Zahl gerundet, das richtige Ergebnis, es sei denn, s ist wirklich groß.

Ganz unabhängig: mehr Performance-Hacks!

• [Die erste «Vermutung» wurde schließlich von @ShreevatsaR entlarvt. entfernt]

• Beim Durchlaufen der Sequenz können nur 3 mögliche Fälle in der 2-Nachbarschaft des aktuellen Elements N(zuerst gezeigt) erhalten werden:

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

  LEAP Vergangenheit dieser Elemente 2 Mittel zu berechnen (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1und N >> 2, respectively.

  Beweisen wir, dass es in beiden Fällen (1) und (2) möglich ist, die erste Formel zu verwenden (N >> 1) + N + 1.

  Fall (1) ist offensichtlich. Fall (2) impliziert (N & 1) == 1also, wenn wir also (ohne Verlust der Allgemeinheit) annehmen, dass N 2 Bit lang ist und seine Bits bavon höchst bis niedrigstwert sind, dann a = 1gilt Folgendes:

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

  wo B = !b. Wenn Sie das erste Ergebnis nach rechts verschieben, erhalten Sie genau das, was wir wollen.

  QED : (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1.

  Wie bewiesen, können wir die Elemente der Sequenz 2 gleichzeitig mit einer einzigen ternären Operation durchlaufen. Eine weitere 2-fache 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 > 2weil der Prozess bei 2 statt 1 anhalten kann, wenn die Gesamtlänge der Sequenz ungerade ist.

[BEARBEITEN:]

Lassen Sie uns dies in Montage ü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 Herausgebers: Tut mir leid, dass ich meine Daten in Ihre Antwort aufgenommen habe, aber meine Antwort hat das 30.000-Zeichen-Limit von Godbolt-Links + Text erreicht!)

C ++ - Programme werden während der Generierung von Maschinencode aus dem Quellcode in Assembly-Programme übersetzt. Es wäre praktisch falsch zu sagen, dass die Assembly langsamer als C ++ ist. Darüber hinaus unterscheidet sich der generierte Binärcode von Compiler zu Compiler. Ein intelligenter C ++ - Compiler kann also Binärcode erzeugen, der optimaler und effizienter ist als der Code eines dummen Assemblers.

Ich glaube jedoch, dass Ihre Profilierungsmethode bestimmte Mängel aufweist. Im Folgenden finden Sie allgemeine Richtlinien für die Profilerstellung:

1. Stellen Sie sicher, dass sich Ihr System im Normal- / Leerlaufzustand befindet. Stoppen Sie alle laufenden Prozesse (Anwendungen), die Sie gestartet haben oder die 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 nur auf eine Probe. Führen Sie Ihren Test N-mal durch. Sammeln Sie die Ergebnisse und berechnen Sie den Mittelwert oder Median des Ergebnisses.

Für das Collatz-Problem können Sie die Leistung erheblich steigern, indem Sie die "Schwänze" zwischenspeichern. Dies ist ein Kompromiss zwischen Zeit und Speicher. Siehe: Memoization ( https://en.wikipedia.org/wiki/Memoization ). Sie können sich auch dynamische Programmierlösungen für andere Zeit- / Speicherkompromisse ansehen.

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))

Aus Kommentaren:

Dieser Code hört jedoch nie auf (wegen eines Ganzzahlüberlaufs)!?! Yves Daoust

Bei vielen Zahlen läuft es nicht über.

Wenn es wird überlaufen - für ein diese unglücklichen Anfang Samt, wird die überflogenen Zahl sehr wahrscheinlich konvergieren in Richtung 1 ohne einen weiteren Überlauf.

Trotzdem wirft dies eine interessante Frage auf: Gibt es eine überlaufzyklische Keimzahl?

Jede einfache endgültige konvergierende Reihe beginnt mit einer Potenz von zwei Werten (offensichtlich genug?).

2 ^ 64 wird auf Null überlaufen, was laut Algorithmus eine undefinierte Endlosschleife ist (endet nur mit 1), aber die optimalste Antwortlösung wird aufgrund der shr raxErzeugung von ZF = 1 beendet.

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

Wie wäre es mit einer komplexeren Zahl, die einen Zyklus ohne erzeugt 0? Ehrlich gesagt bin ich mir nicht sicher, ob meine Mathe-Theorie zu verschwommen ist, um eine ernsthafte Vorstellung davon zu bekommen, wie man ernsthaft damit umgeht. Aber intuitiv würde ich sagen, dass die Reihe für jede Zahl gegen 1 konvergiert: 0 <Zahl, da die 3n + 1-Formel früher oder später langsam jeden Nicht-2-Primfaktor der ursprünglichen Zahl (oder Zwischenstufe) in eine Zweierpotenz umwandelt . Wir müssen uns also keine Sorgen um die Endlosschleife für Originalserien machen, nur ein Überlauf kann uns behindern.

Also habe ich nur ein paar Zahlen in ein Blatt geschrieben und mir 8-Bit-Zahlen abgeschnitten.

Es gibt drei Werte überfüllt zu 0: 227, 170und 85( 85geht direkt an 0, beiden anderen voran in Richtung 85).

Es gibt jedoch keinen Wert, der einen zyklischen Überlauf erzeugt.

Lustigerweise habe ich einen Check durchgeführt, der die erste Zahl ist, die unter 8-Bit-Kürzung leidet und bereits 27betroffen ist! Es erreicht den Wert 9232in der richtigen nicht abgeschnittenen Reihe (der erste abgeschnittene Wert befindet sich 322im 12. Schritt), und der maximale Wert, der für eine der 2-255 Eingangsnummern auf nicht abgeschnittene Weise erreicht wird, ist 13120(für sich 255selbst) die maximale Anzahl von Schritten zu konvergieren 1ist ungefähr 128(+ -2, nicht sicher, ob "1" zählen soll, etc ...).

Interessanterweise ist (für mich) die Anzahl 9232für viele andere Quellennummern maximal. Was ist das Besondere daran? : -O 9232= 0x2410... hmmm .. keine Ahnung.

Leider kann ich kein tiefes Verständnis dieser Serie erhalten, warum es konvergieren und welche Auswirkungen sie von Kürzen k Bits, aber mit cmp number,1Endbedingung ist es sicherlich möglich , den Algorithmus in Endlosschleife mit bestimmtem Eingangswert endet zu setzen , da 0nach Kürzung.

Der Wert, der 27für den 8-Bit-Fall überläuft, ist jedoch eine Art Warnung. Wenn Sie die Anzahl der Schritte zählen, um den Wert zu erreichen 1, erhalten Sie für die Mehrheit der Zahlen aus der gesamten k-Bit-Menge von Ganzzahlen ein falsches Ergebnis. Für die 8-Bit-Ganzzahlen haben die 146 von 256 Zahlen die Serie durch Abschneiden beeinflusst (einige von ihnen treffen möglicherweise versehentlich immer noch die richtige Anzahl von Schritten, ich bin zu faul, um dies zu überprüfen).

Sie haben den vom Compiler generierten Code nicht veröffentlicht, daher gibt es hier einige Vermutungen, aber auch ohne ihn gesehen zu haben, kann man Folgendes sagen:

test rax, 1
jpe even

... hat eine 50% ige Chance, die Branche falsch vorherzusagen, und das wird teuer.

Der Compiler führt mit ziemlicher Sicherheit beide Berechnungen durch (was vernachlässigbar mehr kostet, da div / mod eine ziemlich lange Latenz hat, so dass das Multiplikationsaddieren "frei" ist) und führt anschließend eine CMOV durch. Was natürlich eine Null- Prozent-Chance hat, falsch vorhergesagt zu werden.

Selbst ohne Blick auf die Montage ist der offensichtlichste Grund, dass /= 2wahrscheinlich optimiert wird >>=1und viele Prozessoren einen sehr schnellen Schaltvorgang haben. Aber selbst wenn ein Prozessor keine Verschiebungsoperation hat, ist die Ganzzahldivision schneller als die Gleitkommadivision.

Bearbeiten: Ihre Laufleistung kann in der obigen Anweisung "Ganzzahldivision ist schneller als Gleitkommadivision" variieren. Die folgenden Kommentare zeigen, dass die modernen Prozessoren der Optimierung der fp-Division Vorrang vor der ganzzahligen Division eingeräumt haben. Also , wenn jemand sucht der wahrscheinlichste Grund für die Beschleunigung , die dieser Frage Thread etwa fragt, dann Compiler Optimierung /=2als >>=1der beste Platz 1 zu sehen wäre.

In einem anderen Zusammenhangn ist der Ausdruck n*3+1immer gerade , wenn er ungerade ist . Es besteht also keine Notwendigkeit zu überprüfen. Sie können diesen Zweig in ändern

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

Also wäre die ganze Aussage dann

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

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. B. einmal statt mehrmals Daten berechnen, unnötige Arbeit vollständig vermeiden, Caches optimal nutzen und so weiter. Diese Dinge sind in einer Hochsprache viel einfacher zu tun.

Schreiben Assembler Code ist es möglich , zu verbessern, was eine Optimierung der Compiler tun, aber es ist harte Arbeit. Und wenn dies erledigt ist, ist es viel schwieriger, Ihren Code zu ändern, sodass es viel schwieriger ist, algorithmische Verbesserungen hinzuzufügen. Manchmal verfügt der Prozessor über Funktionen, die Sie in einer Hochsprache nicht verwenden können. In diesen Fällen ist die Inline-Assemblierung häufig hilfreich und ermöglicht die Verwendung einer Hochsprache.

Bei den Euler-Problemen gelingt es Ihnen meistens, etwas zu bauen, herauszufinden, warum es langsam ist, etwas Besseres zu bauen, herauszufinden, warum es langsam ist und so weiter und so fort. Das ist sehr, sehr schwer mit Assembler. Ein besserer Algorithmus mit der halben möglichen Geschwindigkeit schlägt normalerweise einen schlechteren Algorithmus mit voller Geschwindigkeit, und es ist nicht trivial, die volle Geschwindigkeit im Assembler zu erreichen.

Die einfache Antwort:

• MOV RBX, 3 und MUL RBX zu machen ist teuer; nur RBX hinzufügen, RBX zweimal

• ADD 1 ist hier wahrscheinlich schneller als INC

• MOV 2 und DIV sind sehr teuer; einfach nach rechts verschieben

• 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 die Assembly-Liste für Ihr C ++ - Programm generieren, können Sie sehen, wie sie sich von Ihrer Assembly unterscheidet.