Das Ersetzen eines 32-Bit-Schleifenzählers durch 64-Bit führt auf Intel-CPUs zu verrückten Leistungsabweichungen mit _mm_popcnt_u64

Ich suchte nach dem schnellsten Weg zu popcountgroßen Datenfeldern. Ich habe einen sehr seltsamen Effekt festgestellt : Durch Ändern der Schleifenvariablen von, unsignedum uint64_tdie Leistung auf meinem PC um 50% zu senken.

Der Benchmark

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

Wie Sie sehen, erstellen wir einen Puffer mit zufälligen Daten, wobei die Größe xMegabyte xbeträgt und von der Befehlszeile gelesen wird. Anschließend durchlaufen wir den Puffer und verwenden eine nicht gerollte Version des x86- popcountIntrinsic, um die Popcount durchzuführen. Um ein genaueres Ergebnis zu erhalten, führen wir den Popcount 10.000 Mal durch. Wir messen die Zeiten für den Popcount. Im Großbuchstaben ist die Variable der inneren Schleife unsigned, im Kleinbuchstaben ist die Variable der inneren Schleife uint64_t. Ich dachte, dass dies keinen Unterschied machen sollte, aber das Gegenteil ist der Fall.

Die (absolut verrückten) Ergebnisse

Ich kompiliere es so (g ++ Version: Ubuntu 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

Hier sind die Ergebnisse auf meiner Haswell Core i7-4770K- CPU bei 3,50 GHz, die ausgeführt wird test 1(also 1 MB zufällige Daten):

• vorzeichenlos 41959360000 0,401554 Sek. 26,113 GB / s
• uint64_t 41959360000 0,759822 Sek. 13,8003 GB / s

Wie Sie sehen, ist der Durchsatz der uint64_tVersion nur halb so hoch wie der der unsignedVersion! Das Problem scheint zu sein, dass unterschiedliche Baugruppen generiert werden, aber warum? Zuerst dachte ich an einen Compiler-Fehler, also versuchte ich es clang++(Ubuntu Clang Version 3.4-1ubuntu3):

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

Ergebnis: test 1

• vorzeichenlos 41959360000 0,398293 Sek. 26,3267 GB / s
• uint64_t 41959360000 0,680954 Sek. 15,3986 GB / s

Es ist also fast das gleiche Ergebnis und immer noch seltsam. Aber jetzt wird es super seltsam. Ich ersetze die Puffergröße, die von der Eingabe gelesen wurde, durch eine Konstante 1, also ändere ich:

uint64_t size = atol(argv[1]) << 20;

zu

uint64_t size = 1 << 20;

Somit kennt der Compiler jetzt die Puffergröße zur Kompilierungszeit. Vielleicht kann es einige Optimierungen hinzufügen! Hier sind die Zahlen für g++:

• vorzeichenlos 41959360000 0,509156 Sek. 20,5944 GB / s
• uint64_t 41959360000 0,508673 Sek. 20,6139 GB / s

Jetzt sind beide Versionen gleich schnell. Das wurde unsigned jedoch noch langsamer ! Es fiel von 26bis ab 20 GB/s, wodurch eine Nichtkonstante durch einen konstanten Wert ersetzt wurde, was zu einer Deoptimierung führte . Im Ernst, ich habe keine Ahnung, was hier los ist! Nun aber zur clang++neuen Version:

• vorzeichenlos 41959360000 0,677009 Sek. 15,4484 GB / s
• uint64_t 41959360000 0,676909 Sek. 15,4906 GB / s

Warte was? Jetzt fielen beide Versionen auf die langsame Zahl von 15 GB / s. Das Ersetzen einer Nichtkonstante durch einen konstanten Wert führt in beiden Fällen sogar zu langsamem Code für Clang!

Ich habe einen Kollegen mit einer Ivy Bridge- CPU gebeten , meinen Benchmark zu erstellen. Er hat ähnliche Ergebnisse erzielt, daher scheint es nicht Haswell zu sein. Da zwei Compiler hier seltsame Ergebnisse liefern, scheint es sich auch nicht um einen Compiler-Fehler zu handeln. Wir haben hier keine AMD-CPU, daher konnten wir nur mit Intel testen.

Noch mehr Wahnsinn bitte!

Nehmen Sie das erste Beispiel (das mit atol(argv[1])) und setzen Sie ein staticvor die Variable, dh:

static uint64_t size=atol(argv[1])<<20;

Hier sind meine Ergebnisse in g ++:

• ohne Vorzeichen 41959360000 0,396728 Sek. 26,4306 GB / s
• uint64_t 41959360000 0,509484 Sek. 20,5811 GB / s

Ja, noch eine Alternative . Wir haben immer noch die schnellen 26 GB / s mit u32, aber wir haben es geschafft, u64mindestens von 13 GB / s auf die 20 GB / s-Version zu kommen! Auf dem PC meines Kollegen wurde die u64Version sogar noch schneller als die u32Version und lieferte das schnellste Ergebnis von allen. Leider funktioniert dies nur für g++, clang++scheint sich nicht darum zu kümmern static.

Meine Frage

Können Sie diese Ergebnisse erklären? Insbesondere:

• Wie kann es einen solchen Unterschied zwischen u32und geben u64?
• Wie kann das Ersetzen einer nicht konstanten durch eine konstante Puffergröße weniger optimalen Code auslösen ?
• Wie kann das Einfügen des staticSchlüsselworts die u64Schleife beschleunigen? Noch schneller als der Originalcode auf dem Computer meines Kollegen!

Ich weiß, dass die Optimierung ein heikles Gebiet ist, aber ich hätte nie gedacht, dass so kleine Änderungen zu einem 100% igen Unterschied in der Ausführungszeit führen können und dass kleine Faktoren wie eine konstante Puffergröße die Ergebnisse wieder vollständig mischen können. Natürlich möchte ich immer die Version haben, die 26 GB / s popcount kann. Der einzige zuverlässige Weg, den ich mir vorstellen kann, ist das Kopieren, Einfügen der Baugruppe für diesen Fall und die Verwendung der Inline-Baugruppe. Nur so kann ich Compiler loswerden, die bei kleinen Änderungen verrückt zu werden scheinen. Was denken Sie? Gibt es eine andere Möglichkeit, den Code mit der höchsten Leistung zuverlässig abzurufen?

Die Demontage

Hier ist die Demontage für die verschiedenen Ergebnisse:

26 GB / s-Version von g ++ / u32 / non-const bufsize :

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

13 GB / s-Version von g ++ / u64 / non-const bufsize :

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

15 GB / s Version von clang ++ / u64 / non-const bufsize :

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

20 GB / s-Version von g ++ / u32 & u64 / const bufsize :

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

15 GB / s Version von clang ++ / u32 & u64 / const bufsize :

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

Interessanterweise ist die schnellste Version (26 GB / s) auch die längste! Es scheint die einzige Lösung zu sein, die verwendet wird lea. Einige Versionen verwenden, um jbzu springen, andere verwenden jne. Abgesehen davon scheinen alle Versionen vergleichbar zu sein. Ich sehe nicht, woher eine 100% ige Leistungslücke stammen könnte, aber ich bin nicht so geschickt darin, Baugruppen zu entschlüsseln. Die langsamste Version (13 GB / s) sieht sogar sehr kurz und gut aus. Kann jemand das erklären?

Gewonnene Erkenntnisse

Egal wie die Antwort auf diese Frage lautet; Ich habe gelernt, dass in wirklich heißen Schleifen jedes Detail eine Rolle spielen kann, auch Details, die keine Verbindung zum heißen Code zu haben scheinen . Ich habe noch nie darüber nachgedacht, welchen Typ ich für eine Schleifenvariable verwenden soll, aber wie Sie sehen, kann eine so geringfügige Änderung einen 100% igen Unterschied bewirken ! Sogar der Speichertyp eines Puffers kann einen großen Unterschied machen, wie wir beim Einfügen des staticSchlüsselworts vor der Größenvariablen gesehen haben! In Zukunft werde ich immer verschiedene Alternativen auf verschiedenen Compilern testen, wenn ich wirklich enge und heiße Schleifen schreibe, die für die Systemleistung entscheidend sind.

Das Interessante ist auch, dass der Leistungsunterschied immer noch so hoch ist, obwohl ich die Schleife bereits viermal abgewickelt habe. Selbst wenn Sie sich abrollen, können Sie dennoch von großen Leistungsabweichungen betroffen sein. Ziemlich interessant.

Schuldiger: Falsche Datenabhängigkeit (und der Compiler ist sich dessen nicht einmal bewusst)

Auf Sandy / Ivy Bridge- und Haswell-Prozessoren lautet die Anweisung:

popcnt  src, dest

scheint eine falsche Abhängigkeit vom Zielregister zu haben dest. Obwohl der Befehl nur darauf schreibt, wartet der Befehl, bis er destfertig ist, bevor er ausgeführt wird. Diese falsche Abhängigkeit wird (jetzt) ​​von Intel als Erratum HSD146 (Haswell) und SKL029 (Skylake) dokumentiert.

Skylake hat dies für lzcntund behobentzcnt .
Cannon Lake (und Ice Lake) haben dies behoben popcnt.
bsfIch bsrhabe eine echte Ausgabeabhängigkeit: Ausgabe unverändert für Eingabe = 0. (Aber keine Möglichkeit, dies mit Intrinsics zu nutzen - nur AMD dokumentiert es und Compiler machen es nicht verfügbar.)

(Ja, diese Anweisungen werden alle auf derselben Ausführungseinheit ausgeführt. )

Diese Abhängigkeit hält nicht nur die 4 popcnts einer einzelnen Schleifeniteration auf. Es kann Schleifeniterationen übertragen, was es dem Prozessor unmöglich macht, verschiedene Schleifeniterationen zu parallelisieren.

Das unsignedvs. uint64_tund andere Optimierungen wirken sich nicht direkt auf das Problem aus. Sie beeinflussen jedoch den Registerzuweiser, der die Register den Variablen zuordnet.

In Ihrem Fall sind die Geschwindigkeiten ein direktes Ergebnis dessen, was an der (falschen) Abhängigkeitskette hängt, je nachdem, was der Registerzuweiser beschlossen hat.

• 13 GB / s haben eine Kette: popcnt- add- popcnt- popcnt→ nächste Iteration
• 15 GB / s haben eine Kette: popcnt- add- popcnt- add→ nächste Iteration
• 20 GB / s haben eine Kette: popcnt- popcnt→ nächste Iteration
• 26 GB / s haben eine Kette: popcnt- popcnt→ nächste Iteration

Der Unterschied zwischen 20 GB / s und 26 GB / s scheint ein geringfügiges Artefakt der indirekten Adressierung zu sein. In beiden Fällen stößt der Prozessor auf andere Engpässe, sobald Sie diese Geschwindigkeit erreicht haben.

Um dies zu testen, habe ich die Inline-Assembly verwendet, um den Compiler zu umgehen und genau die gewünschte Assembly zu erhalten. Ich habe die countVariable auch aufgeteilt , um alle anderen Abhängigkeiten zu beseitigen, die mit den Benchmarks in Konflikt geraten könnten.

Hier sind die Ergebnisse:

Sandy Bridge Xeon bei 3,5 GHz: (Den vollständigen Testcode finden Sie unten)

• GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
• Ubuntu 12

Verschiedene Register: 18.6195 GB / s

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

Gleiches Register: 8,49272 GB / s

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

Gleiches Register mit gebrochener Kette: 17.8869 GB / s

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

Was ist mit dem Compiler schief gelaufen?

Es scheint, dass weder GCC noch Visual Studio wissen, dass popcnteine solche falsche Abhängigkeit besteht. Trotzdem sind diese falschen Abhängigkeiten keine Seltenheit. Es geht nur darum, ob der Compiler davon Kenntnis hat.

popcntist nicht gerade die am häufigsten verwendete Anweisung. Es ist also keine große Überraschung, dass ein großer Compiler so etwas verpassen könnte. Es scheint auch nirgendwo eine Dokumentation zu geben, die dieses Problem erwähnt. Wenn Intel es nicht preisgibt, wird es niemand draußen wissen, bis jemand zufällig darauf stößt.

( Update: Ab Version 4.9.2 ist sich GCC dieser falschen Abhängigkeit bewusst und generiert Code, um diese zu kompensieren, wenn Optimierungen aktiviert sind. Wichtige Compiler anderer Anbieter, darunter Clang, MSVC und sogar Intels eigener ICC, sind sich dessen noch nicht bewusst Dieses mikroarchitektonische Erratum gibt keinen Code aus, der dies kompensiert.)

Warum hat die CPU eine so falsche Abhängigkeit?

Wir spekulieren kann: es läuft auf der gleichen Ausführungseinheit wie bsf/ bsrwas tun eine Ausgangsabhängigkeit aufweisen. ( Wie ist POPCNT in Hardware implementiert? ) Für diese Anweisungen dokumentiert Intel das ganzzahlige Ergebnis für Eingabe = 0 als "undefiniert" (mit ZF = 1), aber Intel-Hardware bietet tatsächlich eine stärkere Garantie, um zu vermeiden, dass alte Software beschädigt wird: Ausgabe unverändert. AMD dokumentiert dieses Verhalten.

Vermutlich war es irgendwie unpraktisch, einige Uops für diese Ausführungseinheit von der Ausgabe abhängig zu machen, andere nicht.

AMD-Prozessoren scheinen diese falsche Abhängigkeit nicht zu haben.

Der vollständige Testcode dient als Referenz:

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

Einen ebenso interessanten Benchmark finden Sie hier: http://pastebin.com/kbzgL8si
Dieser Benchmark variiert die Anzahl der popcnts in der (falschen) Abhängigkeitskette.

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s

Ich habe ein äquivalentes C-Programm zum Experimentieren codiert und kann dieses seltsame Verhalten bestätigen. Darüber hinaus ist gccdie 64-Bit-Ganzzahl (die wahrscheinlich size_tsowieso eine sein sollte ...) besser, da die Verwendung von uint_fast32_tgcc eine 64-Bit-Uint verwendet.

Ich habe ein bisschen mit der Assembly
herumgespielt : Nehmen Sie einfach die 32-Bit-Version, ersetzen Sie alle 32-Bit-Anweisungen / Register durch die 64-Bit-Version in der inneren Popcount-Schleife des Programms. Beobachtung: Der Code ist genauso schnell wie die 32-Bit-Version!

Dies ist offensichtlich ein Hack, da die Größe der Variablen nicht wirklich 64-Bit ist, da andere Teile des Programms immer noch die 32-Bit-Version verwenden. Solange jedoch die innere Popcount-Schleife die Leistung dominiert, ist dies ein guter Anfang .

Ich habe dann den Code der inneren Schleife aus der 32-Bit-Version des Programms kopiert, ihn auf 64-Bit gehackt und mit den Registern herumgespielt, um ihn als Ersatz für die innere Schleife der 64-Bit-Version zu verwenden. Dieser Code läuft auch so schnell wie die 32-Bit-Version.

Mein Fazit ist, dass dies eine schlechte Befehlsplanung durch den Compiler ist, nicht der tatsächliche Geschwindigkeits- / Latenzvorteil von 32-Bit-Befehlen.

(Vorsichtsmaßnahme: Ich habe die Montage gehackt, hätte etwas kaputt machen können, ohne es zu merken. Ich glaube nicht.)

Dies ist keine Antwort, aber es ist schwer zu lesen, wenn ich die Ergebnisse in einen Kommentar schreibe.

Ich erhalte diese Ergebnisse mit einem Mac Pro ( Westmere 6-Cores Xeon 3,33 GHz). Ich habe es mit kompiliert clang -O3 -msse4 -lstdc++ a.cpp -o a(-O2 bekomme das gleiche Ergebnis).

klirren mit uint64_t size=atol(argv[1])<<20;

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

klirren mit uint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

Ich habe auch versucht:

1. Kehren Sie die Testreihenfolge um, das Ergebnis ist das gleiche, sodass der Cache-Faktor ausgeschlossen wird.
2. Haben Sie die forAussage in umgekehrter Reihenfolge : for (uint64_t i=size/8;i>0;i-=4). Dies ergibt das gleiche Ergebnis und beweist, dass die Kompilierung intelligent genug ist, um die Größe nicht bei jeder Iteration durch 8 zu teilen (wie erwartet).

Hier ist meine wilde Vermutung:

Der Geschwindigkeitsfaktor besteht aus drei Teilen:

• Code-Cache: Die uint64_tVersion hat eine größere Codegröße, dies hat jedoch keine Auswirkungen auf meine Xeon-CPU. Dies macht die 64-Bit-Version langsamer.

• Anweisungen verwendet. Beachten Sie nicht nur die Anzahl der Schleifen, sondern der Zugriff auf den Puffer erfolgt über einen 32-Bit- und einen 64-Bit-Index für die beiden Versionen. Der Zugriff auf einen Zeiger mit einem 64-Bit-Offset erfordert ein dediziertes 64-Bit-Register und eine Adressierung, während Sie sofort einen 32-Bit-Offset verwenden können. Dies kann die 32-Bit-Version beschleunigen.

• Anweisungen werden nur beim 64-Bit-Kompilieren (dh Prefetch) ausgegeben. Dies macht 64-Bit schneller.

Die drei Faktoren stimmen mit den beobachteten scheinbar widersprüchlichen Ergebnissen überein.

Ich kann keine maßgebliche Antwort geben, aber einen Überblick über eine wahrscheinliche Ursache geben. Diese Referenz zeigt ziemlich deutlich, dass für die Anweisungen im Hauptteil Ihrer Schleife ein Verhältnis von 3: 1 zwischen Latenz und Durchsatz besteht. Es zeigt auch die Auswirkungen des Mehrfachversands. Da es in modernen x86-Prozessoren drei Ganzzahleinheiten gibt (Geben oder Nehmen), ist es im Allgemeinen möglich, drei Anweisungen pro Zyklus zu versenden.

Zwischen der Spitzenleistung der Pipeline und der Leistung bei mehreren Versendungen und dem Ausfall dieser Mechanismen liegt die Leistung um den Faktor sechs. Es ist ziemlich bekannt, dass die Komplexität des x86-Befehlssatzes das Auftreten von skurrilen Brüchen recht einfach macht. Das obige Dokument hat ein gutes Beispiel:

Die Pentium 4-Leistung für 64-Bit-Rechtsverschiebungen ist wirklich schlecht. Die 64-Bit-Linksverschiebung sowie alle 32-Bit-Verschiebungen weisen eine akzeptable Leistung auf. Es scheint, dass der Datenpfad von den oberen 32 Bit zu den unteren 32 Bit der ALU nicht gut entworfen ist.

Ich persönlich bin auf einen seltsamen Fall gestoßen, in dem eine Hot-Loop auf einem bestimmten Kern eines Vier-Kern-Chips erheblich langsamer lief (AMD, wenn ich mich recht erinnere). Wir haben tatsächlich eine bessere Leistung bei einer Berechnung zur Kartenreduzierung erzielt, indem wir diesen Kern ausgeschaltet haben.

Hier ist meine Vermutung ein Streit um ganzzahlige Einheiten: Die popcntBerechnungen für den Schleifenzähler und die Adresse können mit dem 32-Bit-Zähler kaum mit voller Geschwindigkeit ausgeführt werden, aber der 64-Bit-Zähler führt zu Konflikten und Pipeline-Verzögerungen. Da es pro Schleifenkörperausführung insgesamt nur etwa 12 Zyklen gibt, möglicherweise 4 Zyklen mit Mehrfachversand, kann ein einzelner Stillstand die Laufzeit vernünftigerweise um den Faktor 2 beeinflussen.

Die durch die Verwendung einer statischen Variablen hervorgerufene Änderung, die vermutlich nur zu einer geringfügigen Neuordnung der Anweisungen führt, ist ein weiterer Hinweis darauf, dass sich der 32-Bit-Code an einem Wendepunkt für Konflikte befindet.

Ich weiß, dass dies keine strenge Analyse ist, aber es ist eine plausible Erklärung.

Ich habe dies mit Visual Studio 2013 Express versucht , wobei ein Zeiger anstelle eines Index verwendet wurde, was den Prozess etwas beschleunigte. Ich vermute, das liegt daran, dass die Adressierung Offset + Register anstelle von Offset + Register + ist (Register << 3). C ++ - Code.

   uint64_t* bfrend = buffer+(size/8);
   uint64_t* bfrptr;

// ...

   {
      startP = chrono::system_clock::now();
      count = 0;
      for (unsigned k = 0; k < 10000; k++){
         // Tight unrolled loop with uint64_t
         for (bfrptr = buffer; bfrptr < bfrend;){
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
         }
      }
      endP = chrono::system_clock::now();
      duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
           << (10000.0*size)/(duration) << " GB/s" << endl;
   }

Assembler-Code: r10 = bfrptr, r15 = bfrend, rsi = count, rdi = buffer, r13 = k:

$LL5@main:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT $LN4@main
        npad    4
$LL2@main:
        mov     rax, QWORD PTR [r10+24]
        mov     rcx, QWORD PTR [r10+16]
        mov     r8, QWORD PTR [r10+8]
        mov     r9, QWORD PTR [r10]
        popcnt  rdx, rax
        popcnt  rax, rcx
        add     rdx, rax
        popcnt  rax, r8
        add     r10, 32
        add     rdx, rax
        popcnt  rax, r9
        add     rsi, rax
        add     rsi, rdx
        cmp     r10, r15
        jb      SHORT $LL2@main
$LN4@main:
        dec     r13
        jne     SHORT $LL5@main

Haben Sie versucht, -funroll-loops -fprefetch-loop-arrayszu GCC überzugehen?

Mit diesen zusätzlichen Optimierungen erhalte ich folgende Ergebnisse:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s

Haben Sie versucht, den Reduktionsschritt außerhalb der Schleife zu verschieben? Im Moment haben Sie eine Datenabhängigkeit, die wirklich nicht benötigt wird.

Versuchen:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

Sie haben auch ein seltsames Aliasing im Gange, von dem ich nicht sicher bin, ob es den strengen Aliasing-Regeln entspricht.

TL; DR: Verwenden Sie __builtinstattdessen Intrinsics. sie könnten zufällig helfen.

Ich konnte gcc4.8.4 (und sogar 4.7.3 auf gcc.godbolt.org) dazu bringen, optimalen Code dafür zu generieren, indem ich __builtin_popcountlldieselbe Assembleranweisung verwendete, aber Glück hatte und zufällig Code erstellte, der keinen unerwarteten hat lange schleifenübertragene Abhängigkeit aufgrund des falschen Abhängigkeitsfehlers.

Ich bin mir meines Benchmarking-Codes nicht 100% sicher, aber die objdumpAusgabe scheint meine Ansichten zu teilen. Ich benutze einige andere Tricks ( ++ivs i++), um den Compiler ohne movlAnweisung für mich zum Abrollen zu bringen (seltsames Verhalten, muss ich sagen).

Ergebnisse:

Count: 20318230000  Elapsed: 0.411156 seconds   Speed: 25.503118 GB/s

Benchmarking-Code:

#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len){
  uint64_t cnt = 0;
  for(size_t i = 0; i < len; ++i){
    cnt += __builtin_popcountll(buf[i]);
  }
  return cnt;
}

