microarchitecture - optimizing software in c++ an optimization guide for windows linux and mac platforms




C++-Code zum Testen der Collatz-Vermutung schneller als handschriftliche Assemblierung-warum? (8)

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 montiert

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

Das C ++ wurde mit kompiliert

g++ p14.cpp -o p14

Assembly, S. 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, um meine Assembly-Lösung weiter zu optimieren (programmatisch und nicht mathematisch).

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

Die Assemblierung dauert jedoch durchschnittlich 1 Sekunde länger als die C ++ - Lösung. Warum ist das? Ich frage vor allem 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 durchschnittlich 578 ms

  • original asm (div) durchschnittlich 2650 ms

  • Asm (shr) durchschnittlich 679 ms

  • @johnfound asm , zusammengestellt mit nasm durchschnittlich 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


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. Wie das einmalige statt mehrfache Berechnen von Daten, das vollständige Vermeiden von unnötiger Arbeit, die bestmögliche Verwendung von Caches und so weiter. Diese Dinge sind in einer höheren Sprache viel einfacher zu tun.

Wenn Sie Assembler-Code schreiben, ist es möglich , die Leistung eines optimierenden Compilers zu verbessern, aber es ist harte Arbeit. Und sobald 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 höheren Sprache nicht verwenden können. In diesem Fall ist die Inline-Assemblierung häufig hilfreich, und Sie können dennoch eine höhere Sprache verwenden.

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


Beim Collatz-Problem können Sie die Leistung erheblich steigern, indem Sie die "Tails" zwischenspeichern. Dies ist ein Zeit / Speicher-Kompromiss. Siehe: Memoization ( https://en.wikipedia.org/wiki/Memoization ). Sie könnten auch nach dynamischen Programmierlösungen für andere Zeit- / Speicher-Kompromisse suchen.

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

Der offensichtlichste Grund, auch ohne die Montage zu betrachten, /= 2 ist wahrscheinlich die Optimierung, da >>=1 viele Prozessoren einen sehr schnellen Schichtbetrieb haben. Aber selbst wenn ein Prozessor keine Verschiebeoperation hat, ist die Ganzzahldivision schneller als die Gleitkommadivision.

Bearbeiten: Ihr Kilometerstand kann bei der obigen Anweisung "Ganzzahlige Division ist schneller als Gleitkommadivision" variieren. Die folgenden Kommentare zeigen, dass die modernen Prozessoren die Optimierung der fp-Division der Ganzzahldivision vorgezogen haben. Also , wenn jemand suchen die wahrscheinlichste Grund für die Beschleunigung , die diese Frage Thread etwa fragt, dann Compiler optimiert /=2 als >>=1 wäre die beste 1. Platz zu suchen.

Auf einer nicht verwandten Notiz , wenn n ungerade ist, der Ausdruck n*3+1 wird immer noch sein. Es ist also keine Überprüfung erforderlich. 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;
}

Die einfache Antwort:

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


