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

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.

Benötigte Zeit zum schreiben eines Arrays in Abhängigkeit von der Array-Größe.
Benötigte Zeit zum schreiben eines Arrays in Abhängigkeit von der Array-Größe.

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 1.

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.

Geschwindigkeitsgewinn beim durchlaufen eines Arrays (Schreibvorgang) zeilenweise, anstatt spaltenweise. Aufgetragen in Abhängigkeit von der Array-Größe.
Geschwindigkeitsgewinn beim durchlaufen eines Arrays (Schreibvorgang) zeilenweise, anstatt spaltenweise. Aufgetragen in Abhängigkeit von der Array-Größe.

Nach der Grafik zu urteilen beträgt der Geschwindigkeitsfaktor etwa 13 2. 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.

Benötigte Zeit zum lesen eines Arrays in Abhängigkeit von der Array-Größe.
Benötigte Zeit zum lesen eines Arrays in Abhängigkeit von der Array-Größe.
Geschwindigkeitsgewinn beim durchlaufen eines Arrays (Lesevorgang) zeilenweise, anstatt spaltenweise. Aufgetragen in Abhängigkeit von der Array-Größe.
Geschwindigkeitsgewinn beim durchlaufen eines Arrays (Lesevorgang) zeilenweise, anstatt spaltenweise. Aufgetragen in Abhängigkeit von der Array-Größe.

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.

Cache-Hierarchie.
Cache-Hierarchie.

L1- Cache ist der kleinste Speicher, er liegt am nächsten zum Prozessor und der Zugriff darauf geschieht am schnellsten 3. 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.

1 Woher genau die beiden Peaks kommen weiß ich auch nicht (das sind keine statistischen Schwankungen). Hinweise und Erklärungen sind erwünscht.

2 Die Ausreißer in der ersten Hälfte der Grafik sind statistische Schwankungen, bedingt durch ungenaue Zeitmessung.

3 Auf den Registern wird gerechnet, also fallen sie aus der Betrachtung heraus.

3 Gedanken zu „Cache-Optimierung: Zeitliche und Räumliche Lokalität“

  1. Ich weiß nicht ob du das mitbekommen hast, aber ich finde es passt ganz gut dazu.

    Bjarne Stroustrup hat auf der GoingNative2012 demonstriert, dass auch die Verwendung von std::vector meistens besser ist als die Verwendung von std::list. Der Grund ist letztlich wieder der CPU-Cache: Die Einfüge- und Lösch-Operationen des std::vector, welche angeblich ja so langsam sind, werden vom Cache extrem beschleunigt, weil der Inhalt eines std::vectors eben stets in einem kompakten (zusammenhängenden) Bereich des Arbeitsspeichers abgelegt wird.

    Bei einer std::list liegen die Elemente kreuz und quer im Arbeitsspeicher verteilt, d.h. „eine std::list maximiert die die Cache-Misses“ (das ist fast original das, was Stroustrup gesagt hat).

    Stroustrup hat daraus gefolgert, dass man bei C++ standardmäßig immer erstmal (!) std::vector nehmen soll.

    Seinen Vortrag müsste man sich noch auf Channel9 ansehen können.

  2. Hallo Robert.
    Nein, ich verfolge diese Thematik nicht. Bin ja auch ein Fachfremder ;)
    Meistens verwende ich sowieso std::vector, weil es mir praktischer erscheint. Damit habe ich den Komfort einer std::list plus einen wahlfreien Zugriff.
    Meistens muss man sowieso genauer anschauen, welche Datenstruktur besser geeignet ist, wenn es wirklich um die letzten Performance-Tropfen geht.

Schreibe einen Kommentar