int main(int argc, char** argv){
  if(argc != 2){
    printf("Usage: %s <buffer size in MB>\n", argv[0]);
    return -1;
  }
  uint64_t size = atol(argv[1]) << 20;
  uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer));

  // Spoil copy-on-write memory allocation on *nix
  for (size_t i = 0; i < (size / 8); i++) {
    buffer[i] = random();
  }
  uint64_t count = 0;
  clock_t tic = clock();
  for(size_t i = 0; i < 10000; ++i){
    count += builtin_popcnt(buffer, size/8);
  }
  clock_t toc = clock();
  printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC)));
  return 0;
}

Kompilierungsoptionen:

gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench

GCC-Version:

gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4

Linux-Kernel-Version:

3.19.0-58-generic

CPU-Informationen:

processor   : 0
vendor_id   : GenuineIntel
cpu family  : 6
model       : 70
model name  : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz
stepping    : 1
microcode   : 0xf
cpu MHz     : 2494.226
cache size  : 6144 KB
physical id : 0
siblings    : 1
core id     : 0
cpu cores   : 1
apicid      : 0
initial apicid  : 0
fpu     : yes
fpu_exception   : yes
cpuid level : 13
wp      : yes
flags       : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt
bugs        :
bogomips    : 4988.45
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Versuchen Sie zunächst, die Spitzenleistung abzuschätzen. Überprüfen Sie https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf insbesondere Anhang C.

