Cache-Optimierung: Zeitliche und Räumliche Lokalität

Wenn man schnelle Programme schreiben möchte, so muss man auch die Funktionsweise der Hardware beachten, wie ich im Folgenden zeige werde.

Nehmen wir an, es muss ein zweidimensionales Array vollständig durchlaufen werden. Dieser Fall trifft beispielsweise oft auf, wenn man Bildmanipulationen durchführt. Dazu ein minimales Beispiel.

	// ein Array dynamisch erstellen
	size_t width = 10000;
	size_t height = 10000;
	int* arr = new int[height*width];

	// Array zeilenweise durchlaufen
	for(size_t i = 0; i < height; i++)
		for(size_t j = 0; j < width; j++)
			arr[i*width+j] = i*j;

	// Array spaltenweise durchlaufen
	for(size_t j = 0; j < width; j++)
		for(size_t i = 0; i < height; i++)	
			arr[i*width+j] = i*j;

Es wird ein zweidimensionales Integer-Array erstellt und auf zwei unterschiedliche Weisen durchlaufen. In jedem Durchgang wird ein Wert in das Array geschrieben.

Misst man die Zeit, die die beiden Schleifen zum durchlaufen des Arrays brauchen, so bekommt man ein zunächst überraschendes Bild.

Auf der X-Achse ist die Größe des Arrays aufgetragen und auf der Y-Achse die durchschnittliche Zeit (in Millisekunden, was an dieser Stelle aber unwichtig ist) aus 5 Durchläufen, die für einen Array-Durchlauf benötigt wurde ¹.

Offensichtlich benötigt der Code weniger Zeit, wenn das Array zeilenweise durchlaufen wird. Wie groß dieser Unterschied ist, sieht man besser, wenn man die beiden Zeiten in Verhältnis setzt.

Nach der Grafik zu urteilen beträgt der Geschwindigkeitsfaktor etwa 13 ². Ein beachtlicher Wert, wenn man bedenkt, dass es sich nur um eine einzige Schleife handelt.

Das gleiche bzw. sogar etwas bessere Bild bekommt man auch, wenn man die Lesezeiten misst.

Der Grund für die Geschwindigkeitsunterschiede ist die Cache-Verwaltung des Prozessors. Ein Computer hat mehrere Speicher, die unterschiedlich schnell und unterschiedlich groß sind, wie in der nachfolgenden Abbildung schematisch dargestellt ist.

L1- Cache ist der kleinste Speicher, er liegt am nächsten zum Prozessor und der Zugriff darauf geschieht am schnellsten ³. Andere Speicher sind größer, aber dafür langsamer.

Muss der Prozessor auf eine Speicheradresse zugreifen, dann wird gleichzeitig in allen Speicherstellen danach gesucht. Da der Zugriff auf L1-Cache am schnellsten geschieht, weiß man zuerst ob die gesuchten Daten dort liegen oder nicht. Wenn nein (man nennt es Cache-Miss), so muss der Prozessor warten bis die Ergebnisse von L2 vorliegen. Es kann sein, dass die Daten auch nicht in L2 liegen, sondern in L3, in Arbeitsspeicher oder sogar auf der Festplatte. In dieser Wartezeit ruht der Prozessor und somit die ganze Berechnung.

Werden die Daten gefunden (Cache-Hit), so werden sie nicht nur an den Prozessor weiter geleitet, sondern auch gleichzeitig in den schnelleren Speicher abgelegt (in Cache geholt). Da schnellere Speicher klein sind, müssen zwangsläufig die alten Inhalte überschrieben werden. Welche Daten man dabei überschreibt ist Prozessorabhängig, aber oft werden die Daten überschrieben, deren Benutzung (Schreibe/Lesen) am weitesten in der Zeit zurück liegt (LRU – Least-recently used). Beim Cache füllen wird nicht nur der Inhalt der gesuchten Speicheradresse kopiert, sondern auch die nachfolgenden Adressen. Wie viele es genau sind, hängt von der Breite des Caches ab.

Darauf ergeben sich zwei wichtige Schlussfolgerungen:

1. Der erneute Zugriff auf eine Speicheradresse wird auf jeden Fall schnell sein, da die Daten nach dem ersten Zugriff im Cache liegen.
2. Der Zugriff auf die nachfolgenden Adressen wird schnell sein (beschränkt auf die Cache-Breite), da beim Cache-Vorgang die nachfolgenden Elemente ebenfalls in den Cache abgelegt wurden.

Diese Schlussfolgerungen erfüllen die Prinzipien der zeitliche und räumliche Lokalität, die aus den statistischen Überlegungen zum Ablauf eines Computerprogramms hervorgehen.

• Zeitliche Lokalität: Nach einem Zugriff auf eine Adresse wird wahrscheinlich erneut darauf zugegriffen.
• Räumliche Lokalität: Nach einem Zugriff auf eine Adresse wird wahrscheinlich auf eine benachbarte Adresse zugegriffen.

Mit anderen Worten gesagt, sind die zeitliche und die räumliche Lokalität eine Folgerung aus der theoretischen Informatik und die Cache-Verwaltung der Prozessoren ist eine praktische Realisierung davon.

Jetzt können wir auch den Geschwindigkeitsunterschied in dem Einführungsbeispiel verstehen. Beim zeilenweisen Zugriff, werden nach dem ersten Cache-Miss die nächsten Elemente in den Cache gelegt. Somit ist der nachfolgende Zugriff (auf die nachfolgende Adresse) besonders schnell. Beim spaltenweisen Zugriff werden ebenfalls die nachfolgenden Elemente in den Cache abgelegt, aber man greift als nächstes nicht auf die nachfolgende Adresse zu, sondern auf die erste Adresse + Arraybreite. In der Regel liegt diese Adresse nicht im Cache und es muss wieder auf den langsameren Speicher geholt werden, was schließlich zur längeren Ausführungszeit führt.

Die Aufgabe des Programmierers ist auf diesen beiden Prinzipien aufzubauen und so die Programme schneller zu machen.