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

159

Dies könnte sich wie eine subjektive Frage anhören, aber ich suche nach bestimmten Fällen, auf die Sie im Zusammenhang damit gestoßen sein könnten.

  1. Wie macht man Code, Cache effektiv / Cache-freundlich (mehr Cache-Treffer, so wenig Cache-Fehler wie möglich)? Aus beiden Perspektiven, Datencache und Programmcache (Anweisungscache), dh welche Dinge im eigenen Code, die sich auf Datenstrukturen und Codekonstrukte beziehen, sollte man sich darum kümmern, dass der Cache effektiv ist.

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

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

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

Die Vielfalt wird dazu beitragen, es besser zu verstehen.

goldene Mitte
quelle
1
Als Intro gibt dieser Vortrag einen guten Überblick youtu.be/BP6NxVxDQIs
schoetbi
Die oben verkürzte URL scheint nicht mehr zu funktionieren, dies ist die vollständige URL zum Vortrag: youtube.com/watch?v=BP6NxVxDQIs
Abhinav Upadhyay

Antworten:

119

Der Cache ist es die Anzahl der Male zu verringern die CPU abgewürgt würde für eine Speicheranforderung warten erfüllt werden (die Speicher Vermeidung Latenz ) und als zweiter Effekt, möglicherweise die Gesamtdatenmenge zu reduzieren , die (Konservieren werden übertragen muss Speicherbandbreite ).

Techniken zur Vermeidung von Speicherabrufverzögerungen sind in der Regel das erste, was in Betracht gezogen werden muss, und helfen manchmal auf lange Sicht. 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, das letztere Problem anzugehen.

Durch die Verbesserung der räumlichen Lokalität stellen Sie sicher, dass jede Cache-Zeile vollständig verwendet wird, sobald sie einem Cache zugeordnet wurde. Wenn wir uns verschiedene Standard-Benchmarks angesehen haben, haben wir festgestellt, dass ein überraschend großer Teil davon nicht 100% der abgerufenen Cache-Zeilen verwendet, bevor die Cache-Zeilen entfernt werden.

Die Verbesserung der Cache-Zeilenauslastung hilft in dreierlei Hinsicht:

  • Es passt tendenziell nützlichere Daten in den Cache, wodurch die effektive Cache-Größe wesentlich erhöht wird.
  • Es passt tendenziell nützlichere Daten in dieselbe Cache-Zeile, was 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 den standardmäßigen dynamischen Speicherzuweiser, der beim Aufwärmen zu Lücken führen und Ihre Daten im Speicher verteilen kann.
  • Stellen Sie sicher, dass alle benachbarten Daten tatsächlich in den Hot Loops verwendet werden. Andernfalls sollten Sie Datenstrukturen in heiße und kalte Komponenten aufteilen, damit die Hot-Loops heiße Daten verwenden.
  • Vermeiden Sie Algorithmen und Datenstrukturen mit unregelmäßigen Zugriffsmustern und bevorzugen Sie lineare Datenstrukturen.

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

Moderne CPUs verfügen häufig über einen oder mehrere Hardware-Prefetchers . Sie trainieren die Fehler in einem Cache und versuchen, Regelmäßigkeiten zu erkennen. Beispielsweise beginnt der hw-Prefetcher nach einigen Fehlern bei nachfolgenden Cache-Zeilen mit dem Abrufen von Cache-Zeilen in den Cache, um die Anforderungen der Anwendung zu antizipieren. 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 selbst Vorabrufanweisungen hinzufügen .

Wenn die Anweisungen so umgruppiert werden, dass diejenigen, die immer im Cache fehlen, nahe beieinander auftreten, kann die CPU diese Abrufe manchmal überlappen, sodass die Anwendung nur einen Latenztreffer aushält ( Parallelität auf Speicherebene ).

Um den Gesamtspeicherbusdruck zu reduzieren, müssen Sie sich mit der sogenannten zeitlichen Lokalität befassen . 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 Umschreibtechniken, die als Kacheln oder Blockieren bekannt sind, versuchen, diese zusätzlichen Speicherabrufe zu vermeiden.

Obwohl es für diese Übung zum Umschreiben einige Faustregeln gibt, müssen Sie in der Regel die Abhängigkeiten von Schleifendaten sorgfältig berücksichtigen, um sicherzustellen, dass Sie die Semantik des Programms nicht beeinflussen.

