Warum das Addieren von Arrays in zwei Schleifen schneller ist als in einer: Analyse von C++-Fehlern

Warum das Addieren von Arrays in zwei Schleifen schneller ist als in einer? Analyse eines legendären C++-Fehlers

Haben Sie jemals Code geschrieben, der intuitiv richtig schien, aber langsam lief? Und dann, durch zufälliges Aufteilen einer Schleife in zwei, eine 2- bis 3-fache Beschleunigung erzielt? Ein bekanntes Problem. Auf Stack Overflow gibt es eine legendäre Frage, die tausende Aufrufe und hunderte Kommentare gesammelt hat: „Why are elementwise additions much faster in separate loops than in a combined loop?“. Heute analysieren wir dieses Phänomen anschaulich, mit C++-Codebeispielen und ohne komplizierte Theorien.

Das ist keine Magie. Es sind Cache-Misses und die Art und Weise, wie der Prozessor tatsächlich auf den Speicher zugreift. Wenn Sie in C++ programmieren und möchten, dass Ihr Code fliegt – lesen Sie aufmerksam. Am Ende des Artikels gibt es konkrete Handlungsempfehlungen, die Sie sofort anwenden können.

Das Kernproblem: Zwei Schleifen vs. eine

Stellen Sie sich vor, wir haben zwei große Arrays a und b und möchten eine elementweise Addition und dann eine Multiplikation jedes Elements durchführen. Die Intuition sagt: „Lass uns eine Schleife machen, um den Prozessor nicht hin und her zu schicken!“.

So sieht die kombinierte Schleife aus:

const int N = 1000000;\nfloat a[N], b[N];\n\n// Eine Schleife – alles auf einmal\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];  // Addition\n    a[i] = a[i] * 2.0f;  // Multiplikation\n}

Und hier die zwei separaten Schleifen:

// Erste Schleife – nur Addition\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];\n}\n\n// Zweite Schleife – nur Multiplikation\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] * 2.0f;\n}

Es ist logisch anzunehmen, dass die erste Variante schneller ist: weniger Overhead für die Schleifenorganisation. In der Praxis ist es jedoch umgekehrt – die zweite Variante ist oft 2- bis 3-mal schneller. Warum? Willkommen in der Welt der Cache-Hierarchie.

Cache-Misses: Der Hauptfeind der Performance

Moderne Prozessoren greifen nicht jedes Mal direkt auf den Arbeitsspeicher zu. Sie verwenden einen Cache – einen schnellen Speicher, der sich direkt auf dem Chip befindet. Der Cache hat mehrere Ebenen (L1, L2, L3), und jede weitere Ebene ist langsamer, aber größer.

Wenn Ihr Code Daten liest oder schreibt, lädt der Prozessor einen ganzen Block (Cache Line) in den Cache – normalerweise 64 Bytes. Wenn die nächste Anfrage in denselben Block fällt, ist es ein Hit (Treffer). Wenn nicht – ein Miss (Fehlschlag), und der Prozessor muss auf die Daten aus dem langsamen RAM warten. Ein einziger Miss kann hunderte Taktzyklen kosten.

Kommen wir zurück zu unserem Beispiel. In der kombinierten Schleife greifen wir in jeder Iteration zweimal auf a[i] und b[i] zu: zuerst zum Lesen, dann zum Schreiben. Während wir mit a[0] und b[0] arbeiten, lädt der Cache deren Cache Lines. Aber in der nächsten Iteration gehen wir zu a[1] und b[1] – ein Miss ist möglich, wenn die Daten in verschiedenen Cache Lines liegen. Infolgedessen „zerren“ wir ständig am Speicher und zwingen den Cache, sich neu zu laden.

In den zwei separaten Schleifen ist das anders. Die erste Schleife liest sequenziell a[i] und b[i] und schreibt das Ergebnis zurück. Die Daten verlaufen linear – der Cache ist vorhersagbar und arbeitet perfekt (räumliche Lokalität). Die zweite Schleife durchläuft erneut dasselbe Array a – die Daten sind bereits heiß im L1-Cache. Es gibt praktisch keine Misses.

Die häufigsten Fehler, die die Performance töten

Fehler Nr. 1 – Mischen von Operationen mit verschiedenen Arrays in einer Schleife. Wenn Sie die Logik in zwei Durchläufe aufteilen können (insbesondere bei großen Datenmengen) – tun Sie es. Der Cache wird es Ihnen danken.

Fehler Nr. 2 – Ignorieren der Cache-Line-Größe. 64 Bytes entsprechen etwa 16 float oder 8 double. Wenn Ihre Arrays seltsame Schrittweiten haben oder Sie nicht sequenziell über Indizes springen, haben Sie garantiert Cache-Misses.

Fehler Nr. 3