Warum ein gutes Datenlayout essentiell ist um das Maximum aus einem Prozessor zu holen

Wenn es um die Performance-Optimierung von Anwendungen geht, die zu langsam laufen, stört mich oft die Ignoranz vieler Entwickler gegenüber der Bedeutung von Datenlokalität. Auch wenn die Auswahl eines Algorithmus aufgrund seiner asymptotischen Laufzeit sicherlich oft das wichtigste Kriterium ist, darf die Arbeitsweise moderner Computer nicht außer Acht gelassen werden. Obwohl die Geschwindigkeit von Prozessoren und Speichern in den letzten Jahren stark zugenommen hat, ist die Geschwindigkeit des Speichers nicht im gleichen Maße gestiegen. Die Geschwindigkeitslücke zwischen CPUs und Hauptspeicher ist enorm. Eine moderne CPU kann Hunderte von einfachen Rechenoperationen in der Zeit ausführen, die für einen einzigen Zugriff auf den Hauptspeicher benötigt wird. Selbst bei Berechnungen, die traditionell als langsam gelten, wie Quadratwurzeln oder Modulo-Operationen, sind CPUs im Vergleich zu einem Speicherzugriff überraschend schnell.

Um den Zugriff auf den Hauptspeicher zu minimieren, verwenden alle Anwendungs- und Serverprozessoren, die in den letzten drei Jahrzehnten hergestellt wurden, Caches. Diese bestehen aus einem oder mehreren kleinen, aber extrem schnellen Speichern, die in Einheiten, so genannten Lines, organisiert sind und Datenblöcke speichern, auf die kürzlich zugegriffen wurde. Bei einem Cache-Miss, d.h. wenn die benötigten Daten nicht im Cache vorhanden sind, werden diese geladen und ersetzen ggf. eine Cacheline, die längere Zeit nicht genutzt wurde.

Für eine gute Performance ist es wichtig, Datenzugriffe sowohl zeitlich als auch räumlich lokal zu organisieren, um die Wahrscheinlichkeit zu erhöhen, dass die benötigten Daten bereits im Cache vorhanden sind. Dies wird am besten erreicht, indem die Daten kompakt gehalten und nach Nutzungszeitpunkt oder -phase strukturiert oder sortiert werden. Die Programmiersprache kann hier mehr oder weniger Flexibilität bieten. 
In Systemsprachen wie C oder C++ hat man die größte Flexibilität, das optimale Speicherlayout zu wählen, allerdings überlässt der Compiler hier die meiste Verantwortung dem Entwickler. Beispielsweise folgt die Anordnung der Attribute einer Struktur im Speicher genau der vom Entwickler festgelegten Reihenfolge, wobei der Compiler Padding-Bytes einfügt, um die Ausrichtungsregeln der Architektur einzuhalten. Eine ungünstige Anordnung kann schnell zu einer Verdoppelung des Speicherbedarfs und einer schlechteren Cache-Nutzung führen. 

Rust ordnet Attribute standardmäßig automatisch um, bietet aber optional die Möglichkeit, das aus C bekannte Verhalten zu nutzen. Darüber hinaus besteht in diesen Sprachen die Möglichkeit, die Anordnung von Datenstrukturen durch eigene Speicherallokatoren sehr kompakt und an bestimmte Zugriffsmuster angepasst zu gestalten.

In höheren Programmiersprachen hängt die optimale Ausrichtung von Datenstrukturen stark vom verwendeten Compiler/Interpreter und dessen Laufzeitumgebung ab. Die Verwendung von "geboxten" Typen oder generell eine starke Heap-Lastigkeit ist zwar nicht optimal, kann aber in bestimmten Situationen durchaus optimiert werden. Auch die Verwendung von generativen Garbage-Collectors mit anschließendem verdichten hilft, Daten lokal zu halten. Dynamische Typen können ebenfalls problematisch sein, aber auch hier gibt es oft Optimierungsmöglichkeiten. Beispielsweise halten aktuelle JavaScript-Engines Objekte mit unveränderlichen Attributen mithilfe von Hidden-Classes erstaunlich kompakt im Speicher. 

Unabhängig von der Sprache können aber die gewählten Datenstrukturen einen erheblichen Einfluss auf die Cache-Lokalität haben, wobei einfache Arrays auf moderner Hardware oft besser sind als komplexere, im Speicher verstreute Strukturen. Für die räumliche und zeitliche Lokalität kann es auch vorteilhaft sein, Arrays von großen Objekten oder Strukturen (AoS) auf der Basis von Zugriffsmustern in mehrere Arrays von kleineren Teilobjekten aufzuteilen (SoA). In JavaScript kann die Implementierung von SoA mit typisierten Arrays besonders effizient sein.

Frühzeitige Überlegungen zu Datenstrukturen und Zugriffsmustern sind entscheidend für eine gute Performance und sollten in Datenintensiven Programmen nicht als Mikrooptimierung oder "Premature Optimization" abgetan werden.

Hennessy, John L.; Patterson, David A.