Frage Das Ersetzen einer 32-Bit-Schleifenanzahlvariablen durch 64-Bit führt zu verrückten Leistungsabweichungen


Ich war auf der Suche nach dem schnellsten Weg popcount große Datenfelder. Ich bin einer begegnet sehr merkwürdig Effekt: Ändern der Loop-Variablen von unsigned zu uint64_t Die Leistung sank auf meinem PC um 50%.

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 aus zufälligen Daten mit der Größe x Megabyte wo x wird von der Befehlszeile gelesen. Danach iterieren wir über den Puffer und verwenden eine unrollte Version des x86 popcount intrinsisch, um den Popcount durchzuführen. Um ein präziseres Ergebnis zu erhalten, machen wir den Popcount 10.000 mal. Wir messen die Zeiten für den Popcount. Im großen Fall ist die innere Schleifenvariable unsignedim kleinen Fall ist die innere Schleifenvariable uint64_t. Ich dachte, das sollte keinen Unterschied machen, 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 meinem Haswell  Core i7-4770K CPU @ 3,50 GHz, läuft test 1 (also 1 MB zufällige Daten):

  • unsigniert 41959360000 0,401554 sek 26,113 GB / s
  • uint64_t 41959360000 0,759822 sek 13.8003 GB / s

Wie Sie sehen, der Durchsatz der uint64_t Version ist nur die Hälfte der eine der unsigned Ausführung! Das Problem scheint zu sein, dass verschiedene Assembly generiert wird, aber warum? Zuerst dachte ich an einen Compilerfehler, also habe ich es versucht clang++ (Ubuntu Clang Version 3.4-1ubuntu3):

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

Ergebnis: test 1

  • unsigniert 41959360000 0,398293 sek 26.3267 GB / s
  • uint64_t 41959360000 0,680954 sek 15.3986 GB / s

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

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

zu

uint64_t size = 1 << 20;

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

  • unsigniert 41959360000 0,509156 sek 20.5944 GB / s
  • uint64_t 41959360000 0,508673 sek 20.6139 GB / s

Jetzt sind beide Versionen gleich schnell. Aber die unsigned  wurde noch langsamer! Es fiel aus 26 zu 20 GB/s, wodurch ein nicht konstanter Wert durch einen konstanten Wert ersetzt wird De-Optimierung. Ernsthaft, ich habe keine Ahnung, was hier vor sich geht! Aber jetzt zu clang++ mit der neuen Version:

  • unsigniert 41959360000 0,677009 sek 15.4884 GB / s
  • uint64_t 41959360000 0.676909 sek 15.4906 GB / s

Warte was? Jetzt fielen beide Versionen auf die langsam Anzahl von 15 GB / s. Somit führt das Ersetzen eines Nicht-Konstanten durch einen konstanten Wert sogar zu einem langsamen Code-In beide Fälle für Clang!

Ich fragte einen Kollegen mit einem Efeu-Brücke CPU um meinen Benchmark zu kompilieren. Er hat ähnliche Ergebnisse, also scheint es nicht Haswell zu sein. Da zwei Compiler hier seltsame Ergebnisse liefern, scheint es auch kein Compilerfehler zu sein. Wir haben hier keine AMD-CPU, daher konnten wir nur mit Intel testen.

Mehr Wahnsinn, bitte!

Nehmen Sie das erste Beispiel (das mit atol(argv[1])) und setze a static vor der Variable, d.h.

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

Hier sind meine Ergebnisse in g ++:

  • unsigniert 41959360000 0.396728 sek 26.4306 GB / s
  • uint64_t 41959360000 0,509484 sek 20.5811 GB / s

Yay, noch eine Alternative. Wir haben immer noch die schnellen 26 GB / s mit u32, aber wir haben es geschafft u64 zumindest von der 13 GB / s bis zur 20 GB / s Version! Auf dem PC meines Kollegen, der u64 Version wurde noch schneller als die u32 Version, die das schnellste Ergebnis von allen ergibt. Leider funktioniert das 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 geben? u32 und u64?
  • Wie kann ein nicht konstanter durch eine konstante Puffergröße ersetzt werden? weniger optimaler Code?
  • Wie kann die Einfügung der static Stichwort machen die u64 Schleife schneller? Noch schneller als der Originalcode auf dem Computer meines Kollegen!