Ziemlich unabhängig: mehr Performance-Hacks!

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

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

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

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

    Wir wollen 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 also (N & 1) == 1 , dass, wenn wir (ohne Verlust der Allgemeinheit) annehmen, dass N 2 Bit lang ist und seine Bits ba von der höchsten zur niedrigsten Signifikanz sind a = 1 , und Folgendes gilt:

    (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. Weitere 2-fache Zeitersparnis.

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

Sehen Sie sich das C und eine verbesserte / fehlerbereinigte Version des Asms von Peter Cordes auf Godbolt an . (Anmerkung der Redaktion: Entschuldigen Sie, dass Sie meine Angaben in Ihre Antwort aufgenommen haben, aber meine Antwort hat das 30-KB-Zeichen-Limit von Godbolt-Links + Text überschritten!)


Aus Kommentaren:

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

Bei vielen Nummern 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.

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

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

2 ^ 64 wird zu Null überlaufen, was laut Algorithmus eine undefinierte Endlosschleife ist (endet nur mit 1), aber die optimalste Antwortlösung wird beendet, da shr rax ZF = 1 erzeugt wird.

Können wir 2 ^ 64 produzieren? Wenn die Startnummer 0x5555555555555555 ungerade ist, ist die nächste Nummer 3n + 1, was 0xFFFFFFFFFFFFFFFF + 1 = ist 0 . Theoretisch ist der Algorithmus nicht definiert, aber die optimierte Antwort von johnfound wird wiederhergestellt, wenn ZF = 1 beendet wird. Die cmp rax,1 von Peter Cordes wird in Endlosschleife enden (QED Variante 1, "cheapo" durch undefinierte 0 Nummer).

Wie wäre es mit einer komplexeren Zahl, die einen Zyklus ohne erstellt 0 ? Ehrlich gesagt bin ich mir nicht sicher, ob meine Mathematiktheorie zu trübe 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 zu 1 konvergiert: 0 <Zahl, da die 3n + 1-Formel jeden Nicht-2-Primfaktor der ursprünglichen Zahl (oder Zwischenstufe) früher oder später langsam in eine Zweierpotenz umwandelt . Wir müssen uns also nicht um Endlosschleifen für Originalserien kümmern, nur ein Überlauf kann uns behindern.

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

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

Aber es ist wertlos, zyklisches Überlauf-Seed zu erzeugen.

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

Interessanterweise (für mich) ist die Anzahl 9232 für viele andere Quellnummern 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 was sind die Auswirkungen von Kürzen sie k Bits, aber mit cmp number,1 Endbedingung möglich ist es sicherlich den Algorithmus in Endlosschleife setzen mit bestimmtem Eingangswert endet wie 0 nach Kürzung.

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


Wenn Sie der Meinung sind, dass ein 64-Bit-DIV-Befehl ein guter Weg ist, um durch zwei zu dividieren, ist es kein Wunder, dass die asm-Ausgabe des Compilers Ihren handgeschriebenen Code -O0 , 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 der Anleitung zur Optimierung der Baugruppe von Agner Fog erfahren Sie, wie Sie effizient asm schreiben. Er hat auch Anweisungstabellen und eine Mikroarchitekturanleitung für spezifische Details für spezifische CPUs. Siehe auch das x86 Tag-Wiki für weiterführende Links.

Siehe auch diese allgemeinere Frage zum Abschneiden 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 tun zu lassen, besonders wenn Sie versuchen, C ++ zu schreiben, das effizient kompiliert werden kann . Sehen Sie auch, ist Assembler schneller als kompilierte Sprachen? . Eine der Antworten verlinkt auf diese tollen Folien, die zeigen, wie verschiedene C-Compiler einige wirklich einfache Funktionen mit coolen Tricks optimieren.

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

Bei Intel Haswell beträgt div r64 36 Uops mit einer Latenzzeit von 32 bis 96 Zyklen und einem Durchsatz von 1 pro 21 bis 74 Zyklen. (Plus die 2 Uops zum Einrichten von RBX und Zero RDX, aber bei einer Ausführung außerhalb der Reihenfolge können diese vorzeitig ausgeführt werden). High-Uop-Count-Befehle wie DIV sind mikrocodiert, was auch zu Front-End-Engpässen führen kann. In diesem Fall ist die Latenz der relevanteste Faktor, da sie Teil einer durch Schleifen übertragenen Abhängigkeitskette ist.

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

Zum Vergleich: Die 32-Bit-Division ist schneller, aber immer noch fürchterlich im Vergleich zu Verschiebungen. idiv r32 ist 9 uops, 22-29c latenz und einer pro 8-11c durchsatz auf haswell.

Wie Sie an der Ausgabe von -O0 asm von gcc ( Godbolt-Compiler-Explorer ) sehen können, werden nur die Anweisungen für Verschiebungen verwendet . clang -O0 kompiliert naiv, wie Sie dachten, selbst wenn Sie zweimal 64-Bit-IDIV verwenden. (Bei der Optimierung verwenden Compiler beide Ausgaben von IDIV, 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 wandelt sich immer durch GIMPLE um, was bedeutet, dass einige "Optimierungen" nicht deaktiviert werden können . Dies beinhaltet das Erkennen der Division durch Konstante und die Verwendung von Verschiebungen (Potenz von 2) oder eines multiplikativen Festkomma-Inversen (Nicht-Potenz von 2), um IDIV zu vermeiden (siehe div_by_13 im obigen Godbolt-Link).

gcc -Os (für Größe optimieren) verwendet IDIV für Division ohne Zweierpotenz, leider sogar in Fällen, in denen der multiplikative inverse Code nur geringfügig größer, aber viel schneller ist.

Dem Compiler helfen

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

Zunächst ist es nur interessant, die optimierte Compiler-Ausgabe zu betrachten. ( -O3 ). -O0 Geschwindigkeit ist grundsätzlich bedeutungslos.

Sehen Sie sich Ihre ASM-Ausgabe an (auf Godbolt oder unter So entfernen Sie "Rauschen" aus der GCC / Clang-Assembly-Ausgabe? ). Wenn der Compiler überhaupt keinen optimalen Code erstellt: Das Schreiben der C / C ++ - Quelle in einer Weise, die den Compiler dazu anleitet, 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 mit der Hand dazu bewegen, dasselbe zu tun: Sehen Sie sich diese Antwort und das an, was ich mit der nicht entrollten Schleife in @ Veedracs Code unten getan habe.)

Dieser Ansatz ist portabel, und in 20 Jahren kann ein zukünftiger Compiler ihn auf eine beliebige Art und Weise kompilieren, die auf künftiger Hardware (x86 oder nicht) effizient ist. Möglicherweise wird eine neue ISA-Erweiterung verwendet oder eine automatische Vektorisierung durchgeführt. Handgeschriebene x86-64-Formate von vor 15 Jahren wären für Skylake normalerweise nicht optimal abgestimmt. ZB Compare & Branch Macro-Fusion gab es damals noch nicht. Was jetzt für handgefertigtes asm für eine Mikroarchitektur optimal ist, ist möglicherweise für andere aktuelle und zukünftige CPUs nicht optimal. In den Kommentaren zu @ johnfounds Antwort werden die Hauptunterschiede zwischen AMD Bulldozer und Intel Haswell erörtert , die einen großen Einfluss auf diesen Code haben. Aber theoretisch werden g++ -O3 -march=bdver3 und g++ -O3 -march=skylake das Richtige tun. (Oder -march=native .) Oder -mtune=... zum -mtune=... , ohne Anweisungen zu verwenden, die andere CPUs möglicherweise nicht unterstützen.

Mein Gefühl ist, dass es für zukünftige Compiler kein Problem sein sollte, den Compiler so zu führen, dass er für eine aktuelle CPU, die Ihnen am Herzen liegt, gut ist. Sie sind hoffentlich besser als aktuelle Compiler darin, Wege zu finden, um Code zu transformieren, und können Wege finden, die für zukünftige CPUs funktionieren. Unabhängig davon wird das zukünftige x86 wahrscheinlich in nichts schlechtem sein, was auf dem aktuellen x86 gut ist, und der zukünftige Compiler wird asm-spezifische Fallstricke vermeiden, während er so etwas wie die Datenverschiebung aus Ihrer C-Quelle implementiert, wenn er nichts Besseres sieht.

Handgeschriebenes asm ist eine Blackbox für das Optimierungsprogramm, daher funktioniert die Konstantenausbreitung nicht, wenn Inlining eine Eingabe zu einer Konstanten 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 den Speicher durchlaufen, was zusätzlichen Aufwand bedeutet .)

