Warum ein 64-Bit-Zähler in einer Schleife die Leistung von _mm_popcnt_u64 beeinträchtigt

Der berühmte Fehler, der C++-Entwickler bis heute verfolgt

Im Jahr 2013 tauchte auf Stack Overflow eine Frage auf, die Hunderttausende von Aufrufen sammelte und einen wahren Kult unter C++-Optimierern hervorbrachte. Sie lautete ungefähr so: „Ich habe int durch uint64_t im Schleifenzähler ersetzt – und die Leistung ist um das Zehnfache gefallen. Warum?“. Die Antwort lag nicht in Magie, sondern in der Mikroarchitektur von Intel-Prozessoren. Im Jahr 2025 ist dieses Problem nicht verschwunden: Moderne Chips können immer noch über einen scheinbar harmlosen Austausch des Datentyps stolpern.

Heute analysieren wir dieses Paradoxon am Beispiel der Anweisung _mm_popcnt_u64 (Zählen der gesetzten Bits in einem 64-Bit-Wort), zeigen echten Code, der unter dieser Anomalie leidet, und geben klare Empfehlungen, wie man im Jahr 2025 schnellen und vorhersagbaren C++-Code schreibt.

Der Kern des Problems: 32-Bit- vs. 64-Bit-Zähler

Stellen Sie sich eine einfache Schleife vor, die die Anzahl der gesetzten Bits (popcount) in einem Array von 64-Bit-Ganzzahlen summiert. Wir verwenden das Intrinsic _mm_popcnt_u64 aus dem SSE4.2-Satz. Hier sind zwei Code-Varianten – die erste mit einem 32-Bit-Zähler, die zweite mit einem 64-Bit-Zähler:

#include <cstdint>\n#include <vector>\n#include <nmmintrin.h> // für _mm_popcnt_u64\n\n// Variante 1: 32-Bit-Zähler (schnell)\nuint64_t popcnt_32bit(const std::vector<uint64_t>& data) {\n    uint64_t result = 0;\n    for (int i = 0; i < data.size(); ++i) {   // int — 32 Bit\n        result += _mm_popcnt_u64(data[i]);\n    }\n    return result;\n}\n\n// Variante 2: 64-Bit-Zähler (langsam)\nuint64_t popcnt_64bit(const std::vector<uint64_t>& data) {\n    uint64_t result = 0;\n    for (uint64_t i = 0; i < data.size(); ++i) { // uint64_t — 64 Bit\n        result += _mm_popcnt_u64(data[i]);\n    }\n    return result;\n}\n

Wenn man die Geschwindigkeit auf einem Intel-Prozessor misst (z. B. Core i7-13700K oder sogar einem älteren Haswell), ist der Unterschied schockierend: Die zweite Variante kann 3- bis 10-mal langsamer sein. Auf einem AMD Ryzen tritt diese Anomalie nicht auf – dort arbeiten beide Varianten gleich schnell.

Warum passiert das? Die Wurzel des Übels – die falsche Abhängigkeit

Die POPCNT-Anweisung auf Intel-Prozessoren (bis hin zu den modernsten) hat eine falsche Abhängigkeit (false dependency) vom Zielregister. Formal überschreibt POPCNT das Ausgaberegister vollständig, aber mikroarchitektonisch verhält sich der Prozessor so, als ob er das alte Ergebnis liest, bevor er schreibt. Dies ist ein Fehler (oder eine Besonderheit) in der Implementierung von Intel.

Betrachten wir nun die Schleife mit dem 64-Bit-Zähler i. Der Compiler ist gezwungen, dasselbe Register (z. B. rax) sowohl für den Zähler als auch für die Zwischenergebnisse von POPCNT zu verwenden. Jede Iteration erzeugt eine Abhängigkeitskette: Die nächste POPCNT kann nicht beginnen, bevor die vorherige abgeschlossen ist, weil der Prozessor „denkt“, dass sie das alte Ergebnis benötigt. Dies tötet die Pipeline.

Mit einem 32-Bit-Zähler verwendet der Compiler unterschiedliche Register (z. B. ecx für den Zähler und rax zum Akkumulieren des Ergebnisses), und die falsche Abhängigkeit tritt nicht auf – POPCNT-Anweisungen werden parallel ausgeführt.

Detaillierte Analyse in Assembler

Um sich zu vergewissern, schauen wir uns an, wozu jede Variante kompiliert wird (GCC 13, Flags -O3 -march=native):

32-Bit-Zähler (schnell):

.L3:\n    popcnt rcx, QWORD PTR [rdx]   ; popcnt in rcx (unabhängiges Register)\n    add    rax, rcx                ; zum Akkumulator addieren\n    add    rdx, 8                  ; Zeiger verschieben\n    cmp    rdi, rdx                ; Vergleich\n    jne    .L3\n

64-Bit-Zähler (langsam):

.L7:\n    popcnt rax, QWORD PTR [rdx]   ; popcnt in rax — dasselbe wie im Akkumulator