Speicherhierarchie

Die Pyramide

Stell dir vor, du arbeitest an einem Bericht. Was du gerade brauchst, liegt auf dem Schreibtisch – wenig Platz, aber sofort greifbar. Das Regal hinter dir fasst mehr, kostet aber eine Drehung. Die Bibliothek im Haus noch mehr, kostet aber einen Gang. Und das Archiv in einer anderen Stadt hat alles – aber eine Anfrage dauert Tage. Genau so ist der Speicher eines Computers organisiert. Klick auf eine Stufe:

Warum baut man nicht einfach alles so schnell wie den L1-Cache? Zwei Gründe:

• Technik: Caches bestehen aus SRAM – sechs Transistoren pro Bit, schnell, aber groß und teuer. Arbeitsspeicher ist DRAM – ein Transistor und ein winziger Kondensator pro Bit, viel dichter und billiger, aber langsamer, und er muss ständig aufgefrischt werden, weil die Ladung verrinnt. Eine SSD speichert in Flash-Zellen, die auch ohne Strom ihren Zustand halten.
• Physik: Je größer ein Speicher, desto länger die Wege. Bei 4 GHz legt ein elektrisches Signal in einem Takt nur wenige Zentimeter zurück. Der L1-Cache sitzt deshalb direkt neben dem Rechenwerk, der Arbeitsspeicher auf einem eigenen Riegel, Zentimeter entfernt.

Lokalität: warum Caches überhaupt funktionieren

Ein Cache mit 48 KB kann unmöglich die Daten eines Programms mit Gigabytes halten. Dass er trotzdem in den meisten Fällen trifft – oft in weit über 90 Prozent der Zugriffe –, liegt an zwei Eigenschaften fast aller Programme:

Dazu kommt der Prefetcher: Erkennt der Prozessor ein Muster – etwa, dass ein Programm Adresse für Adresse vorwärts liest –, lädt er die nächsten Cache-Lines schon, bevor sie verlangt werden. Bei einem Array funktioniert das hervorragend. Bei einer verketteten Liste nicht: Wo der nächste Knoten liegt, steht erst im aktuellen Knoten.

Alle vier Muster lesen dieselben 64 Werte, die Rechenarbeit ist identisch. Trotzdem liegen zwischen dem besten und dem schlechtesten Muster Welten. Das ist die wichtigste Lektion dieser Seite: Die Reihenfolge der Speicherzugriffe kann wichtiger sein als die Zahl der Rechenschritte.

Wie Java-Daten im Speicher liegen

In Java entscheidet man selten bewusst über Speicherlayout – aber man entscheidet es trotzdem, mit jeder Wahl einer Datenstruktur. Dieselben vier Zahlen, dreimal gespeichert:

Caches und mehrere Kerne

Jeder Kern hat eigene L1- und L2-Caches. Was passiert, wenn zwei Kerne dieselbe Speicherstelle in ihren Caches haben und einer schreibt? Ein Kohärenzprotokoll sorgt dafür, dass die Kopie des anderen ungültig wird – bekannt ist etwa MESI, benannt nach den Zuständen einer Line: Modified, Exclusive, Shared, Invalid. Das kostet Zeit, und es arbeitet auf ganzen Cache-Lines.

Daraus entsteht eine berüchtigte Bremse, False Sharing: Zwei Threads schreiben auf zwei verschiedene Variablen, die zufällig in derselben Cache-Line liegen. Logisch teilen sie nichts, physisch reißen sie sich ständig gegenseitig die Line weg. Die JDK-Klasse LongAdder aus dem Thread-Eintrag vermeidet genau das: Sie verteilt ihre Teilzähler mit Abstand auf verschiedene Cache-Lines.

class Zaehler {
    volatile long a;   // Thread 1 schreibt nur a
    volatile long b;   // Thread 2 schreibt nur b
}   // a und b liegen 8 Byte auseinander – dieselbe Cache-Line, ständiges Hin und Her

Die unteren Stufen: RAM, SSD, Netzwerk

Unterhalb der Caches gilt dasselbe Prinzip, nur mit größeren Blöcken und längeren Wartezeiten. Das Betriebssystem verwaltet den Arbeitsspeicher in Seiten von meist 4 KB und benutzt freien RAM als Zwischenspeicher für Dateien. Eine SSD liest ebenfalls in Blöcken; zusammenhängende Daten am Stück zu lesen, ist auch hier viel schneller als verstreute.

Und die Hierarchie endet nicht am Gehäuse. Eine Datenbank hält häufig benutzte Seiten im RAM, ein Server legt Ergebnisse in Redis ab, ein CDN hält Bilder in der Nähe des Nutzers, der Browser speichert Dateien lokal. Überall dieselbe Idee: Halte das Benutzte nah. Und überall dasselbe Problem: Wann ist die Kopie veraltet? Nicht umsonst gilt Cache-Invalidierung als eines der schwersten Probleme der Informatik.

Für Entwickler übersetzt

int[][] m = new int[4096][4096];
long s = 0;

for (int r = 0; r < 4096; r++)          // zeilenweise: Nachbarn im Speicher
    for (int c = 0; c < 4096; c++) s += m[r][c];

for (int c = 0; c < 4096; c++)          // spaltenweise: jeder Zugriff eine andere Zeile
    for (int r = 0; r < 4096; r++) s += m[r][c];

// Gleiche Rechenarbeit, oft ein Vielfaches an Laufzeit.
// Messen mit JMH – nicht mit System.nanoTime() um eine Schleife.

Wer genau wissen will, wie ein Objekt im Speicher liegt, kann es mit dem Werkzeug JOL (Java Object Layout) aus dem OpenJDK-Projekt ausgeben lassen. Und das langfristige Ziel von Projekt Valhalla ist, dass eigene Klassen so dicht im Array liegen können wie heute nur int und double.

Häufige Irrtümer

Verwandte Begriffe