Diese Dinge zahlen sich in der Multicore-Welt wirklich aus, in der Sie nach dem Hinzufügen des zweiten Threads normalerweise keine großen Durchsatzverbesserungen feststellen.

Matten N.
quelle
5
Wenn wir uns verschiedene Standard-Benchmarks angesehen haben, haben wir festgestellt, dass ein überraschend großer Teil davon nicht 100% der abgerufenen Cache-Zeilen verwendet, bevor die Cache-Zeilen entfernt werden. Darf ich fragen, welche Art von Profiling-Tools Ihnen diese Art von Informationen geben und wie?
Dragon Energy
"Organisieren Sie Ihre Daten, um Ausrichtungslöcher zu vermeiden (das Sortieren Ihrer Strukturelemente durch Verringern der Größe ist eine Möglichkeit)" - warum optimiert der Compiler dies nicht selbst? Warum kann der Compiler Mitglieder nicht immer nach abnehmender Größe sortieren? Was ist der Vorteil, um Mitglieder unsortiert zu halten?
javapowered
Ich kenne nicht die Ursprünge, aber zum einen ist die Reihenfolge der Mitglieder entscheidend für die Netzwerkkommunikation, bei der Sie möglicherweise ganze Strukturen Byte für Byte über das Web senden möchten.
Kobrar
1
@javapowered Der Compiler kann dies je nach Sprache möglicherweise tun, obwohl ich nicht sicher bin, ob einer von ihnen dies tut. Der Grund, warum Sie dies in C nicht tun können, ist, dass es vollkommen gültig ist, Mitglieder nach Basisadresse + Offset und nicht nach Namen zu adressieren, was bedeutet, dass eine Neuordnung der Mitglieder das Programm vollständig beschädigen würde.
Dan Bechard
56