In Ihrem Fall zeigt Tabelle C-10, dass der POPCNT-Befehl eine Latenz von 3 Takten und einen Durchsatz von 1 Takt aufweist. Der Durchsatz zeigt Ihre maximale Taktrate an (multiplizieren Sie mit der Kernfrequenz und 8 Bytes bei popcnt64, um die bestmögliche Bandbreitennummer zu erhalten).

Untersuchen Sie nun, was der Compiler getan hat, und fassen Sie die Durchsätze aller anderen Anweisungen in der Schleife zusammen. Dies gibt die bestmögliche Schätzung für den generierten Code.

Schauen Sie sich zum Schluss die Datenabhängigkeiten zwischen Befehlen in der Schleife an, da diese eine latenzintensive Verzögerung anstelle des Durchsatzes erzwingen. Teilen Sie also Befehle mit einer einzelnen Iteration in Datenflussketten auf und berechnen Sie die Latenz über sie hinweg, und nehmen Sie dann naiv das Maximum von ihnen auf. Es wird eine grobe Schätzung unter Berücksichtigung der Datenflussabhängigkeiten geben.

In Ihrem Fall würde jedoch das richtige Schreiben von Code all diese Komplexität beseitigen. Anstatt sich auf dieselbe Zählvariable zu akkumulieren, akkumulieren Sie einfach auf verschiedene (wie count0, count1, ... count8) und fassen Sie sie am Ende zusammen. Oder erstellen Sie sogar ein Array von Zählwerten [8] und akkumulieren Sie es zu seinen Elementen - vielleicht wird es sogar vektorisiert und Sie erhalten einen viel besseren Durchsatz.

