Was ist "cache-freundlicher" Code?

Question

Was ist der Unterschied zwischen "cache-unfreundlichem Code" und dem "cache-freundlichen" Code?

Wie kann ich sicherstellen, dass ich cache-effizienten Code schreibe?

Answer 1

Es muss klar gestellt werden, dass nicht nur Daten cache-freundlich sein sollten, sondern auch der Code. Dies ist neben der Zweigvorhersage, der Befehlsneuordnung, der Vermeidung von tatsächlichen Divisionen und anderen Techniken.

Typischerweise werden je dichter der Code ist, desto weniger Cache-Lines benötigt, um ihn zu speichern. Dies führt dazu, dass mehr Cache-Lines für Daten verfügbar sind.

Der Code sollte nicht überall Funktionen aufrufen, da diese typischerweise eine oder mehrere Cache-Lines für sich benötigen, was zu weniger Cache-Lines für Daten führt.

Eine Funktion sollte an einer cache-line-freundlichen Adresse beginnen. Obwohl es (gcc) Compiler-Schalter dafür gibt, beachten Sie, dass es bei sehr kurzen Funktionen verschwenderisch sein könnte, wenn jede eine ganze Cache-Line einnimmt. Zum Beispiel, wenn drei der am häufigsten verwendeten Funktionen in eine 64-Byte-Cache-Line passen, ist dies weniger verschwenderisch als wenn jede ihre eigene Linie hat und resultiert in zwei Cache-Lines weniger, die für andere Zwecke verfügbar sind. Ein typischer Ausrichtungswert könnte 32 oder 16 sein.

Also nehmen Sie sich etwas extra Zeit, um den Code dicht zu machen. Testen Sie verschiedene Konstrukte, kompilieren Sie und überprüfen Sie die generierte Code-Größe und das Profil.

Answer 2

Wie @Marc Claesen erwähnt hat, ist eine Möglichkeit, cache-freundlichen Code zu schreiben, die Struktur zu nutzen, in der unsere Daten gespeichert sind. Eine weitere Möglichkeit, cache-freundlichen Code zu schreiben, besteht darin: Ändern Sie die Art und Weise, wie unsere Daten gespeichert sind, und schreiben Sie dann neuen Code, um auf die in dieser neuen Struktur gespeicherten Daten zuzugreifen.

Dies ergibt Sinn im Fall von Datenbanksystemen, die die Tupel einer Tabelle linearisieren und speichern. Es gibt zwei grundlegende Möglichkeiten, die Tupel einer Tabelle zu speichern, nämlich Zeilenspeicher und Spaltenspeicher. Im Zeilenspeicher werden die Tupel, wie der Name schon sagt, zeilenweise gespeichert. Nehmen wir an, eine Tabelle namens Produkt hat 3 Attribute, nämlich int32_t key, char name[56] und int32_t price, sodass die Gesamtgröße eines Tupels 64 Bytes beträgt.

Wir können eine sehr einfache Zeilenspeicherabfrage in den Hauptspeicher simulieren, indem wir ein Array von Produkt Strukturen mit der Größe N erstellen, wobei N die Anzahl der Zeilen in der Tabelle ist. Eine solche Speicheranordnung wird auch als Array von Strukturen bezeichnet. Die Struktur für Produkt kann wie folgt aussehen:

struct Produkt
{
   int32_t key;
   char name[56];
   int32_t price;
}

/* Erzeuge ein Array von Strukturen */
Produkt* tabelle = new Produkt[N];
/* Lade nun dieses Array von Strukturen, z. B. aus einer Datei */

Ebenso können wir eine sehr einfache Spaltenlayoutabfrage in den Hauptspeicher simulieren, indem wir 3 Arrays der Größe N erstellen, ein Array für jedes Attribut der Tabelle Produkt. Eine solche Speicheranordnung wird auch als Struktur von Arrays bezeichnet. Die 3 Arrays für jedes Attribut von Produkt können wie folgt aussehen:

/* Erzeuge separate Arrays für jedes Attribut */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* Lade nun diese Arrays, z. B. aus einer Datei */

Nachdem wir sowohl das Array von Strukturen (Zeilenlayout) als auch die 3 separaten Arrays (Spaltenlayout) geladen haben, haben wir Zeilenspeicher und Spaltenspeicher auf unserer Tabelle Produkt im Speicher.

Jetzt kommen wir zum Teil des cache-freundlichen Codes. Angenommen, die Arbeitslast auf unserer Tabelle ist so, dass wir eine Aggregationsabfrage zum Attribut price haben. Wie zum Beispiel

SELECT SUM(price)
FROM PRODUKT

Für den Zeilenspeicher können wir die obige SQL-Abfrage in Folgendes umwandeln