Ich weiß, dass Optimierung ein schwieriges Gebiet ist, aber ich hätte nie gedacht, dass solche kleinen Änderungen zu einem führen können 100% Unterschied in der Ausführungszeit 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 poppen kann. Die einzige zuverlässige Methode, die ich mir vorstellen kann, besteht darin, die Baugruppe für diesen Fall zu kopieren und die Inline-Montage zu verwenden. Nur so kann ich Compiler loswerden, die bei kleinen Änderungen verrückt werden. Was denken Sie? Gibt es eine andere Möglichkeit, den Code zuverlässig mit der höchsten Leistung zu erhalten?

Die Demontage

Hier ist die Demontage für die verschiedenen Ergebnisse:

26 GB / s Version von g ++ / u32 / nicht-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 / nicht-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 / nicht-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 (26 GB / s) Version auch die längste! Es scheint die einzige Lösung zu sein, die verwendet wird lea. Einige Versionen verwenden jb um zu springen, andere benutzen jne. Aber abgesehen davon scheinen alle Versionen vergleichbar zu sein. Ich sehe nicht, wo eine 100% -Leistungslücke herrühren könnte, aber ich bin nicht so geschickt darin, die Montage zu entschlüsseln. Die langsamste (13 GB / s) Version sieht sogar sehr kurz und gut aus. Kann das jemand erklären?

Gewonnene Erkenntnisse

Egal was die Antwort auf diese Frage sein wird; Das habe ich in wirklich heißen Loops gelernt jeden Detail kann wichtig sein, sogar Details, die keine Verbindung zum Hot-Code haben. Ich habe nie darüber nachgedacht, welcher Typ für eine Schleifenvariable verwendet werden soll, aber wie Sie sehen, kann eine solche geringfügige Änderung ein Problem verursachen 100% Unterschied! Auch der Speichertyp eines Puffers kann einen großen Unterschied machen, wie wir beim Einfügen des staticSchlüsselwort vor der Größenvariable! In der 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.

Interessant ist auch, dass der Leistungsunterschied immer noch so hoch ist, obwohl ich die Schleife bereits viermal abgerollt habe. Selbst wenn Sie ausrollen, können Sie immer noch von großen Leistungsabweichungen getroffen werden. Ziemlich interessant.


1146
2017-08-01 10:33


Ursprung


Antworten:


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

Auf Sandy / Ivy Bridge und Haswell Prozessoren, die Anweisung:

popcnt  src, dest

scheint eine falsche Abhängigkeit vom Zielregister zu haben dest. Obwohl der Befehl nur in ihn schreibt, wartet der Befehl bis dest ist vor der Ausführung bereit.

Diese Abhängigkeit hält nicht nur die 4 popcnts aus einer einzelnen Schleifeniteration. Es kann Loop-Iterationen übertragen, die es dem Prozessor unmöglich machen, verschiedene Schleifeniterationen zu parallelisieren.

Das unsigned gegen uint64_t und andere Verbesserungen beeinflussen das Problem nicht direkt. Sie beeinflussen jedoch den Registerzuordner, der die Register den Variablen zuordnet.

In Ihrem Fall sind die Geschwindigkeiten ein direktes Ergebnis dessen, was an der (falschen) Abhängigkeitskette hängt, abhängig davon, was der Registerzuordner entschieden hat.

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

Der Unterschied zwischen 20 GB / s und 26 GB / s scheint ein geringes Artefakt der indirekten Adressierung zu sein. In beiden Fällen beginnt der Prozessor bei Erreichen dieser Geschwindigkeit andere Engpässe zu treffen.


Um dies zu testen, habe ich die Inline-Assemblierung verwendet, um den Compiler zu umgehen und genau die Assembly zu erhalten, die ich möchte. Ich habe auch das geteilt count Variable, um alle anderen Abhängigkeiten zu durchbrechen, die die Benchmarks stören könnten.

Hier sind die Ergebnisse:

Sandy Bridge Xeon @ 3,5 GHz: (vollständiger Testcode kann am Ende gefunden werden)

  • 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 also mit dem Compiler schief gelaufen?

Es scheint, dass weder GCC noch Visual Studio das wissen popcnt hat eine solche falsche Abhängigkeit. Diese falschen Abhängigkeiten sind jedoch nicht ungewöhnlich. Es kommt nur darauf an, ob der Compiler sich dessen bewusst ist.

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

(Aktualisieren:  Ab Version 4.9.2, GCC ist sich dieser falschen Abhängigkeit bewusst und generiert Code, um es zu kompensieren, wenn Optimierungen aktiviert sind. Wichtige Compiler anderer Hersteller, darunter Clang, MSVC und sogar Intels eigene ICC, sind sich dieses mikroarchitektonischen Erratums noch nicht bewusst und geben keinen Code aus, der dies kompensiert.

Warum hat die CPU so eine falsche Abhängigkeit?

Wir können nur spekulieren, aber es ist wahrscheinlich, dass Intel die gleiche Handhabung für viele Zwei-Operanden-Anweisungen hat. Allgemeine Anweisungen wie add, sub Nimm zwei Operanden, die beide Eingänge sind. Also hat Intel wohl gedrängt popcnt in die gleiche Kategorie, um das Prozessor-Design einfach zu halten.

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


Der vollständige Testcode ist unten 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);
}

Ein ebenso interessanter Benchmark findet sich hier: http://pastebin.com/kbzgL8si
Dieser Benchmark variiert die Anzahl der popcnts, die sich in der (falschen) Abhängigkeitskette befinden.

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

1307
2017-08-01 22:41



Ich habe ein gleichwertiges C-Programm zum Experimentieren programmiert, und ich kann dieses merkwürdige Verhalten bestätigen. Was ist mehr, gcc glaubt an die 64-Bit-Ganzzahl (die wahrscheinlich ein sein sollte size_t trotzdem ...) um besser zu sein, als zu benutzen uint_fast32_t bewirkt, dass gcc eine 64-Bit-Uint verwendet.

Ich habe ein bisschen mit der Versammlung 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, aber solange die innere Popcount-Schleife die Leistung dominiert, ist dies ein guter Anfang .

Ich kopierte dann den inneren Schleifencode von der 32-Bit-Version des Programms, hackte ihn zu 64 Bit, fiedelte mit den Registern, 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.

Meine Schlussfolgerung ist, dass dies eine schlechte Instruktions-Planung durch den Compiler ist, nicht ein tatsächlicher Geschwindigkeits- / Latenz-Vorteil von 32-Bit-Instruktionen.

 (Vorbehalt: Ich habe die Versammlung zerhackt, hätte etwas kaputt machen können, ohne es zu merken. Ich glaube nicht.)


47
2017-08-01 22:55



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

Ich bekomme diese Ergebnisse mit a Mac Pro (Westmere 6-Kerne Xeon 3,33 GHz). Ich habe es mit zusammengestellt clang -O3 -msse4 -lstdc++ a.cpp -o a (-O2 erhält das gleiche Ergebnis).

klingeln 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

klingeln 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. Umkehren Sie die Testreihenfolge, das Ergebnis ist das gleiche, so dass es den Cache-Faktor ausschließt.
  2. Habe den for umgekehrte Aussage: for (uint64_t i=size/8;i>0;i-=4). Dies ergibt das gleiche Ergebnis und beweist, dass die Kompilierung schlau genug ist, die Größe bei jeder Iteration (wie erwartet) nicht um 8 zu teilen.

Hier ist meine wilde Vermutung:

Der Geschwindigkeitsfaktor besteht aus drei Teilen:

  • Code-Cache: uint64_t Version hat eine größere Code-Größe, aber das hat keine Auswirkungen auf meine Xeon-CPU. Dies macht die 64-Bit-Version langsamer.

  • Anweisungen verwendet. Beachten Sie nicht nur die Anzahl der Schleifen, sondern auch den Puffer mit einem 32-Bit- und einem 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 für einen 32-Bit-Offset unmittelbar verwenden können. Dies kann die 32-Bit-Version schneller machen.

  • Anweisungen werden nur bei der 64-Bit-Kompilierung (Prefetch) ausgegeben. Dies macht 64-Bit schneller.

