wake-up-neo.com

Wie schreibt man Code, der den CPU-Cache am besten nutzt, um die Leistung zu verbessern?

Dies könnte sich nach einer subjektiven Frage anhören, aber ich suche nach bestimmten Beispielen, die Sie möglicherweise in diesem Zusammenhang angetroffen haben.

  1. Wie kann man Code effektiv/Cache-freundlich machen (mehr Cache-Treffer, so wenig Cache-Fehler wie möglich)? Unter beiden Gesichtspunkten sollten Daten-Cache und Programm-Cache (Anweisungs-Cache), d. H. Welche Dinge im eigenen Code, die mit Datenstrukturen und Codekonstruktionen zusammenhängen, beachtet werden, um den Cache effektiv zu machen.

  2. Gibt es bestimmte Datenstrukturen, die verwendet/vermieden werden müssen, oder gibt es eine bestimmte Art des Zugriffs auf die Mitglieder dieser Struktur usw., um den Code-Cache effektiv zu machen?.

  3. Gibt es irgendwelche Programmkonstrukte (wenn, für, switch, break, goto, ...), Code-Flow (für innerhalb eines if, wenn innerhalb eines for, etc ...), die man in dieser Angelegenheit beachten/vermeiden sollte?

Ich freue mich auf individuelle Erfahrungen im Zusammenhang mit der Erstellung von Cache-effizientem Code im Allgemeinen. Es kann sich um eine beliebige Programmiersprache (C, C++, Assembly, ...), ein beliebiges Hardwareziel (ARM, Intel, PowerPC, ...), ein beliebiges Betriebssystem (Windows, Linux, S ymbian, ...) usw. handeln. .

Die Vielfalt wird dazu beitragen, es besser zu verstehen.

152
goldenmean

Der Cache dient dazu, die Wartezeit der CPU auf die Erfüllung einer Speicheranforderung zu verringern (Vermeidung des Speichers Latenz) und als zweiten Effekt möglicherweise die Gesamtdatenmenge zu verringern das muss übertragen werden (Erhaltung des Speichers Bandbreite).

Techniken zur Vermeidung von Latenzzeiten beim Abrufen des Speichers sind in der Regel das erste, das in Betracht gezogen werden muss, und helfen manchmal sehr. Die begrenzte Speicherbandbreite ist auch ein begrenzender Faktor, insbesondere für Multicores und Multithread-Anwendungen, bei denen viele Threads den Speicherbus verwenden möchten. Eine andere Reihe von Techniken hilft bei der Lösung des letzteren Problems.

Das Verbessern von räumliche Lokalität bedeutet, dass Sie sicherstellen, dass jede Cache-Zeile vollständig verwendet wird, sobald sie einem Cache zugeordnet wurde. Wenn wir uns verschiedene Standardbenchmarks angesehen haben, haben wir festgestellt, dass ein überraschend großer Teil derer nicht 100% der abgerufenen Cache-Zeilen verwendet, bevor die Cache-Zeilen entfernt werden.

Das Verbessern der Cachezeilenauslastung hilft in dreierlei Hinsicht:

  • Es passt in der Regel mehr nützliche Daten in den Cache, wodurch die effektive Cachegröße wesentlich erhöht wird.
  • In der Regel passen mehr nützliche Daten in dieselbe Cache-Zeile, wodurch sich die Wahrscheinlichkeit erhöht, dass angeforderte Daten im Cache gefunden werden.
  • Dies reduziert die Anforderungen an die Speicherbandbreite, da weniger Abrufe erfolgen.

Übliche Techniken sind:

  • Verwenden Sie kleinere Datentypen
  • Organisieren Sie Ihre Daten, um Ausrichtungslöcher zu vermeiden (das Sortieren Ihrer Strukturelemente durch Verringern der Größe ist eine Möglichkeit).
  • Achten Sie auf die standardmäßige dynamische Speicherzuordnung, durch die beim Aufwärmen möglicherweise Lücken entstehen und Ihre Daten im Arbeitsspeicher verteilt werden.
  • Stellen Sie sicher, dass alle angrenzenden Daten tatsächlich in den Hot Loops verwendet werden. Andernfalls sollten Sie Datenstrukturen in heiße und kalte Komponenten aufteilen, damit die heißen Schleifen heiße Daten verwenden.
  • vermeiden Sie Algorithmen und Datenstrukturen, die unregelmäßige Zugriffsmuster aufweisen, und bevorzugen Sie lineare Datenstrukturen.