In diesem Fall : Ihr n hat einen vorzeichenbehafteten Typ, und gcc verwendet die SAR / SHR / ADD-Sequenz, die die richtige Rundung ergibt. (IDIV und arithmetische Verschiebung "runden" für negative Eingaben unterschiedlich, siehe manuelle Eingabe von SAR insn set ref ). (IDK, wenn gcc versucht hat und nicht beweisen konnte, dass n nicht negativ sein kann, oder was. Signed-Overflow ist undefiniertes Verhalten, also hätte es können.)

Sie sollten uint64_t n , damit es nur SHR kann. Und so ist es portabel für Systeme mit nur 32-Bit- long (z. B. x86-64 Windows).

Übrigens sieht die optimierte asm-Ausgabe von gcc ziemlich gut aus (mit einem unsigned long n ) : Die innere Schleife, die es in main() einfügt, bewirkt Folgendes:

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

Insgesamt: 5 Zyklen pro Iteration, Latenzengpass . Parallel dazu erledigt die Out-of-Order-Ausführung alles andere (theoretisch: Ich habe noch nicht mit Leistungsindikatoren getestet, ob es wirklich mit 5c / iter läuft).

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

In ähnlicher Weise liegt das MOV-> SHR, das die RDI-Eingabe von CMOV erzeugt, außerhalb des kritischen Pfads, da es auch schneller als das LEA ist. MOV auf IvyBridge und höher hat keine Latenz (wird beim Umbenennen des Registers verarbeitet). (Es braucht immer noch ein UOP und einen Slot in der Pipeline, es ist also nicht frei, nur keine Latenz). Das 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 durch eine Schleife übertragen, da Steuerabhängigkeiten mit Verzweigungsvorhersage und spekulativer Ausführung behandelt werden, im Gegensatz zu Datenabhängigkeiten auf dem kritischen Pfad.