Ich kann nicht glauben, dass es darauf keine weiteren Antworten gibt. Ein klassisches Beispiel ist jedenfalls das Iterieren eines mehrdimensionalen Arrays "von innen nach außen":

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, liegt darin, 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 von [befindet 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.

1800 INFORMATIONEN
quelle
9
Zurück im College hatten wir eine Aufgabe zur Matrixmultiplikation. Es stellte sich heraus, dass es aus genau diesem Grund schneller war, zuerst eine Transponierte der "Spalten" -Matrix zu erstellen und Zeilen für Zeilen anstatt Zeilen für Spalten zu multiplizieren.
Ykaganovich
11
Tatsächlich können die meisten modernen Compiler dies selbst herausfinden (mit aktivierten Optimierungen)
Ricardo Nolde
1
@ykaganovich Das ist auch das Beispiel in Ulrich Dreppers Artikel: lwn.net/Articles/255364
Simon Stender Boisen
Ich bin mir nicht sicher, ob dies immer richtig ist - wenn das gesamte Array in den L1-Cache passt (oft 32 KB!), Haben beide Aufträge die gleiche Anzahl von Cache-Treffern und -Fehlern. Vielleicht hat das Vorabrufen des Speichers einen Einfluss, denke ich. Gerne natürlich korrigiert zu werden.
Matt Parkins
Wer wird jemals die erste Version dieses Codes wählen, wenn die Reihenfolge keine Rolle spielt?
Silver_Rrocket
45

Die Grundregeln sind eigentlich ziemlich einfach. Es wird schwierig, wie sie auf Ihren Code angewendet werden.

Der Cache arbeitet 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 wahrscheinlich bald die Adresse X + 1 benötigen, wenn Sie die Daten kürzlich an Adresse X verwendet haben.

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

Dies bedeutet, dass Sie immer möchten, dass Ihr eigener Code diese beiden Lokalitätsformen so weit wie möglich ausnutzt. Springe nicht über den ganzen Speicher. Arbeiten Sie so viel wie möglich an einem kleinen Bereich und fahren Sie dann mit dem nächsten fort. Arbeiten Sie dort so viel wie möglich.

Ein einfaches Beispiel ist die 2D-Array-Durchquerung, die die Antwort von 1800 zeigte. Wenn Sie es zeilenweise durchlaufen, lesen Sie den Speicher nacheinander. Wenn Sie dies spaltenweise tun, lesen Sie einen Eintrag, springen dann zu einer völlig anderen Stelle (dem Anfang der nächsten Zeile), lesen einen Eintrag und springen erneut. Und wenn Sie endlich zur ersten Zeile zurückkehren, befindet sie sich 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 ändern kleine if-Anweisungen wahrscheinlich nichts (Sie überspringen nur ein paar Bytes, sodass Sie immer noch im zwischengespeicherten Bereich landen), aber Funktionsaufrufe implizieren normalerweise, dass Sie zu einem völlig anderen springen Adresse, die möglicherweise nicht zwischengespeichert wird. Es sei denn, es wurde kürzlich aufgerufen.

Die Verwendung des Anweisungscaches ist jedoch in der Regel weitaus weniger problematisch. Worüber Sie sich normalerweise Sorgen machen müssen, ist der Datencache.

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

Und wenn Sie mehrere Kerne ausnutzen möchten, kann dies sehr interessant werden, da normalerweise jeweils nur eine CPU eine bestimmte 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.

jalf
quelle
4
+1, gute und praktische Ratschläge. Ein Zusatz: Zeitlokalität und Raumlokalität zusammen legen nahe, dass es beispielsweise für Matrix-Ops ratsam sein kann, sie in kleinere Matrizen aufzuteilen, die vollständig in eine Cache-Zeile passen oder deren Zeilen / Spalten in Cache-Zeilen passen. Ich erinnere mich, dass ich das zur Visualisierung von Multidim gemacht habe. Daten. Es sorgte für einen ernsthaften Tritt in die Hose. Es ist gut daran zu denken, dass der Cache mehr als eine 'Zeile' enthält;)
AndreasT
1
Sie sagen, dass jeweils nur 1 CPU eine bestimmte Adresse im L1-Cache haben kann - ich nehme an, Sie meinen eher Cache-Zeilen als Adresse. Ich habe auch von falschen Freigabeproblemen gehört, wenn mindestens eine der CPUs Schreibvorgänge ausführt, aber nicht, wenn beide nur Lesevorgänge ausführen. Mit "Zugriff" meinen Sie also eigentlich "Schreiben"?
Joseph Garvin
2
@ JosephGarvin: Ja, ich meinte schreibt. Sie haben Recht, mehrere Kerne können gleichzeitig dieselben Cache-Zeilen in ihren L1-Caches haben. Wenn jedoch ein Kern in diese Adressen schreibt, wird er in allen anderen L1-Caches ungültig und muss dann neu geladen werden, bevor sie dies tun können alles damit. Entschuldigen Sie die ungenaue (falsche) Formulierung. :)
Jalf
44

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

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

Tomi Kyöstilä
quelle
16
Sie sollten eine Zusammenfassung der wichtigsten Punkte aus dem Artikel hinzufügen.
Azmisov
Gute Lektüre, aber ein weiteres Buch, das hier erwähnt werden muss, ist Hennessy, Patterson, Computer Architecture, A Quantitiative Approach , das bis heute in der 5. Auflage erhältlich ist.
Haymo Kutschbach
15

Neben Datenzugriffsmuster, ein wichtiger Faktor im Cache- Kommandocode ist Datengröße . Weniger Daten bedeuten, dass mehr davon in den Cache passt.

Dies ist hauptsächlich ein Faktor bei speicherausgerichteten Datenstrukturen. "Konventionelle" Weisheit besagt, 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 eines einfachen Schreibens). . Caches können dieses Argument jedoch vollständig ungültig machen.