Wir sollten auch beachten, dass es andere Möglichkeiten gibt, die Speicherlatenz auszublenden, als Caches zu verwenden.

Moderne CPUs haben oft einen oder mehrere Hardware Prefetchers. Sie trainieren die Fehler in einem Cache und versuchen, Regelmäßigkeiten zu erkennen. Beispielsweise beginnt der Hardware-Prefetcher nach einigen Fehlern bei nachfolgenden Cache-Zeilen mit dem Abrufen von Cache-Zeilen in den Cache, um den Anforderungen der Anwendung entgegenzukommen. Wenn Sie ein reguläres Zugriffsmuster haben, leistet der Hardware Prefetcher normalerweise sehr gute Arbeit. Und wenn Ihr Programm keine regulären Zugriffsmuster anzeigt, können Sie die Dinge verbessern, indem Sie Prefetch-Anweisungen selbst hinzufügen.

Wenn Anweisungen so neu gruppiert werden, dass diejenigen, die immer im Cache fehlen, nahe beieinander auftreten, kann die CPU diese Abrufe manchmal überlappen, sodass die Anwendung nur einen Latenztreffer erleidet (Memory Level Parallelism).

Um den Gesamtspeicherbusdruck zu verringern, müssen Sie anfangen, das anzusprechen, was zeitlicher Ort genannt wird. Dies bedeutet, dass Sie Daten wiederverwenden müssen, solange sie noch nicht aus dem Cache entfernt wurden.

Das Zusammenführen von Schleifen, die dieselben Daten berühren (Schleifenfusion), und das Verwenden von Umschreibungstechniken, die als Kacheln oder Blockieren bekannt sind, bemühen sich, diese zusätzlichen Speicherabrufe zu vermeiden .

Obwohl es einige Faustregeln für diese Umschreibübung gibt, müssen Sie in der Regel die schleifenbasierten Datenabhängigkeiten sorgfältig berücksichtigen, um sicherzustellen, dass Sie die Semantik des Programms nicht beeinflussen.

Diese Dinge zahlen sich in der Multicore-Welt aus, in der nach dem Hinzufügen des zweiten Threads in der Regel keine großen Durchsatzverbesserungen zu verzeichnen sind.

116
Mats N

Ich kann nicht glauben, dass es keine weiteren Antworten darauf gibt. Wie auch immer, ein klassisches Beispiel ist, ein mehrdimensionales Array "von innen nach außen" zu iterieren:

pseudocode
for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[j][i]

Der Grund dafür, dass der Cache ineffizient ist, ist, dass moderne CPUs die Cache-Zeile mit "nahen" Speicheradressen aus dem Hauptspeicher laden, wenn Sie auf eine einzelne Speicheradresse zugreifen. Wir durchlaufen die "j" (äußeren) Zeilen im Array in der inneren Schleife, sodass die Cache-Zeile bei jedem Durchlauf durch die innere Schleife geleert und mit einer Adresszeile geladen wird, die sich in der Nähe der [ j] [i] eintrag. Wenn dies auf das Äquivalent geändert wird:

for (i = 0 to size)
  for (j = 0 to size)
    do something with ary[i][j]

Es wird viel schneller laufen.

52

Ich empfehle den 9-teiligen Artikel Was jeder Programmierer über Speicher wissen sollte von Ulrich Drepper, wenn Sie daran interessiert sind, wie Speicher und Software interagieren. Es ist auch verfügbar als ein 104-seitiges PDF .

Abschnitte, die für diese Frage besonders relevant sind, könnten Teil 2 (CPU-Caches) und Teil 5 (Was Programmierer tun können - Cache-Optimierung) sein.

43
Tomi Kyöstilä

Die Grundregeln sind eigentlich ziemlich einfach. Was schwierig wird, ist die Art und Weise, wie sie auf Ihren Code angewendet werden.