PS und führen Sie niemals eine Sekunde lang einen Benchmark durch. Erwärmen Sie zuerst den Kern und lassen Sie dann die Schleife mindestens 10 Sekunden oder besser 100 Sekunden lang laufen. Andernfalls testen Sie die Power Management-Firmware und die DVFS-Implementierung in Hardware :)

PPS Ich hörte endlose Debatten darüber, wie viel Zeit Benchmark wirklich laufen sollte. Die meisten klügsten Leute fragen sogar, warum 10 Sekunden nicht 11 oder 12. Ich sollte zugeben, dass dies theoretisch lustig ist. In der Praxis führen Sie einfach hundert Mal hintereinander einen Benchmark durch und zeichnen Abweichungen auf. Das IST lustig. Die meisten Leute wechseln genau EINMAL die Quelle und führen die Bank aus, um einen neuen Leistungsrekord zu erzielen. Mach die richtigen Dinge richtig.

Noch nicht überzeugt? Verwenden Sie einfach die obige C-Version des Benchmarks von assp1r1n3 ( https://stackoverflow.com/a/37026212/9706746 ) und versuchen Sie 100 anstelle von 10000 in einer Wiederholungsschleife.

Meine 7960X zeigt mit RETRY = 100:

Anzahl: 203182300 Verstrichen: 0,008385 Sekunden Geschwindigkeit: 12,505379 GB / s

Anzahl: 203182300 Verstrichen: 0,011063 Sekunden Geschwindigkeit: 9,478225 GB / s

Anzahl: 203182300 Verstrichen: 0,011188 Sekunden Geschwindigkeit: 9,372327 GB / s

Anzahl: 203182300 Verstrichen: 0,010393 Sekunden Geschwindigkeit: 10,089252 GB / s

Anzahl: 203182300 Verstrichen: 0,009076 Sekunden Geschwindigkeit: 11,553283 GB / s

mit RETRY = 10000:

Anzahl: 20318230000 Verstrichen: 0,661791 Sekunden Geschwindigkeit: 15,844519 GB / s

Anzahl: 20318230000 Verstrichen: 0,665422 Sekunden Geschwindigkeit: 15,758060 GB / s

Anzahl: 20318230000 Verstrichen: 0,660983 Sekunden Geschwindigkeit: 15,863888 GB / s

Anzahl: 20318230000 Verstrichen: 0,665337 Sekunden Geschwindigkeit: 15,760073 GB / s

Anzahl: 20318230000 Verstrichen: 0,662138 Sekunden Geschwindigkeit: 15,836215 GB / s

PPPS Endlich auf "akzeptierte Antwort" und anderes Geheimnis ;-)

