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

Zusätzlich zu @Marc Claesens Antwort denke ich, dass ein instruktives klassisches Beispiel für cache-unfreundlichen Code Code ist, der ein zweidimensionales C-Array (z.B. ein Bitmap-Bild) spaltenweise statt zeilenweise durchsucht.

Elemente, die in einer Zeile benachbart sind, sind auch im Speicher benachbart, sodass auf sie in Sequenz zuzugreifen bedeutet, auf sie in aufsteigender Speicherfolge zuzugreifen; dies ist cache-freundlich, da der Cache dazu neigt, zusammenhängende Speicherblöcke vorabzuholen.

Stattdessen ist der Zugriff auf solche Elemente spaltenweise cache-unfreundlich, da Elemente in derselben Spalte im Speicher voneinander entfernt sind (insbesondere ist ihr Abstand gleich der Größe der Zeile), sodass Sie beim Verwenden dieses Zugriffsmusters im Speicher herumspringen und möglicherweise die Mühe des Caches vergeuden, die Elemente in der Nähe im Speicher abzurufen.

Und alles, was es braucht, um die Leistung zu ruinieren, ist der Wechsel von

// Cache-freundliche Version - verarbeitet Pixel, die im Speicher benachbart sind
for(unsigned int y=0; y

``

zu

// Cache-unfreundliche Version - springt ohne guten Grund im Speicher herum
for(unsigned int x=0; x

`

Dieser Effekt kann in Systemen mit kleinen Caches und/oder bei der Arbeit mit großen Arrays (z.B. 10+ Megapixel 24 bpp Bilder auf aktuellen Maschinen) recht dramatisch sein (mehrere Größenordnungen in der Geschwindigkeit); aus diesem Grund ist es oft besser, wenn Sie viele vertikale Scans durchführen müssen, das Bild zuerst um 90 Grad zu drehen und die verschiedenen Analysen später durchzuführen, wodurch der cache-unfreundliche Code nur auf die Rotation beschränkt wird.

` ``

Answer 2

Die Optimierung der Cache-Nutzung hängt größtenteils von zwei Faktoren ab.

Lokalität des Verweises

Der erste Faktor (auf den andere bereits hingewiesen haben) ist die Lokalität des Verweises. Die Lokalität des Verweises hat jedoch wirklich zwei Dimensionen: Raum und Zeit.

• Räumlich

Die räumliche Dimension reduziert sich auch auf zwei Dinge: Erstens wollen wir unsere Informationen dicht verpacken, damit mehr Informationen in diesen begrenzten Speicher passen. Das bedeutet (zum Beispiel), dass Sie eine erhebliche Verbesserung der Rechenkomplexität benötigen, um Datenstrukturen auf der Basis von kleinen Knoten, die durch Zeiger verbunden sind, zu rechtfertigen.

Zweitens wollen wir Informationen, die zusammen verarbeitet werden sollen, auch zusammen platzieren. Ein typischer Cache arbeitet in "Zeilen", was bedeutet, dass beim Zugriff auf Informationen andere Informationen an benachbarten Adressen mit dem Teil, den wir berührt haben, in den Cache geladen werden. Wenn ich also ein Byte berühre, lädt der Cache vielleicht 128 oder 256 Bytes in der Nähe davon. Um dies auszunutzen, wollen Sie im Allgemeinen die Daten so anordnen, dass die Wahrscheinlichkeit maximiert wird, dass Sie auch die anderen Daten verwenden, die zur gleichen Zeit geladen wurden.

Als wirklich triviales Beispiel kann dies bedeuten, dass eine lineare Suche mit einem binären Suchalgorithmus viel wettbewerbsfähiger sein kann, als man erwarten würde. Wenn Sie also ein Element aus einer Cache-Zeile geladen haben, ist die Verwendung des restlichen Datensatzes in dieser Cache-Zeile fast kostenlos. Eine binäre Suche wird erst deutlich schneller, wenn die Daten groß genug sind, dass die binäre Suche die Anzahl der Cache-Zeilen reduziert, auf die Sie zugreifen.

• Zeit

Die Zeitdimension bedeutet, dass Sie, wenn Sie einige Operationen auf bestimmten Daten durchführen, (so viel wie möglich) alle Operationen auf diesen Daten auf einmal durchführen möchten.

Da Sie dies als C++ markiert haben, verweise ich auf ein klassisches Beispiel für ein relativ cache-unfreundliches Design: std::valarray. valarray überlädt die meisten arithmetischen Operatoren, sodass ich (zum Beispiel) a = b + c + d; sagen kann (wobei a, b, c und d alle valarrays sind), um die elementweise Addition dieser Arrays durchzuführen.

Das Problem dabei ist, dass es sich durch einen Datensatz arbeitet, die Ergebnisse in einem Zwischenspeicher speichert, sich durch einen weiteren Datensatz arbeitet usw. Mit einer großen Datenmenge verschwindet das Ergebnis einer Berechnung möglicherweise aus dem Cache, bevor es in der nächsten Berechnung verwendet wird, sodass die Daten wiederholt gelesen (und geschrieben) werden müssen, bevor das endgültige Ergebnis erzielt wird. Wenn jedes Element des endgültigen Ergebnisses etwas wie (a[n] + b[n]) * (c[n] + d[n]); sein wird, ist es im Allgemeinen besser, jedes a[n], b[n], c[n] und d[n] einmal zu lesen, die Berechnung durchzuführen, das Ergebnis zu schreiben, n zu inkrementieren und dies zu wiederholen, bis Sie fertig sind.

Zeilenfreigabe

Der zweite wesentliche Faktor ist die Vermeidung von Zeilenfreigabe. Um dies zu verstehen, müssen wir wahrscheinlich zurücktreten und uns ein wenig ansehen, wie Caches organisiert sind. Die einfachste Form des Caches ist der direkt zugeordnete Cache. Dies bedeutet, dass eine Adresse im Hauptspeicher nur an einem bestimmten Ort im Cache gespeichert werden kann. Wenn wir zwei Datenelemente verwenden, die auf denselben Speicherplatz im Cache abgebildet werden, funktioniert es schlecht - jedes Mal, wenn wir ein Datenelement verwenden, muss das andere aus dem Cache ausgeschlossen werden, um Platz für das andere zu schaffen. Der Rest des Caches kann leer sein, aber diese Elemente werden nicht andere Teile des Caches verwenden.

Um dies zu verhindern, sind die meisten Caches so genannte "set-assoziativ". In einem 4-Wege set-assoziativen Cache kann ein Element aus dem Hauptspeicher an einem von 4 verschiedenen Orten im Cache gespeichert werden. Wenn also der Cache ein Element laden soll, sucht er das zuletzt verwendete Element unter diesen vier, löscht es in den Hauptspeicher und lädt das neue Element an seiner Stelle.

Das Problem ist wahrscheinlich ziemlich offensichtlich: Für einen direkt zugeordneten Cache können zwei Operanden, die zufällig auf dieselbe Cache-Position abgebildet werden, zu Fehlverhalten führen. Ein N-Wege set-assoziativer Cache erhöht die Anzahl von 2 auf N+1. Die Organisation eines Caches in mehr "Ways" erfordert zusätzliche Schaltungsteile und läuft im Allgemeinen langsamer, sodass (zum Beispiel) ein 8192-Wege assoziativer Cache auch selten eine gute Lösung ist.

Letztendlich ist dieser Faktor jedoch in portierbarem Code schwieriger zu kontrollieren. Ihre Kontrolle darüber, wo Ihre Daten platziert werden, ist normalerweise ziemlich begrenzt. Schlimmer noch, die genaue Zuordnung von Adresse zu Cache variiert zwischen ansonsten ähnlichen Prozessoren. In einigen Fällen kann es jedoch sinnvoll sein, Dinge wie die Zuweisung eines großen Puffers und die Verwendung nur von Teilen von dem, was Sie zugewiesen haben, zu tun, um sicherzustellen, dass Daten nicht dieselben Cache-Zeilen teilen (obwohl Sie wahrscheinlich den genauen Prozessor erkennen und entsprechend handeln müssen, um dies zu tun).

• Falsches Teilen

Es gibt noch einen anderen verwandten Punkt namens "falsches Teilen". Dies tritt in einem Multiprozessor- oder Mehrkernsystem auf, bei dem zwei (oder mehr) Prozessoren/Kerne Daten haben, die getrennt sind, aber in derselben Cache-Zeile liegen. Dies zwingt die beiden Prozessoren/Kerne dazu, ihren Zugriff auf die Daten zu koordinieren, obwohl jeder sein eigenes, separates Datenelement hat. Besonders wenn die beiden die Daten abwechselnd ändern, kann dies zu einer massiven Verlangsamung führen, da die Daten ständig zwischen den Prozessoren hin und hergeschoben werden müssen. Dies kann nicht einfach durch die Organisation des Caches in mehr "Wege" oder dergleichen geheilt werden. Der Hauptweg, dies zu verhindern, besteht darin sicherzustellen, dass zwei Threads selten (am besten nie) Daten ändern, die sich möglicherweise in derselben Cache-Zeile befinden (mit denselben Einschränkungen hinsichtlich der Schwierigkeit der Kontrolle der Adressen, an denen Daten zugewiesen werden).

---

1. Diejenigen, die sich gut mit C++ auskennen, könnten sich fragen, ob dies durch etwas wie Ausdrucksvorlagen optimiert werden könnte. Ich bin mir ziemlich sicher, dass die Antwort ja lautet und dass es, wenn dies geschehen würde, wahrscheinlich ein ziemlich großer Gewinn wäre. Ich kenne jedoch niemanden, der das getan hat, und angesichts der geringen Verwendung von valarray, wäre ich zumindest ein wenig überrascht, wenn das jemand tun würde.

2. Falls sich jemand fragt, wie valarray (speziell für die Leistung konzipiert) so falsch sein könnte, kommt dies auf eine Sache an: Es wurde wirklich für Rechner wie die älteren Crays entworfen, die schnellen Hauptspeicher und keinen Cache verwendet haben. Für sie war dies wirklich ein nahezu ideales Design.

3. Ja, ich vereinfache: Die meisten Caches messen den zuletzt verwendeten Eintrag nicht wirklich genau, sondern verwenden eine Heuristik, die beabsichtigt ist, dem nahe zu kommen, ohne für jeden Zugriff einen vollständigen Zeitstempel zu halten.

Answer 3

Willkommen in der Welt des datenorientierten Designs. Das Grundmantra ist Sortieren, Zweige eliminieren, Batchen, virtual-Aufrufe eliminieren - alles Schritte zur besseren Lokalität.

Da Sie die Frage mit C++ getaggt haben, hier ist das obligatorische typische C++-Geschwätz. Tony Albrechts Fallstricke der objektorientierten Programmierung sind auch eine großartige Einführung in das Thema.

Answer 4

Nur aufschichten: das klassische Beispiel für cache-unfreundlichen gegenüber cache-freundlichem Code ist das "Cache-Blocking" der Matrixmultiplikation.

Naive Matrixmultiplikation sieht so aus:

for(i=0;i

``

Wenn N groß ist, z.B. wenn N * sizeof(elemType) größer ist als die Cache-Größe, dann wird jeder Zugriff auf src2[k][j] ein Cache-Miss sein.

Es gibt viele verschiedene Möglichkeiten, dies für einen Cache zu optimieren. Hier ist ein sehr einfaches Beispiel: Anstatt in der inneren Schleife nur ein Element pro Cache-Zeile zu lesen, alle Elemente verwenden:

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i

`

Wenn die Cache-Zeilenlänge 64 Bytes beträgt und wir mit 32-Bit (4-Byte) floats arbeiten, dann gibt es 16 Elemente pro Cache-Zeile. Und die Anzahl der Cache-Misses wird durch diese einfache Transformation ungefähr um das 16-fache reduziert.

Fortgeschrittenere Transformationen arbeiten mit 2D-Kacheln, optimieren für mehrere Caches (L1, L2, TLB) usw.

Einige Ergebnisse einer Google-Suche zu "Cache-Blocking":

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

Ein schönes Video-Animation eines optimierten Cache-Blocking-Algorithmus.

http://www.youtube.com/watch?v=IFWgwGMMrh0

Schleifenkachelung ist sehr eng verwandt:

http://en.wikipedia.org/wiki/Loop_tiling

` ``

Answer 5

Heutzutage arbeiten Prozessoren mit vielen Ebenen von sich überschneidenden Speicherbereichen. Die CPU verfügt über eine Menge Speicher, der sich auf dem CPU-Chip selbst befindet. Sie hat sehr schnellen Zugriff auf diesen Speicher. Es gibt unterschiedliche Cache-Ebenen, wobei jede langsameren Zugriff (und größer) hat als die nächste, bis man zum Systemspeicher gelangt, der sich nicht auf der CPU befindet und relativ langsamer zu erreichen ist.

Vom logischen Standpunkt aus bezieht sich die Befehlssatz der CPU einfach auf Speicheradressen in einem riesigen virtuellen Adressraum. Wenn man auf eine einzelne Speicheradresse zugreift, wird die CPU diese abrufen. Früher hat sie nur diese eine Adresse abgerufen. Heutzutage wird die CPU jedoch eine Menge Speicher um das Bit herum abrufen, nach dem man gefragt hat, und es in den Cache kopieren. Sie geht davon aus, dass wenn man nach einer bestimmten Adresse fragt, es sehr wahrscheinlich ist, dass man nach einer Adresse in der Nähe gefragt wird. Zum Beispiel, wenn man einen Puffer kopiert, liest und schreibt man von aufeinanderfolgenden Adressen - direkt hintereinander.

Daher überprüft die CPU heute, wenn man auf eine Adresse zugreift, den Cache der ersten Ebene, um zu sehen, ob sie diese Adresse bereits in den Cache geladen hat. Findet sie sie nicht, handelt es sich um einen Cache-Fehler und sie muss zur nächsten Cache-Ebene gehen, um sie zu finden, bis sie schließlich in den Hauptspeicher gehen muss.

Cache-freundlicher Code versucht, Zugriffe nah beieinander im Speicher zu halten, um Cache-Fehler zu minimieren.

Ein Beispiel wäre, wenn man sich vorstellen würde, man wollte eine riesige zweidimensionale Tabelle kopieren. Sie ist so organisiert, dass jede Zeile aufeinanderfolgend im Speicher steht und eine Zeile direkt auf die nächste folgt.

Wenn man die Elemente von links nach rechts, eine Reihe nach der anderen, kopiert - das wäre Cache-freundlich. Wenn man sich entschieden hätte, die Tabelle spalte für Spalte zu kopieren, würde man dieselbe Menge Speicher kopieren - aber es wäre cache-unfreundlich.