Der Cache funktioniert nach zwei Prinzipien: zeitliche Lokalität und räumliche Lokalität. Ersteres ist die Idee, dass Sie einen bestimmten Datenblock wahrscheinlich bald wieder benötigen, wenn Sie ihn kürzlich verwendet haben. Letzteres bedeutet, dass Sie, wenn Sie die Daten kürzlich unter der Adresse X verwendet haben, wahrscheinlich bald die Adresse X + 1 benötigen.

Der Cache versucht, dies zu berücksichtigen, indem er sich die zuletzt verwendeten Datenblöcke merkt. Es arbeitet mit Cache-Zeilen, die normalerweise eine Größe von etwa 128 Byte haben. Selbst wenn Sie also nur ein einziges Byte benötigen, wird die gesamte Cache-Zeile, in der es sich befindet, in den Cache gezogen. Wenn Sie anschließend das folgende Byte benötigen, befindet es sich bereits im Cache.

Und das bedeutet, dass Sie immer Ihren eigenen Code haben möchten, um diese beiden Lokalitätsformen so gut wie möglich auszunutzen. Springe nicht über das Gedächtnis. Arbeiten Sie auf einem kleinen Gebiet so viel wie möglich, und fahren Sie dann mit dem nächsten fort, und tun Sie dort so viel wie möglich.

Ein einfaches Beispiel ist die 2D-Array-Durchquerung, die die Antwort von 1800 zeigte. Wenn Sie es nacheinander durchlaufen, lesen Sie den Speicher nacheinander. Wenn Sie dies spaltenweise tun, lesen Sie einen Eintrag, springen dann zu einer völlig anderen Position (dem Anfang der nächsten Zeile), lesen einen Eintrag und springen erneut. Und wenn Sie endlich in die erste Reihe zurückkehren, befindet sich diese nicht mehr im Cache.

Gleiches gilt für Code. Sprünge oder Verzweigungen bedeuten eine weniger effiziente Cache-Nutzung (da Sie die Anweisungen nicht nacheinander lesen, sondern zu einer anderen Adresse springen). Natürlich werden kleine if-Anweisungen wahrscheinlich nichts ändern (Sie überspringen nur ein paar Bytes, so dass Sie immer noch in der zwischengespeicherten Region landen), aber Funktionsaufrufe implizieren normalerweise, dass Sie zu einer völlig anderen springen Adresse, die möglicherweise nicht zwischengespeichert wird. Es sei denn, es wurde vor kurzem aufgerufen.

Die Verwendung des Befehls-Cache ist jedoch in der Regel weitaus weniger problematisch. Worüber Sie sich normalerweise Gedanken machen müssen, ist der Datencache.

In einer Struktur oder Klasse werden alle Mitglieder zusammenhängend angeordnet, was gut ist. In einem Array werden alle Einträge auch zusammenhängend angeordnet. In verknüpften Listen wird jeder Knoten an einem völlig anderen Ort zugeordnet, was schlecht ist. Zeiger neigen im Allgemeinen dazu, auf nicht verwandte Adressen zu verweisen, was wahrscheinlich zu einem Cache-Fehler führt, wenn Sie die Referenzierung aufheben.

Und wenn Sie mehrere Kerne ausnutzen möchten, kann dies sehr interessant werden, da normalerweise jeweils nur eine CPU eine Adresse im L1-Cache hat. Wenn also beide Kerne ständig auf dieselbe Adresse zugreifen, führt dies zu ständigen Cache-Fehlern, da sie um die Adresse streiten.

43
jalf

Neben den Datenzugriffsmustern ist data size ein Hauptfaktor für den Cache-freundlichen Code. Weniger Daten bedeuten, dass mehr davon in den Cache passen.

Dies ist hauptsächlich ein Faktor bei speicherausgerichteten Datenstrukturen. "Herkömmliche" Weisheiten besagen, dass Datenstrukturen an Wortgrenzen ausgerichtet werden müssen, da die CPU nur auf ganze Wörter zugreifen kann. Wenn ein Wort mehr als einen Wert enthält, müssen Sie zusätzliche Arbeit leisten (Lesen-Ändern-Schreiben anstelle von einfachem Schreiben). . Caches können dieses Argument jedoch vollständig ungültig machen.