Den Compiler schlagen

GCC hat hier einen ziemlich guten Job gemacht. Durch die Verwendung von inc edx anstelle von add edx, 1 könnte ein Code-Byte add edx, 1 , da sich niemand um P4 und seine falschen Abhängigkeiten für Anweisungen zum Ändern von Teil-Flags kümmert.

Es könnte auch alle MOV-Anweisungen speichern, und TEST: SHR setzt CF = das herausgeschobene Bit, sodass wir cmovc anstelle 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 die Antwort von @ johnfound für einen weiteren cleveren Trick: Entfernen Sie das CMP, indem Sie auf das Flag-Ergebnis von SHR verzweigen und es für CMOV verwenden: Null 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 . Auf diese Weise haben sie es Single-UOP gemacht. Die Shift-by-1-Spezialcodierung ist jedoch in Ordnung.)

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

Sogar auf Haswell kann diese Version Abhilfe schaffen, indem gelegentliche Verzögerungen vermieden werden, bei denen ein unkritischer 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, was hilfreich sein kann, wenn mehrere n Werte 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 ( [base+idx+const] , für die zwei separate [base+idx+const] ), aber nur 1c mit 2 oder weniger Komponenten (eine Addition). 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 die Latenzen so, dass es keine 2c-Ups gibt , sonst wäre 3-Komponenten-LEA nur 2c wie Bulldozer. (3-Komponenten-LEA ist bei AMD ebenfalls langsamer, jedoch nicht so stark).

lea rcx, [rax + rax*2] / inc rcx ist also nur eine Latenz von lea rcx, [rax + rax*2] inc rcx , schneller als lea rcx, [rax + rax*2 + 1] , auf CPUs der Intel SnB-Familie wie Haswell. Breakeven auf BD und schlechter auf Core2. Es kostet einen zusätzlichen Durchsatz, der sich normalerweise nicht lohnt, um 1 Cent Latenz zu sparen. Die Latenz ist jedoch der größte Engpass, und Haswell verfügt über eine ausreichend breite Pipeline, um den zusätzlichen Durchsatz zu bewältigen.

Weder gcc, icc noch clang (bei godbolt) verwendeten den CF-Ausgang von SHR, immer mit AND oder TEST . Dumme Compiler. : P Sie sind große Teile komplexer Maschinen, aber ein kluger Mensch kann sie oft bei kleinen Problemen besiegen. (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 eine Menge inline Code optimiert würde Sie modellieren die Pipeline auch nicht in der Zielmikroarchitektur, zumindest nicht im gleichen Detail wie IACA oder andere statische Analysewerkzeuge, sondern verwenden lediglich einige Heuristiken.)