Verwenden wir die Antwort von assp1r1n3 - er hat einen 2,5-GHz-Kern. POPCNT hat 1 Taktdurchsatz, sein Code verwendet 64-Bit-Popcnt. Mathe ist also 2,5 GHz * 1 Takt * 8 Bytes = 20 GB / s für sein Setup. Er sieht 25 Gbit / s, möglicherweise aufgrund eines Turbo-Boosts auf etwa 3 GHz.

Gehen Sie daher zu ark.intel.com und suchen Sie nach i7-4870HQ: https://ark.intel.com/products/83504/Intel-Core-i7-4870HQ-Processor-6M-Cache-up-to-3-70 -GHz-? Q = i7-4870HQ

Dieser Kern könnte bis zu 3,7 GHz erreichen und die tatsächliche maximale Rate beträgt 29,6 GB / s für seine Hardware. Wo sind also noch 4 GB / s? Möglicherweise wird es für Schleifenlogik und anderen umgebenden Code innerhalb jeder Iteration ausgegeben.

Jetzt wo ist diese falsche Abhängigkeit? Hardware läuft fast mit Spitzenrate. Vielleicht ist meine Mathematik schlecht, es passiert manchmal :)

PPPPPS Immer noch Leute, die HW-Errata vorschlagen, sind schuld, also folge ich dem Vorschlag und erstelle ein Inline-Asm-Beispiel, siehe unten.