Ebenso verwendet ein Java boolesches Array ein ganzes Byte für jeden Wert, um einzelne Werte direkt bearbeiten zu können. Sie können die Datengröße um den Faktor 8 reduzieren, wenn Sie tatsächliche Bits verwenden, aber Der Zugriff auf einzelne Werte wird dann sehr viel komplexer und erfordert Bitverschiebungs- und Maskenoperationen (die Klasse BitSet erledigt dies für Sie.) Aufgrund von Cache-Effekten kann dies jedoch immer noch erheblich schneller sein als die Verwendung eines Booleschen []. Wenn das Array groß ist, habe ich auf diese Weise einmal eine Beschleunigung um den Faktor 2 oder 3 erreicht.

14

Die effektivste Datenstruktur für einen Cache ist ein Array. Caches funktionieren am besten, wenn Ihre Datenstruktur sequentiell angeordnet ist und CPUs ganze Cache-Zeilen (normalerweise 32 Byte oder mehr) gleichzeitig aus dem Hauptspeicher lesen.

Jeder Algorithmus, der in zufälliger Reihenfolge auf den Speicher zugreift, verwirft die Caches, da er immer neue Cache-Zeilen benötigt, um den Arbeitsspeicher aufzunehmen, auf den zufällig zugegriffen wird. Andererseits ist ein Algorithmus, der sequentiell durch ein Array läuft, am besten, weil:

  1. Dies gibt der CPU die Möglichkeit, vorauszulesen, z. Stellen Sie spekulativ mehr Speicher in den Cache, auf den später zugegriffen wird. Dieses Vorauslesen verleiht einen enormen Leistungsschub.

  2. Durch das Ausführen einer engen Schleife über ein großes Array kann die CPU auch den in der Schleife ausgeführten Code zwischenspeichern. In den meisten Fällen können Sie einen Algorithmus vollständig aus dem Cache-Speicher ausführen, ohne den externen Speicherzugriff blockieren zu müssen.

9
grover

Ein Beispiel, das ich in einer Spiele-Engine gesehen habe, war das Verschieben von Daten aus Objekten in ihre eigenen Arrays. An ein Spielobjekt, das Gegenstand der Physik war, können auch viele andere Daten angehängt sein. Während der Physik-Aktualisierungsschleife kümmerte sich der Motor nur um Daten zu Position, Geschwindigkeit, Masse, Begrenzungsrahmen usw. All dies wurde in eigenen Arrays abgelegt und so weit wie möglich für SSE optimiert.

Während der Physikschleife wurden die Physikdaten in Array-Reihenfolge unter Verwendung von Vektormathematik verarbeitet. Die Spielobjekte verwendeten ihre Objekt-ID als Index für die verschiedenen Arrays. Es war kein Zeiger, da Zeiger ungültig werden könnten, wenn die Arrays verschoben werden müssten.

In vielerlei Hinsicht hat dies gegen objektorientierte Entwurfsmuster verstoßen, den Code jedoch erheblich beschleunigt, indem Daten, die in denselben Schleifen bearbeitet werden mussten, dicht beieinander platziert wurden.

Dieses Beispiel ist wahrscheinlich veraltet, da ich davon ausgehe, dass die meisten modernen Spiele eine vorgefertigte Physik-Engine wie Havok verwenden.

8
Zan Lynx

Eine Bemerkung zum "klassischen Beispiel" von Benutzer 1800 INFORMATION (zu lang für einen Kommentar)

Ich wollte die Zeitunterschiede für zwei Iterationsreihenfolgen ("outter" und "inner") überprüfen und machte deshalb ein einfaches Experiment mit einem großen 2D-Array:

measure::start();
for ( int y = 0; y < N; ++y )
for ( int x = 0; x < N; ++x )
    sum += A[ x + y*N ];
measure::stop();

und der zweite Fall mit den for Schleifen vertauscht.

Die langsamere Version ("x first") war 0,88 Sekunden und die schnellere war 0,06 Sekunden. Das ist die Kraft des Zwischenspeicherns :)