Einfaches Abrollen der Schleife hilft nicht . Diese Schleife hat Engpässe bei der Latenz einer durch die Schleife übertragenen Abhängigkeitskette und nicht beim Overhead / Durchsatz der Schleife. Dies bedeutet, dass es sich gut für Hyperthreading (oder jede andere Art von SMT) eignet, da die CPU viel Zeit zum Verschachteln von Anweisungen aus zwei Threads hat. Dies würde bedeuten, dass die Schleife in main parallelisiert wird, aber das ist in Ordnung, da jeder Thread nur einen Bereich von n Werten prüfen und 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 belegt und alle dasselbe max / maxi aktualisieren können. Dies schafft mehr Parallelität auf Befehlsebene .

Der Trick besteht darin, zu entscheiden, ob Sie warten müssen, bis alle n Werte 1 erreicht haben, bevor Sie ein weiteres Paar von n Startwerten erhalten, oder ob Sie einen neuen Startpunkt für einen Punkt abrufen möchten, der die Endbedingung erreicht hat, ohne die Register für das zu berühren andere Reihenfolge. 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-Packed-Compare-Dingen tun, um den Zähler für Vektorelemente, bei denen n noch nicht 1 erreicht hat, bedingt zu erhöhen. Und um die noch längere Latenz einer SIMD-Implementierung mit bedingten Inkrementen zu verbergen, müssen Sie mehr Vektoren mit n Werten in der Luft halten. Vielleicht nur mit 256b Vektor wert (4x uint64_t ).

Ich denke, die beste Strategie, um eine 1 "klebrig" zu erkennen, besteht darin, den Vektor aller Einsen zu maskieren, die Sie hinzufügen, um den Zähler zu erhöhen. Nachdem Sie also eine 1 in 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

    # 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 handgeschriebenem asm implementieren.

Verbesserung des Algorithmus / der Implementierung:

Suchen Sie nach Möglichkeiten, die Logik zu vereinfachen oder redundante Arbeit zu vermeiden, und implementieren Sie nicht nur dieselbe Logik mit effizienterem asm. zB merken, um gemeinsame Enden von Sequenzen zu erkennen. Oder noch besser, sehen Sie sich 8 nachgestellte Bits gleichzeitig an (gnashers Antwort)

@EOF weist darauf hin, dass mit tzcnt (oder bsf ) mehrere Iterationen mit n/=2 in einem Schritt ausgeführt werden können. Das ist wahrscheinlich besser als das Vektorisieren mit SIMD, da dies mit keinem SSE- oder AVX-Befehl möglich ist. Es ist jedoch weiterhin kompatibel, mehrere skalare n in verschiedenen Ganzzahlregistern parallel auszuführen.

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 deutlich weniger Iterationen, bei CPUs der Intel SnB-Familie ohne BMI2 ist die Verschiebung der Variablenanzahl jedoch langsam. 3 Ups, 2C Latenz. (Sie haben eine Eingangsabhängigkeit von den FLAGS, da count = 0 bedeutet, dass die Flags unverändert sind. Sie behandeln dies als Datenabhängigkeit und nehmen mehrere Uops entgegen, da ein Uop nur zwei Eingänge haben kann (ohnehin vor HSW / BDW).) Auf diese Art beziehen sich Leute, die sich über das verrückte CISC-Design von x86 beschweren. Dadurch werden x86-CPUs langsamer, als dies der Fall wäre, wenn der ISA heute von Grund auf neu entwickelt worden wäre, auch wenn dies größtenteils auf ähnliche Weise erfolgt. (Das heißt, 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 bei Haswell und höher) in den kritischen Pfad versetzt, wodurch die Gesamtlatenz der durch die Schleife übertragenen Abhängigkeitskette erheblich verlängert wird. Ein CMOV oder die Vorbereitung eines Registers mit n>>1 entfällt. 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 n 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, sodass REP BSF als BSF ausgeführt wird.)

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

