Dieselbe Summe, aber viel langsamer
Ein Versandhändler summiert jede Nacht eine große Tabelle mit Bestellungen. Eine Kollegin tauscht die beiden Schleifen, damit das Programm die Spalten hinunter statt die Zeilen entlang läuft.
Das Ergebnis stimmt auf den Cent. Der Bericht dauert jetzt aber ein Mehrfaches. An der Arbeit hat sich nichts geändert, nur die Reihenfolge. Der Grund ist der Cache.
Am Ende dieser Lektion
Notiz
Ich kann erklären, warum ein Cache den Speicher schnell macht.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Speicherhierarchie | Speicher, geordnet von klein und schnell bis groß und langsam | |
| Cache | ein kleiner, schneller Speicher mit Kopien kürzlich benutzter Daten | |
| Cachezeile | der Block von Bytes, den ein Cache auf einmal kopiert | 64 Bytes |
| Treffer | die gesuchten Daten liegen schon im Cache | |
| Fehlzugriff | die Daten müssen aus langsamerem Speicher geholt werden | |
| Lokalität | Programme benutzen Daten oft wieder, und Daten, die daneben liegen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Speicher gibt es in Schichten
Ein Prozessor schafft eine Addition in deutlich weniger als einer Nanosekunde. Ein Zugriff auf den Hauptspeicher dauert etwa hundertmal so lange.
Deshalb haben Computer eine Speicherhierarchie. Nah am Prozessor sitzen kleine, schnelle Caches: L1, dann L2, oft auch L3. Dahinter liegt der Hauptspeicher und dahinter die SSD. Jede Schicht ist größer und langsamer als die davor.
Beispiel: ein üblicher Laptop
| Schicht | Übliche Größe | Grobe Lesezeit |
|---|---|---|
| Register | 32 zu je 8 Bytes | Unter 1 Nanosekunde |
| L1-Cache | 32 bis 64 KB | Etwa 1 Nanosekunde |
| L2-Cache | Hunderte KB bis wenige MB | Einige Nanosekunden |
| L3-Cache | Einige MB bis einige zehn MB | 10 bis 20 Nanosekunden |
| Hauptspeicher | Einige GB | Etwa 100 Nanosekunden |
| SSD | Hunderte GB | Zehntausende Nanosekunden |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
In den Architektur-Ordner wechseln
cd ~/archHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Wie groß ist hier eine Cachezeile?
getconf LEVEL1_DCACHE_LINESIZEHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein Fehlzugriff holt eine ganze Zeile
Ein Cache kopiert nie nur ein Byte. Bei einem Fehlzugriff kopiert er eine ganze Cachezeile aus der Schicht darunter, meist 64 Bytes.
Das lohnt sich wegen der Lokalität. Ein Programm liest bald Daten, die neben den gerade gelesenen liegen: räumliche Lokalität. Es liest auch dieselben Daten wieder: zeitliche Lokalität. In beiden Fällen ist der nächste Zugriff ein Treffer.
Warum Zeile für Zeile in loop.c gewinnt
loop.c hält eine Tabelle mit 4096 Zeilen zu je 4096 ints. Ein int hat 4 Bytes. Eine Tabellenzeile hat also 16384 Bytes, und eine Cachezeile von 64 Bytes fasst 16 Zahlen.
Zeile für Zeile holt ein Fehlzugriff die nächsten 16 Zahlen, also sind 15 von 16 Zugriffen Treffer. Spalte für Spalte liegt jeder Zugriff eine ganze Tabellenzeile weiter, in einer anderen Cachezeile. Kommt die Schleife zurück, ist diese Cachezeile schon verdrängt.
Bytes je Zeile, Zahlen je Cachezeile, MB
python3 -c "print(4096 * 4, 64 // 4, 4096 * 4096 * 4 // 1048576)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Das Programm loop des Labs bauen
gcc -O2 -o loop loop.cHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Beide Reihenfolgen messen
./loopHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele glauben, die langsamere Schleife müsse mehr arbeiten. Das tut sie nicht: Beide addieren dieselben 16777216 Zahlen und drucken dieselbe Summe. Anders ist nur, wie oft der Prozessor auf den Speicher wartet. Wenn Code langsam ist, zählen Sie neben den Schritten auch die Fehlzugriffe.
Wohin ein Block im direkt abgebildeten Cache kommt
In einem direkt abgebildeten Cache hat jede Adresse genau eine Cachezeile, in die sie darf. Teilen Sie die Adresse in drei Teile.
Der Offset ist die Adresse modulo Zeilengröße: welches Byte in der Zeile. Geteilt durch die Zeilengröße ergibt sie die Blocknummer. Der Index ist die Blocknummer modulo Anzahl der Zeilen: welche Zeile. Der Rest ist das Tag: welcher Block gerade in der Zeile liegt.
Beispiel: 4 Zeilen zu 16 Bytes
| Adresse | Block | Index | Tag | Ergebnis |
|---|---|---|---|---|
| 8 | 0 | 0 | 0 | Fehlzugriff: Zeile 0 leer |
| 12 | 0 | 0 | 0 | Treffer |
| 40 | 2 | 2 | 0 | Fehlzugriff: Zeile 2 leer |
| 72 | 4 | 0 | 1 | Fehlzugriff: verdrängt Block 0 |
| 8 | 0 | 0 | 0 | Fehlzugriff: Block 0 wurde verdrängt |
| 44 | 2 | 2 | 0 | Treffer |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
0x2f48 für 4 Zeilen zu 32 Bytes zerlegen
python3 -c "print(0x2f48 % 32, 0x2f48 // 32 % 4, 0x2f48 // 128)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend: eine kleinere Tabelle
Machen Sie eine Kopie von loop.c mit einem Viertel der Tabelle: sed 's/4096/2048/' loop.c > viertel.c. Bauen Sie sie mit gcc -O2 -o viertel viertel.c und starten Sie ./viertel einige Male.
Sagen Sie die Summe vorher voraus. Vergleichen Sie dann den Abstand zwischen beiden Reihenfolgen mit dem bei ./loop. Erklären Sie, was Sie sehen, mit Ihrem Simulator.