DE
RU
EN
ES
ZH
FR
PT
AR
HI
Einleitung: Die magische Zahl 8192 und Ihr sich verlangsamender Code
\nHaben Sie jemals bemerkt, dass Ihr C++-Code, der mit 1000 oder 10000 Elementen einwandfrei funktionierte, plötzlich bei genau 8192 zu verlangsamen beginnt? Nein, das ist kein Compiler-Fehler und kein Fluch alter Programmierer. Es ist ein klassisches Beispiel dafür, wie die Prozessorarchitektur Ihren schnellen Algorithmus in eine lahme Schnecke verwandeln kann.
\nDiese Geschichte begann mit einer legendären Frage auf Stack Overflow: "Why is my program slow when looping over exactly 8192 elements?", die tausende Aufrufe sammelte und zu einem echten Meme in der Welt des High Performance Computing wurde. Heute, im Jahr 2025, wo Prozessoren noch komplexer geworden sind, ist das Verständnis dieses Problems nicht nur eine lustige Tatsache, sondern eine echte Fähigkeit, die einen Junior-Entwickler von einem Ingenieur unterscheidet, der schnellen Code schreibt.
\nIn diesem Artikel werden wir analysieren, was unter der Haube Ihres Prozessors passiert, warum die Größe 8192 (und ihre Vielfachen) eine "rote Zone" darstellen und wie man Code schreibt, der bei beliebigen Daten konstant schnell ist. Los geht's!
\n\n1. Anatomie des Problems: Cache-Fehler und Assoziativität
\nUm die Wurzel des Übels zu verstehen, müssen wir einen Blick auf die Architektur moderner Prozessoren werfen. Die langsamste Operation ist der Zugriff auf den Arbeitsspeicher (RAM). Um den Zugriff zu beschleunigen, verwendet der Prozessor einen Cache – einen kleinen, aber sehr schnellen Speicher, der direkt auf dem Chip sitzt.
\n1.1. Wie der Cache funktioniert (sehr kurz)
\n- \n
- L1-Cache: Der schnellste und kleinste (~32 KB pro Kern). \n
- L2-Cache: Etwas langsamer, aber größer (~256-512 KB). \n
- L3-Cache: Gemeinsam für alle Kerne, am größten (mehrere MB). \n
Daten werden nicht Byte für Byte in den Cache geladen, sondern in Blöcken – sogenannten Cache-Lines (normalerweise 64 Bytes). Wenn der Prozessor Daten anfordert, die nicht im Cache sind, kommt es zu einem Cache-Fehler (Cache Miss), und er muss auf das Laden aus dem RAM warten. Dies kann hunderte Taktzyklen dauern.
\n\n1.2. Der Fluch der 8192: Cache-Assoziativität
\nDer Cache ist nicht einfach ein großer Korb. Er ist in Sets organisiert. Jede Speicheradresse kann nur in einem dieser Sets abgelegt werden. Dies nennt man einen set-associative cache.
\nStellen Sie sich einen Parkplatz vor, auf dem die Plätze in Reihen gruppiert sind. Ihr Auto (die Speicheradresse) kann nur in einer bestimmten Reihe (dem Set) geparkt werden. Wenn alle Plätze in dieser Reihe belegt sind, müssen Sie eines der Autos entfernen (die Cache-Line verdrängen), um Platz zu schaffen.
\nBei vielen modernen Prozessoren sind die L1- und L2-Caches 8-fach set-associative. Das bedeutet, dass in jedem Set 8 Cache-Lines Platz haben.
\nUnd jetzt der entscheidende Punkt: Die Größe einer Cache-Line beträgt 64 Bytes (512 Bit). Wenn Sie mit einem Array von int (4 Bytes) arbeiten, enthält eine Cache-Line 16 Elemente.
Wenn Sie ein Array mit einer Schrittweite durchlaufen, die einer Zweierpotenz entspricht, können alle Elemente, auf die Sie zugreifen, auf dasselbe Cache-Set abgebildet werden. Wenn Sie beispielsweise jedes 16. Element nehmen, konkurrieren alle um dieselben 8 Slots im Set. Wenn es mehr Elemente als Slots gibt (z. B. wenn Sie ein Array mit 8192 Elementen durchlaufen, die auf ein Set abgebildet werden), beginnt der Cache ständig, alte Daten zu "verwerfen" und neue zu laden. Dies nennt man Cache Thrashing.
\n8192 ist 2^13. Bei einer bestimmten Anordnung der Daten im Speicher trifft genau diese Anzahl von Elementen ideal auf die Assoziativitätsbeschränkungen eines typischen L1-Caches (32 KB / 64 Bytes = 512 Sets, und 8192 / 16 = 512, was perfekt auf jedes Set passt).
\n\n2. Demonstration des Problems in C++
\nSchauen wir uns den Code an, der dieses Problem reproduziert. Wir messen die Zeit für das Durchlaufen eines zweidimensionalen Arrays mit verschiedenen Schrittweiten.
\n\n#include <iostream>\n#include <vector>\n#include <chrono>\n\nconst int SIZE 