Die drei Faktoren zusammen passen zu den beobachteten scheinbar widersprüchlichen Ergebnissen.


24
2017-08-01 11:04



Ich kann keine verbindliche Antwort geben, aber einen Überblick über eine mögliche Ursache geben. Diese Referenz zeigt ziemlich deutlich, dass für die Anweisungen im Body Ihrer Schleife ein 3: 1-Verhältnis zwischen Latenz und Durchsatz besteht. Es zeigt auch die Auswirkungen von Mehrfachversand. Da es in modernen x86-Prozessoren drei ganzzahlige Einheiten gibt (geben oder nehmen), ist es im Allgemeinen möglich, drei Anweisungen pro Zyklus zu senden.

Zwischen der Peak-Pipeline und der Multiple-Dispatch-Performance und dem Ausfall dieser Mechanismen haben wir einen Faktor von sechs in der Leistung. Es ist ziemlich bekannt, dass die Komplexität des x86-Befehlssatzes es leicht macht, dass ein merkwürdiger Bruch auftritt. Das obige Dokument hat ein großartiges Beispiel:

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

Ich bin persönlich in einen seltsamen Fall geraten, in dem eine heiße Schleife auf einem bestimmten Kern eines Vier-Kern-Chips (AMD, wenn ich mich erinnere) deutlich langsamer lief. Wir haben tatsächlich eine bessere Leistung bei einer Kartenreduzierungsberechnung, indem wir diesen Kern ausschalten.

Hier ist meine Vermutung Behauptung für ganzzahlige Einheiten: dass die popcnt, Schleifenzähler- und Adressberechnungen können alle mit dem 32-Bit breiten Zähler nur knapp mit voller Geschwindigkeit laufen, aber der 64-Bit-Zähler verursacht Konflikte und Pipeline-Blockierungen. Da es nur ungefähr 12 Zyklen insgesamt gibt, möglicherweise 4 Zyklen mit mehrfachem Versand, pro Schleifenkörperausführung, könnte ein einzelner Strömungsabriss die Laufzeit um einen Faktor von 2 vernünftigerweise beeinflussen.

Die durch die Verwendung einer statischen Variable hervorgerufene Änderung, die, wie ich vermute, nur eine geringfügige Neuanordnung von Anweisungen verursacht, ist ein weiterer Hinweis darauf, dass der 32-Bit-Code an einem Wendepunkt für Konflikte ist.

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


10
2017-08-01 20:12



Hast du versucht, vorbeizugehen? -funroll-loops -fprefetch-loop-arrays zum GCC?

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

9
2017-08-04 15:37



Ich habe das mit versucht Visual Studio 2013 Express, mit einem Zeiger anstelle eines Index, der den Prozess ein wenig beschleunigt. Ich vermute, dies liegt daran, dass die Adressierung Offset + Register statt Offset + Register + (Register << 3) ist. 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;
   }

Assemblercode: r10 = bfrptr, r15 = bfrend, rsi = Anzahl, rdi = Puffer, 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

9
2017-08-02 03:48



Haben Sie versucht, den Reduzierungsschritt 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 einige seltsame Aliasing, dass ich nicht sicher bin, ist konform mit den strengen Aliasing-Regeln.


7
2017-08-01 18:33



TL; DR: Verwenden __builtin intrinsics stattdessen.

Ich konnte es machen gcc 4.8.4 (und sogar 4.7.3 auf gcc.godbolt.org) erzeugen hierfür optimalen Code __builtin_popcountllDas verwendet die gleiche Assembly-Anweisung, hat aber diesen Fehler mit falscher Abhängigkeit nicht.

Ich bin mir meines Benchmarking-Codes nicht 100% sicher, aber objdump Ausgabe scheint meine Ansichten zu teilen. Ich benutze ein paar andere Tricks (++i vs i++) um den Compiler für mich die Schleife ausrollen zu lassen movl Anleitung (seltsames Verhalten, muss ich sagen).

Ergebnisse:

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

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

5
2018-05-04 11:14