Ich benutzte gcc -O2 und trotzdem wurden die Schleifen nicht optimiert. Die Bemerkung von Ricardo , dass "die meisten modernen Compiler dies selbst herausfinden können", trifft nicht zu

7
Jakub M.

Es wurde nur ein Beitrag behandelt, aber beim Austausch von Daten zwischen Prozessen tritt ein großes Problem auf. Sie möchten vermeiden, dass mehrere Prozesse versuchen, dieselbe Cache-Zeile gleichzeitig zu ändern. Zu beachten ist hier die "falsche" Freigabe, bei der zwei benachbarte Datenstrukturen eine Cache-Zeile gemeinsam nutzen und Änderungen an einer die Cache-Zeile für die andere ungültig machen. Dies kann dazu führen, dass Cache-Zeilen unnötigerweise zwischen Prozessor-Caches hin und her verschoben werden, die die Daten auf einem Multiprozessorsystem gemeinsam nutzen. Eine Möglichkeit, dies zu vermeiden, besteht darin, Datenstrukturen so auszurichten und aufzufüllen, dass sie auf verschiedene Zeilen gesetzt werden.

7
RussellH

Ich kann (2) damit beantworten, dass verknüpfte Listen in der C++ - Welt leicht den CPU-Cache zerstören können. Arrays sind nach Möglichkeit eine bessere Lösung. Keine Erfahrung darüber, ob das Gleiche für andere Sprachen gilt, aber es ist leicht vorstellbar, dass dieselben Probleme auftreten würden.

4
Andrew

Der Cache ist in "Cache-Zeilen" angeordnet, und (realer) Speicher wird in Blöcken dieser Größe gelesen und beschrieben.

Datenstrukturen, die in einer einzelnen Cache-Zeile enthalten sind, sind daher effizienter.

Ebenso sind Algorithmen, die auf zusammenhängende Speicherblöcke zugreifen, effizienter als Algorithmen, die in zufälliger Reihenfolge durch den Speicher springen.

Leider variiert die Cache-Zeilengröße zwischen den Prozessoren dramatisch, sodass nicht garantiert werden kann, dass eine auf einem Prozessor optimale Datenstruktur auf einem anderen Prozessor effizient ist.

4
Alnitak

Die Frage, wie ein Code erstellt, der effektiv und Cache-freundlich ist, und die meisten anderen Fragen, lautet in der Regel, wie ein Programm optimiert werden kann, da der Cache einen so großen Einfluss auf die Leistung hat, dass jedes optimierte Programm ein Cache ist effektiv Cache freundlich.

Ich schlage vor, über Optimierung zu lesen. Auf dieser Website finden Sie einige gute Antworten. In Bezug auf Bücher empfehle ich Computersysteme: Die Perspektive eines Programmierers , das einen guten Text über die ordnungsgemäße Verwendung des Caches enthält.

(b.t.w - so schlimm ein Cache-Miss auch sein kann, es ist schlimmer - wenn ein Programm Paging von der Festplatte ist ...)

4
Liran Orevi

Es gab viele Antworten auf allgemeine Ratschläge wie Datenstrukturauswahl, Zugriffsmuster usw. Hier möchte ich ein weiteres Code-Design-Muster hinzufügen, das als Software-Pipeline bezeichnet wird. ), die die aktive Cache-Verwaltung nutzt.

Die Idee stammt von anderen Pipeline-Techniken, z. CPU-Anweisungs-Pipelining.

Diese Art von Muster eignet sich am besten für Verfahren, die

  1. könnte in sinnvolle mehrere Unterschritte, S [1], S [2], S [3], ..., zerlegt werden, deren Ausführungszeit in etwa vergleichbar ist mit RAM Zugriffszeit (~ 60-70ns).
  2. führt eine Reihe von Eingaben aus und führt die oben genannten Schritte aus, um das Ergebnis zu erhalten.

Nehmen wir einen einfachen Fall, in dem es nur eine Unterprozedur gibt. Normalerweise würde der Code gerne:

def proc(input):
    return sub-step(input))

Um eine bessere Leistung zu erzielen, möchten Sie möglicherweise mehrere Eingaben in einem Stapel an die Funktion übergeben, um den Funktionsaufruf-Overhead zu amortisieren und die Code-Cache-Lokalität zu erhöhen.

