Speicherlokalität

Speicherlokalität bezeichnet in der Informatik die Tendenz eines Programms, auf zusammenhängende Speicherseiten zuzugreifen und wiederholte Zugriffe auf denselben Speicherbereich zu tätigen. Sie beeinflusst maßgeblich, wie effizient ein Programm mit dem hierarchischen Speichersystem eines Computers interagiert.

Es werden üblicherweise zwei Formen unterschieden: temporale Lokalität und räumliche Lokalität. Temporale Lokalität bedeutet, dass kürzlich gelesene oder geschriebene Speicheradressen bald wieder verwendet werden. Räumliche Lokalität bedeutet, dass nahe Adressen in kurzer Folge ebenfalls adressiert werden. Typische Beispiele sind das wiederholte Durchlaufen einer Schleife über ein Array (temporale Lokalität) oder das sequenzielle Lesen benachbarter Array-Elemente (räumliche Lokalität).

Die Speicherlokalität hängt eng mit der CPU-Cache-Hierarchie zusammen. Moderne Prozessoren verwenden mehrere Cache-Ebenen (L1, L2, L3), um häufig genutzte Daten schnell bereitzustellen. Günstige Zugriffsmuster nutzen Caches effektiv; unstrukturierte oder zufällige Zugriffe erhöhen Cache-Misses und verlangsamen das Programm. Das Speicherlayout von Datenstrukturen beeinflusst die Lokalität ebenso wie der Zugriffsstil. So kann die Wahl zwischen Array-of-Structures und Structure-of-Arrays die Ausnutzung räumlicher Lokalität beeinflussen.

Auswirkungen auf Leistung und Energieverbrauch sind zentral. Lokalisierte Zugriffe führen zu häufigeren Cache-Hits, geringeren Latenzen und höherer Bandbreite, während schlechte Lokalität zu Cache-Misses, längeren Wartezeiten und höherem Energieverbrauch führt.

Praxisnahe Optimierungen zielen darauf ab, Lokalität zu verbessern: sequenzielle oder blockweise Verarbeitung, Loop-Optimierung, Datenstrukturen an Cache-Größen anpassen, Daten zusammenhängend speichern und möglichst wenige Sprünge zwischen Speicherbereichen erzeugen. Oft lohnt sich der Wechsel von AoS zu SoA oder entsprechende Blockierungsstrategien, um räumliche Lokalität zu erhöhen.