Cache-freundlicher Code in C++: Was das ist und warum es für die Geschwindigkeit wichtig ist

Ihr Code läuft langsam, obwohl der Algorithmus perfekt ist? Vielleicht ist er nicht "cache-freundlich"

Haben Sie jemals Code in C++ geschrieben, der theoretisch blitzschnell laufen sollte, in der Praxis aber träge ist? Oder haben Sie bemerkt, dass das Durchlaufen eines zweidimensionalen Arrays zeilen- und spaltenweise unterschiedliche Geschwindigkeiten ergibt, obwohl die Komplexität des Algorithmus gleich ist? Wenn ja, sind Sie auf cache-freundlichen (cache-friendly) und das Gegenteil – cache-unfreundlichen Code gestoßen.

Heute analysieren wir, was das auf Hardware-Ebene bedeutet, warum der Cache nicht nur "ein weiterer Speicher" ist, sondern der Schlüssel zur Leistung, und wie man Code schreibt, den der Prozessor "liebt". Ohne komplexe Abstraktionen – nur C++ und verständliche Beispiele.

Warum kann der Prozessor nicht einfach aus dem Arbeitsspeicher lesen?

Die Prozessorgeschwindigkeit hat sich in den letzten Jahrzehnten um das Tausendfache erhöht, die Geschwindigkeit des Arbeitsspeichers (DRAM) jedoch nur um das Zehnfache. Stellen Sie sich einen Formel-1-Fahrer (Prozessor) vor, der jede Sekunde anhalten muss, um Treibstoff (Daten) von einem Lkw zu bekommen, der mit 30 km/h fährt (Arbeitsspeicher). Traurig und langsam.

Die Lösung ist der Prozessor-Cache: ein kleiner, aber sehr schneller Speicher, der direkt in den Chip integriert ist. Er speichert Kopien häufig verwendeter Daten. Wenn der Prozessor Daten benötigt, überprüft er zuerst den Cache (L1 – der schnellste, dann L2, L3). Nur wenn die Daten dort nicht vorhanden sind (Cache-Miss), greift er auf den langsamen Arbeitsspeicher zu.

Hier sind ungefähre Latenzzeiten (in Prozessortakten):

\n
• L1-Cache: ~3-5 Takte
\n
• L2-Cache: ~10-20 Takte
\n
• L3-Cache: ~30-50 Takte
\n
• Arbeitsspeicher: ~100-300 Takte
\n

Der Unterschied zwischen L1 und RAM beträgt das 50- bis 100-fache. Deshalb kann cache-freundlicher Code in C++ um ein Vielfaches schneller sein als eine "unfreundliche" Alternative.

Das Prinzip der Lokalität: Wie der Cache entscheidet, was gespeichert wird

Der Cache kopiert nicht ein einzelnes Byte – er arbeitet in Blöcken (Cache-Lines), normalerweise 64 Bytes. Wenn Sie eine Variable lesen, lädt der Prozessor den gesamten Block, der diese Variable enthält. Dabei setzt er auf zwei Prinzipien:

\n
• Räumliche Lokalität (Spatial locality): Wenn Sie ein Array-Element arr[i] lesen, werden Sie wahrscheinlich bald arr[i+1] benötigen.
\n
• Zeitliche Lokalität (Temporal locality): Wenn Sie Daten jetzt gelesen haben, werden Sie wahrscheinlich in Kürze erneut darauf zugreifen.
\n

Cache-freundlicher Code ist Code, der diese Prinzipien maximal ausnutzt. Sehen wir uns an, wie das in der Praxis aussieht.

Beispiel 1: Durchlaufen eines zweidimensionalen Arrays – der Klassiker

Cache-unfreundlich (schlechter Code)

const int SIZE = 1024;\nint matrix[SIZE][SIZE];\n\n// Spaltenweise Durchlauf (column-major)\nfor (int j = 0; j < SIZE; ++j) {\n    for (int i = 0; i < SIZE; ++i) {\n        matrix[i][j] = i + j;\n    }\n}\n

In C++ werden Arrays im Row-Major-Order (zeilenweise) gespeichert. Das heißt, die Elemente einer Zeile matrix[0][0], matrix[0][1], matrix[0][2]... liegen im Speicher nacheinander. Die äußere Schleife über j (Spalten) zwingt den Prozessor, bei jedem Schritt über die gesamte Zeile zu springen – jeder Zugriff auf matrix[i][j] ist höchstwahrscheinlich ein Cache-Miss. Der Prozessor verbringt Zeit damit, neue Blöcke zu laden, während die vorherigen Daten aus dem Cache verdrängt werden.

Cache-freundlich (guter Code)

// Zeilenweise Durchlauf (row-major)\nfor (int i = 0; i < SIZE; ++i) {\n    for (int j = 0; j < SIZE; ++j) {\n        matrix[i][j] = i + j;\n    }\n}\n

Jetzt gehen wir sequentiell durch den Speicher. Sobald wir den Block mit matrix[0][0] geladen haben, sind die nächsten 15 Elemente (bei 4-Byte-int) bereits im Cache! Dies führt zu einem Geschwindigkeitszuwachs um das 5- bis 10-fache