In ähnlicher Weise verwendet ein Java-Boolesches Array ein ganzes Byte für jeden Wert, um die direkte Bearbeitung einzelner Werte zu ermöglichen. Sie können die Datengröße um den Faktor 8 reduzieren, wenn Sie tatsächliche Bits verwenden. Der Zugriff auf einzelne Werte wird jedoch viel komplexer und erfordert Bitverschiebungs- und Maskenoperationen (die BitSetKlasse 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. IIRC I hat auf diese Weise einmal eine Beschleunigung um den Faktor 2 oder 3 erreicht.

Michael Borgwardt
quelle
9

Die effektivste Datenstruktur für einen Cache ist ein Array. Caches funktionieren am besten, wenn Ihre Datenstruktur nacheinander angeordnet ist, während 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 immer neue Cache-Zeilen benötigt werden, um den Speicher mit dem zufälligen Zugriff aufzunehmen. Andererseits ist ein Algorithmus, der nacheinander durch ein Array läuft, am besten, weil:

  1. Dies gibt der CPU die Möglichkeit, vorauszulesen, z. B. spekulativ mehr Speicher in den Cache zu stellen, auf den später zugegriffen wird. Dieses Vorauslesen sorgt für einen enormen Leistungsschub.

  2. Wenn Sie eine enge Schleife über ein großes Array ausführen, 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.

Grover
quelle
@Grover: Über Ihren Punkt 2. Kann man also sagen, dass, wenn in einer engen Schleife eine Funktion für jede Schleifenzahl aufgerufen wird, sie insgesamt neuen Code abruft und einen Cache-Fehler verursacht, stattdessen, wenn Sie die Funktion als setzen können Code in der for-Schleife selbst, kein Funktionsaufruf, wäre es schneller wegen weniger Cache-Fehlern?
Goldenmean
1
Ja und nein. Die neue Funktion wird in den Cache geladen. Wenn genügend Cache-Speicherplatz vorhanden ist, hat diese Funktion bei der zweiten Iteration bereits im Cache, sodass kein Grund besteht, sie erneut zu laden. Es ist also ein Hit beim ersten Anruf. In C / C ++ können Sie den Compiler auffordern, Funktionen mithilfe geeigneter Segmente direkt nebeneinander zu platzieren.
Grover
Noch ein Hinweis: Wenn Sie aus der Schleife aufrufen und nicht genügend Cache-Speicherplatz vorhanden ist, wird die neue Funktion unabhängig davon in den Cache geladen. Es kann sogar vorkommen, dass die ursprüngliche Schleife aus dem Cache geworfen wird. In diesem Fall fallen für den Anruf bis zu drei Strafen für jede Iteration an: eine zum Laden des Anrufziels und eine zum erneuten Laden der Schleife. Und ein dritter, wenn sich der Schleifenkopf nicht in derselben Cache-Zeile befindet wie die Anrufrücksprungadresse. In diesem Fall benötigt das Springen zum Schleifenkopf auch einen neuen Speicherzugriff.
Grover
8

Ein Beispiel, das ich in einer Spiel-Engine gesehen habe, war das Verschieben von Daten aus Objekten in ihre eigenen Arrays. An ein Spielobjekt, das der Physik unterworfen war, sind möglicherweise auch viele andere Daten angehängt. Während der Physik-Update-Schleife kümmerte sich der Motor jedoch 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 verletzte dies objektorientierte Entwurfsmuster, aber es machte den Code viel schneller, indem Daten nahe beieinander platziert wurden, die in denselben Schleifen bearbeitet werden mussten.

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

Zan Lynx
quelle
2
+1 Überhaupt nicht veraltet. Dies ist der beste Weg, um Daten für Spiel-Engines zu organisieren - Datenblöcke zusammenhängend zu machen und alle vorgegebenen Operationen (z. B. KI) auszuführen, bevor Sie mit der nächsten fortfahren (z. B. Physik), um die Cache-Nähe / -Lokalität von zu nutzen Referenz.
Ingenieur
Ich habe dieses genaue Beispiel vor ein paar Wochen in einem Video gesehen, habe aber seitdem den Link dazu verloren / kann mich nicht erinnern, wie ich es finden soll. Erinnern Sie sich, wo Sie dieses Beispiel gesehen haben?
wird
@will: Nein, ich erinnere mich nicht genau, wo das war.
Zan Lynx
Dies ist die Idee eines Entitätskomponentensystems (ECS: en.wikipedia.org/wiki/Entity_component_system ). Speichern Sie Daten als Struktur von Arrays und nicht als die traditionelleren Arrays von Strukturen, die OOP-Praktiken fördern.
BuschnicK
7

Es wurde nur ein Beitrag darauf angesprochen, aber beim Austausch von Daten zwischen Prozessen tritt ein großes Problem auf. Sie möchten vermeiden, dass mehrere Prozesse gleichzeitig versuchen, dieselbe Cache-Zeile zu ändern. Hier ist auf "falsche" Freigabe zu achten, 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 zwischen Prozessor-Caches, die die Daten auf einem Multiprozessorsystem gemeinsam nutzen, unnötig hin und her verschoben werden. Eine Möglichkeit, dies zu vermeiden, besteht darin, Datenstrukturen auszurichten und aufzufüllen, um sie in verschiedenen Zeilen zu platzieren.

RussellH
quelle
7

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, also machte ich 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 forgetauschten Schleifen.

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

Ich habe verwendet gcc -O2und trotzdem wurden die Loops nicht optimiert. Der Kommentar von Ricardo, dass "die meisten modernen Compiler dies selbst herausfinden können", trifft nicht zu

Jakub M.
quelle
Ich bin mir nicht sicher, ob ich das verstehe. In beiden Beispielen greifen Sie weiterhin auf jede Variable in der for-Schleife zu. Warum ist einer Weg schneller als der andere?
ed-
letztendlich intuitiv für mich zu verstehen, wie es sich auswirkt :)
Laie
@ EdwardCorlew Es liegt an der Reihenfolge, in der auf sie zugegriffen wird. Die y-erste Ordnung ist schneller, da sie nacheinander auf die Daten zugreift. Wenn der erste Eintrag angefordert wird, lädt der L1-Cache eine gesamte Cache-Zeile, die den angeforderten int plus die nächsten 15 enthält (unter der Annahme einer 64-Byte-Cache-Zeile), sodass kein CPU-Stall auf die nächsten 15 wartet. Das x Die erste Reihenfolge ist langsamer, da das Element, auf das zugegriffen wird, nicht sequentiell ist und vermutlich N groß genug ist, dass sich der Speicher, auf den zugegriffen wird, immer außerhalb des L1-Cache befindet und daher jede Operation blockiert.
Matt Parkins
4

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