Sie verhalten sich bei Intel-CPUs genauso, speichern Sie also einfach das Byte, wenn das alles ist, was zählt. TZCNT unter Intel (vor Skylake) ist genau wie BSF immer noch falsch vom angeblich schreibgeschützten Ausgabeoperanden abhängig, um das undokumentierte Verhalten zu unterstützen, dass BSF mit input = 0 das Ziel unverändert lässt. Sie müssen das also umgehen, es sei denn, Sie optimieren nur für Skylake, sodass das zusätzliche REP-Byte nichts bringt. (Intel geht oft über das hinaus, was das x86 ISA-Handbuch erfordert, um zu vermeiden, dass häufig verwendeter Code beschädigt wird, der von etwas abhängt, das er nicht sollte, oder das rückwirkend nicht zugelassen wird. Beispielsweise geht Windows 9x davon aus, dass TLB-Einträge nicht vorab spekulativ abgerufen werden , was sicher war als der Code geschrieben wurde, bevor Intel die TLB-Verwaltungsregeln aktualisiert hat .)

Wie auch immer, LZCNT / TZCNT auf Haswell haben die gleiche falsche Abhängigkeit wie POPCNT: siehe diese Fragen und Antworten. Aus diesem Grund wird in gccs asm-Ausgabe für @ Veedrac-Code die Dep-Kette durch Xor-Zeroing im Register unterbrochen, das als TZCNT-Ziel 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 lediglich 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, der von der Software gesehen werden kann, liegt in der Interaktion mit einer anderen Einschränkung der Mikroarchitektur: Sie können einen Speicheroperanden mit einem indizierten Adressierungsmodus auf Haswell mikro-fusionieren , aber auf Skylake, wo Intel die falsche Abhängigkeit für LZCNT / TZCNT beseitigt hat, werden sie "unlaminiert". Indizierte Adressierungsmodi, während POPCNT weiterhin jeden ADR-Modus mikroschmelzen kann.

Verbesserungen an Ideen / Code aus anderen Antworten:

Die Antwort von @hidefromkgb hat eine nette Beobachtung, dass Sie nach 3n + 1 garantiert eine richtige Schicht 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 Zählung> 1 undefiniert ist) und langsam: ROR rdi,2 ist schneller als SHRD rdi,rdi,2 und verwendet zwei CMOV-Anweisungen auf dem kritischen Pfad ist langsamer als ein zusätzlicher TEST, der parallel ausgeführt werden kann.

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

Verbesserte auch das Drucken der Ausgabe, um in einen String zu konvertieren und ein write() erzeugen write() anstatt jeweils ein Zeichen zu write() . Dies minimiert die Auswirkungen auf das Timing des gesamten Programms mit perf stat ./collatz (um Leistungsindikatoren aufzuzeichnen), und ich habe einige der nicht kritischen perf stat ./collatz .

@ Veedrac-Code

Ich habe eine sehr kleine Beschleunigung erhalten, weil ich so viel nach rechts geschaltet habe, wie wir wissen , und nachgesehen habe, um die Schleife fortzusetzen. Von 7,5 s für Limit = 1e8 bis zu 7,275 s auf Core2Duo (Merom) mit einem Abrollfaktor von 16.

Code + Kommentare zu Godbolt . Verwenden Sie diese Version nicht mit clang. es macht etwas albernes mit der Verzögerungsschleife. Die Verwendung eines tmp-Zählers k und die anschließende Addition zum späteren count ändert die Funktion des Klangs, schadet jedoch leicht gcc.

Siehe Diskussion in Kommentaren: Veedrac-Code ist auf CPUs mit BMI1 (dh nicht Celeron / Pentium) ausgezeichnet


Zu behaupten, der C ++ - Compiler könne optimaleren Code erzeugen 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 Assembly-Code in der Frage in den inneren Schleifen bei weitem nicht optimal ist.

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

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

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

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





x86