int sum = 0;
for (int i=0; i

Für den Spaltenlayout können wir die obige SQL-Abfrage in Folgendes umwandeln

    int sum = 0;
    for (int i=0; i

``

Der Code für das Spaltenlayout wäre schneller als der Code für das Zeilenlayout in dieser Abfrage, da er nur eine Teilmenge von Attributen benötigt und im Spaltenlayout genau das tun, d.h. nur auf die Preisspalte zugreifen.

Angenommen, die Cache-Zeilenlänge beträgt `64` Byte.

Im Fall des Zeilenlayouts, wenn eine Cache-Zeile gelesen wird, wird der Preiswert von nur 1(`Cachelinie_Größe/Produktstrukturgröße = 64/64 = 1`) Tupel gelesen, weil unsere Strukturgöße 64 Bytes beträgt und die gesamte Cache-Zeile füllt, sodass für jedes Tupel ein Cache-Miss im Falle eines Zeilenlayouts auftritt.

Im Fall des Spaltenlayouts, wenn eine Cache-Zeile gelesen wird, werden die Preiswerte von 16(`Cachelinie_Größe/Preis_int_Größe = 64/4 = 16`) Tupeln gelesen, da 16 aufeinander folgende Preiswerte, die im Speicher gespeichert sind, in den Cache geladen werden, sodass für jedes sechzehnte Tupel im Fall des Spaltenlayouts ein Cache-Miss auftritt.

Das Spaltenlayout wird daher in diesem Fall der gegebenen Abfrage schneller sein und ist schneller bei solchen Aggregationsabfragen auf einer Teilmenge von Spalten der Tabelle. Sie können ein solches Experiment mit den Daten aus dem [TPC-H](http://www.tpc.org/tpch/)-Benchmark selbst durchführen und die Laufzeiten für beide Speicheranordnungen vergleichen. Der [Wikipedia](https://de.wikipedia.org/wiki/Spaltenorientierte_Datenbank)-Artikel über spaltenorientierte Datenbanksysteme ist ebenfalls gut.

Also, in Datenbanksystemen, wenn die Abfrage-Arbeitslast im Voraus bekannt ist, können wir unsere Daten in Layouts speichern, die zu den Abfragen in der Arbeitslast passen, und von diesen Layouts aus auf die Daten zugreifen. Im Fall des obigen Beispiels haben wir ein Spaltenlayout erstellt und unseren Code so geändert, dass er die Summe berechnet und cache-freundlich wird.

`` ```

Answer 3

Beachten Sie, dass Caches nicht nur kontinuierlichen Speicher zwischenspeichern. Sie haben mehrere Zeilen (mindestens 4), daher können auch diskontinuierlicher und überlappender Speicher oft genauso effizient gespeichert werden.

Was in allen obigen Beispielen fehlt, sind gemessene Leistungsindikatoren. Es gibt viele Mythen über Leistung. Wenn Sie es nicht messen, wissen Sie es nicht. Komplizieren Sie Ihren Code nicht, es sei denn, Sie haben eine gemessene Verbesserung.

Answer 4

Stellen Sie sicher, dass Ihr Programm Ihre Hardware bevorzugt, indem Sie spezifische Metriken während des Design- und Laufzeitoptimierungsprozesses optimieren

Hintergrundkonzept: Synergetisch mit Caching & Branch Prediction

Die Leistung von Software ist proportional zu ihrer Synergie mit den Verarbeitungsprinzipien der Hardware, auf der sie ausgeführt wird. Die Leistung einer Von-Neumann-Computerarchitektur hängt wesentlich davon ab, wie schnell Daten zwischen Speicher und Logik/Arithmetikeinheiten fließen können, wobei der Datenbus das Hauptproblem darstellt. Mehrere Maßnahmen wurden implementiert, um dieses Problem zu reduzieren, und sie drehen sich hauptsächlich um die Segmentierung des Speichers in eine Hierarchie verschiedener Leistungsebenen (Caching) und die Optimierung des Datenmanagements über diese Hierarchie (Branch Prediction). Daher bringt die Synergie Ihrer Programme mit der Art des Cachens und der Verzweigungsvorhersage der Hardware enorme Leistungsvorteile bei der Ausführung auf einer Von-Neumann-Architektur.

Stellen Sie sicher, dass Daten als lokale feste Variablen auf dem Stapel abgelegt werden und vermeiden Sie die Zuweisung von dynamischem Speicher im Heap über malloc

Um Ihr Programm synergetisch mit Caching und Branch Prediction zu gestalten, müssen Sie Ihr Datenhandling so entwerfen, dass Daten größtenteils optimal in den Caches (vor)geladen werden. Ihre Hardware wird in der Regel sehr gut darin sein, Ihr Programm zu cachen, da sie vorhersagen kann, welcher Code gerade ausgeführt wird, einschließlich der Operation sowie lokaler Variablen. Was in der Regel schlecht gecacht wird, sind die dynamisch allozierten Speichersegment. Wenn Sie also vermeiden, Speicher selbst über malloc zuzuweisen und nur lokale Variablen verwenden, sollte Ihr Programm gut optimiert sein. Eine effiziente Speicherverwaltung, die sich auf den Stapel konzentriert, ist entscheidend.

Es gibt Laufzeitanalysetools, die Ihre Metriken zur Speicherzuweisung innerhalb Ihres Programms zeigen. Verwenden Sie diese Statistiken, um sicherzustellen, dass Ihre Software in Bezug auf den Speicher optimiert ist.

Stellen Sie sicher, dass Sie Flusssteuerungsaussagen wie if/else/do/while/switch/jump durch mathematische Operationen mit branchenlosem Programmieren ersetzt haben

Da die Verzweigungsvorhersage versucht vorherzusagen, welcher Zweig ausgeführt wird, können Sie die Erfolgswahrscheinlichkeit auf 100% erhöhen, indem Sie die möglichen Zweige auf nur einen reduzieren - dies wird als branchless Programmierung bezeichnet und beinhaltet den Austausch von Flusssteuerungsaussagen durch mathematische Operationen. Dies hat auch den Vorteil, dass hauptsächlich die Verwendung von CPU-Registern beteiligt ist und die Verwendung von speicherbasierten Variablen vermieden wird und somit die Leistung weiter erhöht wird. Branchless-Programmierung ist ein fortgeschrittenes Konzept und zu groß, um es hier weiter zu erläutern.

Es gibt Quellcodeanalysetools, die Ihre Metriken zu den Zweigen innerhalb Ihrer Algorithmen zeigen. Verwenden Sie diese Statistiken, um sicherzustellen, dass Ihre Software in Bezug auf die minimale Anzahl von Verzweigungen optimiert ist.