Andrew
quelle
@ Andrew: Wie wäre es mit Strukturen. Sind sie effizient im Cache? Haben sie Größenbeschränkungen, um Cache-effizient zu sein?
Goldenmean
Eine Struktur ist ein einzelner Speicherblock. Solange sie die Größe Ihres Caches nicht überschreitet, werden keine Auswirkungen angezeigt. Nur wenn Sie über eine Sammlung von Strukturen (oder Klassen) verfügen, werden Cache-Treffer angezeigt. Dies hängt davon ab, wie Sie die Sammlung organisieren. Ein Array stößt die Objekte gegeneinander an (gut), aber eine verknüpfte Liste kann Objekte im gesamten Adressraum mit Verknüpfungen zwischen ihnen enthalten, was offensichtlich die Cache-Leistung beeinträchtigt.
Andrew
Eine Möglichkeit, verknüpfte Listen zu verwenden, ohne den Cache zu schließen, ist am effektivsten für nicht große Listen, indem Sie einen eigenen Speicherpool erstellen, dh ein großes Array zuweisen. Anstatt den Speicher für jedes kleine verknüpfte Listenmitglied, das an einer völlig anderen Stelle im Speicher zugewiesen werden kann, zu "mallocieren" (oder "neu" in C ++ zu machen) und Speicherplatz zu verschwenden, geben Sie ihm Speicher aus Ihrem Speicherpool. Wenn Sie die Wahrscheinlichkeit, dass Mitglieder der Liste logisch geschlossen werden, stark erhöhen, werden sie gemeinsam im Cache gespeichert.
Liran Orevi
Sicher, aber es ist eine Menge Arbeit, std :: list <> et al. um Ihre benutzerdefinierten Speicherblöcke zu verwenden. Als ich ein junger Whippersnapper war, bin ich diesen Weg absolut gegangen, aber heutzutage ... zu viele andere Dinge, um sie anzugehen.
Andrew
4

Der Cache ist in "Cache-Zeilen" angeordnet und der (echte) Speicher wird aus Blöcken dieser Größe gelesen und in diese geschrieben.

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

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

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

Alnitak
quelle
nicht unbedingt. Sei nur vorsichtig mit falschem Teilen. Manchmal müssen Sie Daten in verschiedene Cache-Zeilen aufteilen. Wie effektiv der Cache ist, hängt immer davon ab, wie Sie ihn verwenden.
DAG
4