Auf meinem 7960X läuft die erste Version (mit Einzelausgabe an cnt0) mit 11 MB / s, die zweite Version (mit Ausgabe an cnt0, cnt1, cnt2 und cnt3) mit 33 MB / s. Und man könnte sagen - voila! es ist Ausgabeabhängigkeit.

OK, vielleicht habe ich darauf hingewiesen, dass es keinen Sinn macht, solchen Code zu schreiben, und dass es sich nicht um ein Problem der Ausgabeabhängigkeit handelt, sondern um eine dumme Codegenerierung. Wir testen keine Hardware, wir schreiben Code, um maximale Leistung zu erzielen. Sie könnten erwarten, dass HW OOO diese "Ausgabeabhängigkeiten" umbenennt und verbirgt, aber, gash, machen Sie einfach die richtigen Dinge richtig und Sie werden niemals einem Rätsel gegenüberstehen.

uint64_t builtin_popcnt1a(const uint64_t* buf, size_t len) 
{
    uint64_t cnt0, cnt1, cnt2, cnt3;
    cnt0 = cnt1 = cnt2 = cnt3 = 0;
    uint64_t val = buf[0];
    #if 0
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "popcnt %2, %1\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0)
        : "q" (val)
        :
        );
    #else
        __asm__ __volatile__ (
            "1:\n\t"
            "popcnt %5, %1\n\t"
            "popcnt %5, %2\n\t"
            "popcnt %5, %3\n\t"
            "popcnt %5, %4\n\t"
            "subq $4, %0\n\t"
            "jnz 1b\n\t"
        : "+q" (len), "=q" (cnt0), "=q" (cnt1), "=q" (cnt2), "=q" (cnt3)
        : "q" (val)
        :
        );
    #endif
    return cnt0;
}