def batch_proc(inputs):
    results = []
    for i in inputs:
        // avoids code cache miss, but still suffer data(inputs) miss
        results.append(sub-step(i))
    return res

Wie bereits erwähnt, können Sie den Code weiter verbessern, wenn die Ausführung des Schritts in etwa mit der Zugriffszeit von RAM) übereinstimmt:

def batch_pipelined_proc(inputs):
    for i in range(0, len(inputs)-1):
        prefetch(inputs[i+1])
        # work on current item while [i+1] is flying back from RAM
        results.append(sub-step(inputs[i-1]))

    results.append(sub-step(inputs[-1]))

Der Ausführungsablauf würde folgendermaßen aussehen:

  1. prefetch (1) Die CPU wird aufgefordert, die Eingabe [1] vorab in den Cache zu holen, wobei die Vorabrufanweisung P-Zyklen selbst dauert und zurückkehrt, und im Hintergrund würde die Eingabe [1] nach R-Zyklen in den Cache gelangen.
  2. works_on (0) Cold Miss auf 0 und arbeitet daran, was M braucht
  3. prefetch (2) erneut holen
  4. works_on (1) Wenn P + R <= M ist, sollten sich die Eingänge [1] bereits vor diesem Schritt im Cache befinden. Vermeiden Sie daher einen Daten-Cache-Fehler
  5. works_on (2) ...

Es könnten mehr Schritte erforderlich sein, dann können Sie eine mehrstufige Pipeline entwerfen, solange das Timing der Schritte und die Speicherzugriffslatenz übereinstimmen und Sie einen geringen Code-/Daten-Cache-Fehler erleiden. Dieser Prozess muss jedoch mit vielen Experimenten abgestimmt werden, um die richtige Gruppierung von Schritten und die richtige Vorabrufzeit herauszufinden. Aufgrund des erforderlichen Aufwands wird die Hochleistungsverarbeitung von Daten-/Paketströmen zunehmend eingesetzt. Ein gutes Beispiel für einen Produktionscode finden Sie im DPDK QoS Enqueue-Pipeline-Design: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Kapitel 21.2.4.3. Pipeline einreihen.

Weitere Informationen finden Sie unter:

https://software.intel.com/de-de/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

4
Wei Shen

Neben der Ausrichtung Ihrer Struktur und Ihrer Felder möchten Sie, wenn Ihre Struktur einen Heapspeicher zugewiesen hat, möglicherweise Zuweiser verwenden, die die Ausrichtung von Zuweisungen unterstützen. wie _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); Andernfalls kann es vorkommen, dass Sie eine zufällige falsche Weitergabe haben. Denken Sie daran, dass der Standardheap unter Windows eine 16-Byte-Ausrichtung hat.

1
aracntido

Schreiben Sie Ihr Programm auf eine minimale Größe. Aus diesem Grund ist es nicht immer sinnvoll, -O3-Optimierungen für GCC zu verwenden. Es nimmt eine größere Größe ein. Oft ist -Os genauso gut wie -O2. Es hängt jedoch alles vom verwendeten Prozessor ab. YMMV.

Arbeiten Sie mit kleinen Datenblöcken gleichzeitig. Aus diesem Grund können weniger effiziente Sortieralgorithmen bei großen Datenmengen schneller als Quicksort ausgeführt werden. Finden Sie Möglichkeiten, um Ihre größeren Datensätze in kleinere zu unterteilen. Andere haben dies vorgeschlagen.

Um die zeitliche/räumliche Lokalität der Anweisungen besser ausnutzen zu können, sollten Sie untersuchen, wie Ihr Code in Assembly konvertiert wird. Beispielsweise:

for(i = 0; i < MAX; ++i)
for(i = MAX; i > 0; --i)

Die beiden Schleifen erzeugen unterschiedliche Codes, obwohl sie lediglich ein Array analysieren. In jedem Fall ist Ihre Frage sehr architekturspezifisch. Die einzige Möglichkeit, die Cache-Nutzung genau zu steuern, besteht darin, die Funktionsweise der Hardware zu verstehen und den Code dafür zu optimieren.

1
sybreon