Wenn Sie fragen, wie Sie einen Code erstellen, der für den Cache effektiv ist, und die meisten anderen Fragen, müssen Sie normalerweise fragen, wie Sie ein Programm optimieren. Dies liegt daran, dass 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 gibt es einige gute Antworten. In Bezug auf Bücher empfehle ich zu Computersystemen: Eine Programmiererperspektive, die einen feinen Text über die ordnungsgemäße Verwendung des Caches enthält.

(btw - so schlimm wie eine Cache-Miss sein kann, gibt es noch schlimmer - wenn ein Programm Paging von der Festplatte ...)

Liran Orevi
quelle
4

Es gab viele Antworten auf allgemeine Hinweise wie Datenstrukturauswahl, Zugriffsmuster usw. Hier möchte ich ein weiteres Code-Entwurfsmuster hinzufügen, das als Software-Pipeline bezeichnet wird und die aktive Cache-Verwaltung nutzt.

Die Idee stammt aus anderen Pipelining-Techniken, z. B. dem Pipelining von CPU-Anweisungen.

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

  1. könnte in vernünftige mehrere Unterschritte unterteilt werden, S [1], S [2], S [3], ... deren Ausführungszeit in etwa mit der RAM-Zugriffszeit (~ 60-70 ns) vergleichbar ist.
  2. Nimmt eine Reihe von Eingaben vor 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 möchte der Code:

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 Aufwand für Funktionsaufrufe zu amortisieren und die Lokalität des Code-Cache 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 der RAM-Zugriffszeit entspricht:

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) fordert die CPU auf, die Eingabe [1] in den Cache vorab abzurufen, wobei der Prefetch-Befehl P-Zyklen selbst benötigt und zurückkehrt und im Hintergrund die Eingabe [1] nach R-Zyklen im Cache ankommt.
  2. works_on (0) Cold Miss auf 0 und arbeitet daran, was M dauert
  3. Prefetch (2) gibt einen weiteren Abruf aus
  4. works_on (1) Wenn P + R <= M ist, sollten sich die Eingaben [1] bereits vor diesem Schritt im Cache befinden, um einen Datencache-Fehler zu vermeiden
  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 Latenz des Speicherzugriffs übereinstimmen und Sie nur wenig Code- / Daten-Cache-Fehler erleiden. Dieser Prozess muss jedoch mit vielen Experimenten abgestimmt werden, um die richtige Gruppierung von Schritten und die Vorabrufzeit herauszufinden. Aufgrund des erforderlichen Aufwands wird die Verarbeitung von Daten / Paketströmen mit hoher Leistung verstärkt. 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 in die Warteschlange stellen.

Weitere Informationen finden Sie unter:

https://software.intel.com/en-us/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

Wei Shen
quelle
1

Schreiben Sie Ihr Programm so, dass es eine minimale Größe hat. Aus diesem Grund ist es nicht immer eine gute Idee, -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 jeweils mit kleinen Datenblöcken. Aus diesem Grund können weniger effiziente Sortieralgorithmen schneller ausgeführt werden als Quicksort, wenn der Datensatz groß ist. Finden Sie Möglichkeiten, Ihre größeren Datensätze in kleinere aufzuteilen. Andere haben dies vorgeschlagen.

Um die zeitliche / räumliche Lokalität von Anweisungen besser auszunutzen, 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.

Sybreon
quelle
Interessanter Punkt. Treffen Vorausschau-Caches Annahmen, die auf der Richtung einer Schleife / eines Durchlaufs durch den Speicher basieren?
Andrew
1
Es gibt viele Möglichkeiten, spekulative Datencaches zu entwerfen. Schrittbasierte messen die "Entfernung" und "Richtung" von Datenzugriffen. Inhaltsbasierte verfolgen Verfolgungsketten. Es gibt andere Möglichkeiten, sie zu entwerfen.
Sybreon
1

Neben der Ausrichtung Ihrer Struktur und Felder möchten Sie möglicherweise auch Allokatoren verwenden, die ausgerichtete Zuordnungen unterstützen, wenn Ihre Struktur Heap zugewiesen ist. wie _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); Andernfalls kann es zu einer zufälligen falschen Freigabe kommen. Denken Sie daran, dass der Standardheap in Windows eine Ausrichtung von 16 Byte hat.

Aracntido
quelle