Ok, ich möchte eine kleine Antwort auf eine der vom OP gestellten Unterfragen geben, die in den vorhandenen Fragen nicht behandelt zu werden scheinen. Vorsichtsmaßnahme, ich habe keine Tests oder Codegenerierung oder Demontage durchgeführt, wollte nur einen Gedanken teilen, den andere möglicherweise erläutern sollten.

Warum ändert das staticdie Leistung?

Die fragliche Zeile: uint64_t size = atol(argv[1])<<20;

Kurze Antwort

Ich würde mir die Assembly ansehen, die für den Zugriff generiert wurde, sizeund prüfen, ob für die nicht statische Version zusätzliche Schritte der Zeiger-Indirektion erforderlich sind.

Lange Antwort

Da es nur eine Kopie der Variablen gibt, unabhängig davon, ob sie deklariert wurde staticoder nicht, und sich die Größe nicht ändert, gehe ich davon aus, dass der Unterschied die Position des Speichers ist, der zum Sichern der Variablen verwendet wird, sowie die Position, an der sie im Code weiter verwendet wird Nieder.

Denken Sie zunächst daran, dass allen lokalen Variablen (zusammen mit den Parametern) einer Funktion Speicherplatz auf dem Stapel zur Verwendung als Speicher zur Verfügung gestellt wird. Offensichtlich wird der Stapelrahmen für main () nie bereinigt und nur einmal generiert. Ok, was ist damit static? In diesem Fall weiß der Compiler, dass er Speicherplatz im globalen Datenbereich des Prozesses reservieren muss, sodass der Speicherort nicht durch Entfernen eines Stapelrahmens gelöscht werden kann. Trotzdem haben wir nur einen Standort. Was ist der Unterschied? Ich vermute, es hat damit zu tun, wie auf Speicherorte auf dem Stapel verwiesen wird.

Wenn der Compiler die Symboltabelle generiert, gibt er lediglich einen Eintrag für eine Beschriftung zusammen mit relevanten Attributen wie Größe usw. ein. Er weiß, dass er den entsprechenden Speicherplatz reservieren muss, wählt diesen Speicherort jedoch erst etwas später aus Prozess nach Durchführung der Lebendigkeitsanalyse und möglicherweise Registerzuordnung. Woher weiß der Linker dann, welche Adresse er dem Maschinencode für den Endmontagecode geben muss? Es kennt entweder den endgültigen Standort oder weiß, wie es am Standort ankommt. Mit einem Stapel ist es ziemlich einfach, auf eine Position zu verweisen, die auf zwei Elementen basiert, dem Zeiger auf den Stapelrahmen und dann einem Versatz in den Rahmen. Dies liegt im Wesentlichen daran, dass der Linker den Speicherort des Stackframes vor der Laufzeit nicht kennen kann.