wake-up-neo.com

Was ist ein "Cache-freundlicher" Code?

Was ist der Unterschied zwischen "Cache-unfreundlicher Code" und "Cache-freundlicher Code"?

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

687
Alex

Vorbereitungen

Auf modernen Computern können nur die Speicherstrukturen der untersten Ebene (die - Register ) Daten in einzelnen Taktzyklen verschieben. Register sind jedoch sehr teuer und die meisten Computerkerne haben weniger als ein paar Dutzend Register (einige hundert bis vielleicht tausend Bytes insgesamt). Am anderen Ende des Speicherspektrums (DR) ist der Speicher millionenfach sehr billig (dh buchstäblich billiger ), benötigt aber Hunderte von Zyklen nach einer Anfrage, um die Daten zu erhalten. Um diese Lücke zwischen super schnell und teuer und super langsam und billig zu schließen, sind die Cache-Speicher mit den Bezeichnungen L1, L2, L3 in abnehmender Geschwindigkeit und Kosten. Die Idee ist, dass der Großteil des ausführenden Codes häufig auf einen kleinen Satz von Variablen trifft und der Rest (ein viel größerer Satz von Variablen) selten. Wenn der Prozessor die Daten im L1-Cache nicht finden kann, sucht er im L2-Cache. Wenn nicht, dann L3-Cache und wenn nicht, Hauptspeicher. Jeder dieser "Fehler" ist zeitaufwendig.

(Die Analogie ist Cache-Speicher ist zum Systemspeicher, da Systemspeicher zu Festplattenspeicher ist. Festplattenspeicher ist super billig, aber sehr langsam).

Caching ist eine der Hauptmethoden, um den Einfluss der Latenz zu verringern. Um Herb Sutter zu paraphrasieren (vgl. Links unten): Die Erhöhung der Bandbreite ist einfach, aber wir können uns keinen Weg aus der Latenz herauskaufen .

Daten werden immer über die Speicherhierarchie abgerufen (kleinste == schnellste bis langsamste). Ein Cachetreffer/-fehler bezieht sich normalerweise auf einen Treffer/Fehler in der höchsten Cache-Ebene der CPU - mit höchster Ebene meine ich die größte == langsamste. Die Cache-Trefferrate ist entscheidend für die Leistung, da jeder Cache-Fehler zum Abrufen von Daten aus RAM (oder schlechter ...) führt, was a dauert viel Zeit (Hunderte von Zyklen für RAM, Dutzende von Millionen von Zyklen für HDD). Im Vergleich dazu dauert das Lesen von Daten aus dem Cache (der höchsten Ebene) in der Regel nur eine Handvoll Zyklen.

In modernen Computerarchitekturen verlässt der Leistungsengpass den CPU-Chip (z. B. Zugriff auf RAM oder höher). Dies wird sich mit der Zeit nur verschlimmern. Die Erhöhung der Prozessorfrequenz ist derzeit für die Leistungssteigerung nicht mehr relevant. Das Problem ist der Speicherzugriff. Daher konzentrieren sich die Bemühungen beim Hardware-Design in CPUs derzeit stark auf die Optimierung von Caches, Prefetching, Pipelines und Parallelität. Zum Beispiel geben moderne CPUs rund 85% des Chips für Caches und bis zu 99% für das Speichern/Verschieben von Daten aus!

Zu diesem Thema gibt es viel zu sagen. Hier sind einige gute Referenzen zu Caches, Speicherhierarchien und der richtigen Programmierung:

Hauptkonzepte für Cache-freundlichen Code

Ein sehr wichtiger Aspekt des Cache-freundlichen Codes ist das Prinzip der Lokalität, dessen Ziel es ist, in Beziehung zu setzen Daten werden im Speicher geschlossen, um ein effizientes Caching zu ermöglichen. Im Hinblick auf den CPU-Cache ist es wichtig, die Cache-Zeilen zu kennen, um zu verstehen, wie dies funktioniert: Wie funktionieren Cache-Zeilen?

Die folgenden besonderen Aspekte sind für die Optimierung des Cachings von großer Bedeutung:

  1. Temporäre Lokalität : Wenn auf einen bestimmten Speicherort zugegriffen wurde, ist es wahrscheinlich, dass in naher Zukunft wieder auf denselben Speicherort zugegriffen wird. Idealerweise werden diese Informationen zu diesem Zeitpunkt noch zwischengespeichert.
  2. Raumlokalität : Dies bezieht sich auf die räumliche Nähe von zugehörigen Daten. Caching findet auf vielen Ebenen statt, nicht nur in der CPU. Wenn Sie beispielsweise aus dem RAM lesen, wird in der Regel ein größerer Teil des Speichers abgerufen, als speziell angefordert wurde, da das Programm diese Daten sehr oft in Kürze benötigt. HDD-Caches folgen der gleichen Denkrichtung. Speziell für CPU-Caches ist der Begriff Cache-Zeilen wichtig.

Verwenden Sie geeignete c ++ Container

Ein einfaches Beispiel für Cache-freundlich und Cache-unfreundlich ist c ++ 's std::vector versus std::list. Elemente eines std::vector werden in einem zusammenhängenden Speicher abgelegt, und daher ist der Zugriff auf sie viel cachefreundlicher als der Zugriff auf Elemente in einem std::list, in dem gespeichert wird sein Inhalt überall. Dies liegt an der räumlichen Lokalität.

Ein sehr schönes Beispiel dafür gibt Bjarne Stroustrup in dieser Youtube-Clip (Danke an @Mohammad ALi Baydoun für den Link!).

Vernachlässigen Sie nicht den Cache in der Datenstruktur und im Algorithmus-Design

Versuchen Sie nach Möglichkeit, Ihre Datenstrukturen und die Reihenfolge der Berechnungen so anzupassen, dass der Cache maximal genutzt wird. Eine in dieser Hinsicht gebräuchliche Technik ist Cache-Blockierung(Archive.org-Version) , was im Hochleistungs-Computing von äußerster Wichtigkeit ist (vgl. Zum Beispiel ATLAS ).

Die implizite Struktur von Daten kennen und ausnutzen

Ein anderes einfaches Beispiel, das viele Leute auf dem Gebiet manchmal vergessen, ist Spaltenmajor (z. B. fortran , matlab ) vs. Zeilenmajor (z. B. c , c ++ ) zum Speichern zweidimensionaler Arrays. Betrachten Sie beispielsweise die folgende Matrix:

1 2
3 4

In der Zeilen-Hauptreihenfolge wird dies im Speicher als 1 2 3 4 gespeichert. In der Hauptreihenfolge der Spalten wird dies als 1 3 2 4 gespeichert. Es ist leicht zu erkennen, dass Implementierungen, die diese Reihenfolge nicht ausnutzen, schnell zu (leicht vermeidbaren!) Cache-Problemen führen. Leider sehe ich solche Dinge sehr oft in meinem Bereich (maschinelles Lernen). @MatteoItalia hat dieses Beispiel in seiner Antwort genauer gezeigt.

Wenn ein bestimmtes Element einer Matrix aus dem Speicher abgerufen wird, werden auch Elemente in dessen Nähe abgerufen und in einer Cache-Zeile gespeichert. Wenn die Reihenfolge ausgenutzt wird, führt dies zu weniger Speicherzugriffen (da sich die nächsten Werte, die für nachfolgende Berechnungen benötigt werden, bereits in einer Cache-Zeile befinden).

Der Einfachheit halber wird angenommen, dass der Cache eine einzelne Cache-Zeile umfasst, die zwei Matrixelemente enthalten kann, und dass beim Abrufen eines bestimmten Elements aus dem Speicher auch das nächste Element vorhanden ist. Nehmen wir an, wir wollen die Summe über alle Elemente in der obigen Beispiel-Matrix 2x2 nehmen (nennen wir es M):

Ausnutzen der Reihenfolge (z. B. Ändern des Spaltenindex zuerst in c ++ ):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

Nicht ausnutzen der Reihenfolge (z. B. Ändern des Zeilenindex zuerst in c ++ ):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

In diesem einfachen Beispiel verdoppelt sich durch Ausnutzung der Reihenfolge die Ausführungsgeschwindigkeit ungefähr (da der Speicherzugriff viel mehr Zyklen erfordert als die Berechnung der Summen). In der Praxis kann der Leistungsunterschied viel größer sein.

Vermeiden Sie unvorhersehbare Verzweigungen

Moderne Architekturen verfügen über Pipelines, und Compiler können Code immer besser neu anordnen, um Verzögerungen aufgrund des Speicherzugriffs zu minimieren. Wenn Ihr kritischer Code (unvorhersehbare) Zweige enthält, ist es schwierig oder unmöglich, Daten vorab abzurufen. Dies führt indirekt zu mehr Cache-Fehlern.

Dies wird hier sehr gut erklärt (danke an @ 0x90 für den Link): Warum verarbeitet ein sortiertes Array schneller als ein unsortiertes Array?

Vermeiden Sie virtuelle Funktionen

Im Kontext von c ++ stellen virtual Methoden ein kontroverses Problem in Bezug auf Cache-Fehler dar (es besteht ein allgemeiner Konsens, dass sie in Bezug auf die Leistung nach Möglichkeit vermieden werden sollten). Virtuelle Funktionen können beim Nachschlagen zu Cache-Fehlern führen. Dies geschieht jedoch nur dann , wenn die bestimmte Funktion nicht häufig aufgerufen wird (andernfalls würde sie wahrscheinlich zwischengespeichert werden). Dies wird daher als nicht angesehen -ausgabe von einigen. Informationen zu diesem Problem finden Sie unter: Wie hoch sind die Leistungskosten einer virtuellen Methode in einer C++ - Klasse?

Allgemeine Probleme

Ein häufiges Problem in modernen Architekturen mit Multiprozessor-Caches ist false sharing . Dies tritt auf, wenn jeder einzelne Prozessor versucht, Daten in einem anderen Speicherbereich zu verwenden und diese in derselben Cache-Zeile zu speichern. Dadurch wird die Cache-Zeile, die Daten enthält, die ein anderer Prozessor verwenden kann, immer wieder überschrieben. Tatsächlich lassen sich verschiedene Threads gegenseitig warten, indem sie in dieser Situation Cache-Fehler auslösen. Siehe auch (danke an @Matt für den Link): Wie und wann auf die Cache-Zeilengröße ausrichten?

Ein extremes Symptom für schlechtes Caching im RAM Speicher (was in diesem Zusammenhang wahrscheinlich nicht gemeint ist) ist das sogenannte Thrashing . Dies tritt auf, wenn der Prozess kontinuierlich Seitenfehler erzeugt (z. B. Zugriffe auf Speicher, der sich nicht auf der aktuellen Seite befindet), die Plattenzugriff erfordern.

894
Marc Claesen

Zusätzlich zur Antwort von @Marc Claesen 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 abtastet.

Elemente, die in einer Reihe benachbart sind, sind auch im Speicher benachbart, so dass auf sie in aufsteigender Speicherreihenfolge zugegriffen wird; Dies ist cachefreundlich, da der Cache dazu neigt, zusammenhängende Speicherblöcke vorab abzurufen.

Stattdessen ist der spaltenweise Zugriff auf solche Elemente Cache-unfreundlich, da Elemente in derselben Spalte im Speicher voneinander entfernt sind (insbesondere entspricht ihr Abstand der Zeilengröße). Wenn Sie also dieses Zugriffsmuster verwenden, springen im Speicher herum und verschwenden möglicherweise den Aufwand des Caches, um die in der Nähe befindlichen Elemente im Speicher abzurufen.

Und alles, was es braucht, um die Leistung zu ruinieren, ist zu gehen

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

zu

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

Dieser Effekt kann in Systemen mit kleinen Caches und/oder großen Arrays (z. B. Bildern mit mehr als 10 Megapixeln und 24 bpp auf aktuellen Computern) sehr dramatisch sein (mehrere Größenordnungen der Geschwindigkeit). Aus diesem Grund ist es bei vielen vertikalen Scans oft besser, zuerst das Bild um 90 Grad zu drehen und später die verschiedenen Analysen durchzuführen, um den Cache-unfreundlichen Code auf die Drehung zu beschränken.

136
Matteo Italia

Die Optimierung der Cache-Nutzung hängt hauptsächlich von zwei Faktoren ab.

Bezugsort

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

  • Räumlich

Die räumliche Dimension hängt auch von zwei Dingen ab: Erstens möchten wir unsere Informationen dicht packen, damit mehr Informationen in diesen begrenzten Speicher passen. Dies bedeutet beispielsweise, dass Sie die Rechenkomplexität erheblich verbessern müssen, um Datenstrukturen basierend auf kleinen Knoten, die durch Zeiger verbunden sind, zu rechtfertigen.

Zweitens wollen wir Informationen, die gemeinsam verarbeitet werden, auch gemeinsam lokalisieren. Ein typischer Cache funktioniert in "Zeilen", dh, wenn Sie auf einige Informationen zugreifen, werden andere Informationen an in der Nähe befindlichen Adressen mit dem von uns berührten Teil in den Cache geladen. Wenn ich beispielsweise ein Byte berühre, lädt der Cache möglicherweise 128 oder 256 Bytes in der Nähe dieses Bytes. Um dies zu nutzen, möchten Sie im Allgemeinen, dass die Daten so angeordnet werden, dass die Wahrscheinlichkeit maximiert wird, dass Sie auch die anderen Daten verwenden, die gleichzeitig geladen wurden.

Für ein wirklich triviales Beispiel kann dies bedeuten, dass eine lineare Suche mit einer binären Suche viel wettbewerbsfähiger ist, als Sie es erwarten würden. Sobald Sie ein Element aus einer Cache-Zeile geladen haben, ist die Verwendung der restlichen Daten in dieser Cache-Zeile nahezu kostenlos. Eine binäre Suche wird nur dann spürbar schneller, wenn die Daten so groß sind, dass die Anzahl der Cache-Zeilen, auf die Sie zugreifen, durch die binäre Suche verringert wird.

  • Zeit

Die Zeitdimension bedeutet, dass Sie, wenn Sie einige Vorgänge mit einigen Daten ausführen, (so viel wie möglich) alle Vorgänge mit diesen Daten auf einmal ausführen möchten.

Da Sie dies als C++ getaggt haben, zeige ich ein klassisches Beispiel für ein relativ Cache-unfreundliches Design: std::valarray. valarray überlastet die meisten arithmetischen Operatoren, also kann ich (zum Beispiel) sagen a = b + c + d; (wobei a, b, c und d alle sind valarrays), um diese Arrays elementweise zu addieren.

Das Problem dabei ist, dass ein Eingangspaar durchlaufen wird, die Ergebnisse temporär abgelegt werden, ein anderes Eingangspaar durchlaufen wird und so weiter. Bei vielen Daten wird das Ergebnis einer Berechnung möglicherweise aus dem Cache entfernt, bevor es für die nächste Berechnung verwendet wird. Daher werden die Daten wiederholt gelesen (und geschrieben), bevor das endgültige Ergebnis vorliegt. Wenn jedes Element des Endergebnisses so etwas wie (a[n] + b[n]) * (c[n] + d[n]); ist, möchten wir im Allgemeinen jeden a[n], b[n], c[n] und d[n] einmal lesen. Berechnen Sie, schreiben Sie das Ergebnis, erhöhen Sie n und wiederholen Sie, bis wir fertig sind.2

Line Sharing

Der zweite wichtige Faktor ist das Vermeiden der gemeinsamen Nutzung von Leitungen. Um dies zu verstehen, müssen wir uns wahrscheinlich ein wenig mit der Organisation der Caches befassen. Die einfachste Form des Cache wird direkt zugeordnet. Dies bedeutet, dass eine Adresse im Hauptspeicher nur an einer bestimmten Stelle im Cache gespeichert werden kann. Wenn wir zwei Datenelemente verwenden, die derselben Stelle im Cache zugeordnet sind, funktioniert dies schlecht. Jedes Mal, wenn wir ein Datenelement verwenden, muss das andere aus dem Cache gelöscht werden, um Platz für das andere zu schaffen. Der Rest des Caches ist möglicherweise leer, diese Elemente verwenden jedoch keine anderen Teile des Caches.

Um dies zu verhindern, werden die meisten Caches als "satzassoziativ" bezeichnet. Beispielsweise kann in einem 4-Wege-Satz-Assoziativ-Cache jedes Element aus dem Hauptspeicher an einer von 4 verschiedenen Stellen im Cache gespeichert werden. Wenn der Cache ein Element lädt, sucht er nach dem zuletzt verwendeten3 item unter diesen vier löscht es in den Hauptspeicher und lädt das neue Element an seiner Stelle.

Das Problem ist wahrscheinlich ziemlich offensichtlich: Bei einem direkt zugeordneten Cache können zwei Operanden, die zufällig demselben Cache-Speicherort zugeordnet sind, zu einem schlechten Verhalten führen. Ein satzassoziativer N-Wege-Cache erhöht die Zahl von 2 auf N + 1. Das Organisieren eines Caches in mehr "Wege" erfordert zusätzliche Schaltkreise und ist im Allgemeinen langsamer. Daher ist (beispielsweise) ein assoziativer Cache mit 8192-Wege-Sätzen auch selten eine gute Lösung.

Letztendlich ist dieser Faktor in portablem Code jedoch schwieriger zu kontrollieren. Ihre Kontrolle darüber, wo Ihre Daten gespeichert werden, ist normalerweise recht begrenzt. Schlimmer noch, die genaue Zuordnung von Adresse zu Cache variiert zwischen ansonsten ähnlichen Prozessoren. In einigen Fällen kann es sich jedoch lohnen, einen großen Puffer zuzuweisen und dann nur Teile der zugewiesenen Daten zu verwenden, um sicherzustellen, dass die gleichen Cache-Zeilen verwendet werden (auch wenn Sie wahrscheinlich den genauen Prozessor und den Wert ermitteln müssen) entsprechend handeln, um dies zu tun).

  • Falsches Teilen

Es gibt einen weiteren verwandten Gegenstand namens "Falsches Teilen". Dies tritt in einem Multiprozessor- oder Multicore-System auf, in dem zwei (oder mehr) Prozessoren/Kerne Daten haben, die getrennt sind, sich jedoch in derselben Cache-Zeile befinden. Dies zwingt die beiden Prozessoren/Kerne, ihren Zugriff auf die Daten zu koordinieren, obwohl jeder ein eigenes, separates Datenelement hat. Insbesondere wenn die beiden Daten abwechselnd ändern, kann dies zu einer massiven Verlangsamung führen, da die Daten ständig zwischen den Prozessoren ausgetauscht werden müssen. Dies kann nicht einfach behoben werden, indem der Cache auf mehr "Arten" oder auf ähnliche Weise organisiert wird. Die primäre Möglichkeit, dies zu verhindern, besteht darin, sicherzustellen, dass zwei Threads selten (vorzugsweise nie) Daten ändern, die sich möglicherweise in derselben Cache-Zeile befinden (mit denselben Einschränkungen hinsichtlich der Schwierigkeit, die Adressen zu steuern, denen Daten zugewiesen werden).


  1. Diejenigen, die C++ gut kennen, mögen sich fragen, ob dies über so etwas wie Ausdrucksvorlagen optimiert werden kann. Ich bin mir ziemlich sicher, dass die Antwort lautet: Ja, es könnte getan werden, und wenn es so wäre, wäre es wahrscheinlich ein ziemlich substanzieller Gewinn. Mir ist jedoch nicht bewusst, dass jemand dies getan hat, und wenn man bedenkt, wie wenig valarray sich daran gewöhnt, wäre ich zumindest ein wenig überrascht, wenn jemand dies auch sieht.

  2. Für den Fall, dass sich jemand fragt, wie valarray (speziell für die Leistung entwickelt) so schlimm falsch sein könnte, kommt es auf eine Sache an: Es wurde wirklich für Maschinen wie die älteren Crays entwickelt, die schnellen Hauptspeicher und keinen Cache verwendeten. Für sie war dies wirklich ein nahezu ideales Design.

  3. Ja, ich vereinfache: Die meisten Caches messen das zuletzt verwendete Element nicht genau, verwenden jedoch eine Heuristik, die derjenigen nahe kommt, ohne dass für jeden Zugriff ein vollständiger Zeitstempel erstellt werden muss.

84
Jerry Coffin

Willkommen in der Welt des datenorientierten Designs. Das grundlegende Mantra besteht darin, Zweige zu sortieren, zu beseitigen, Stapel zu erstellen, virtual Aufrufe zu beseitigen - alle Schritte in Richtung einer besseren Lokalität.

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

32
arul

Einfach aufhäufen: Das klassische Beispiel für cachefreundlichen versus cachefreundlichen Code ist das "Cache-Blocking" von Matrix-Multiplikation.

Naive Matrix multiplizieren sieht aus wie

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

Wenn N groß ist, z. Wenn N * sizeof(elemType) größer als die Cache-Größe ist, ist jeder einzelne Zugriff auf src2[k][j] ein Cache-Fehler.

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

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k=0;k<N;k++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

Wenn die Cache-Zeilengröße 64 Byte beträgt und 32-Bit-Floats (4 Byte) verwendet werden, gibt es 16 Elemente pro Cache-Zeile. Und die Anzahl der Cache-Fehlschläge durch diese einfache Transformation ist ungefähr 16-fach reduziert.

Fancier-Transformationen werden auf 2D-Kacheln ausgeführt und für mehrere Caches (L1, L2, TLB) usw. optimiert.

Einige Ergebnisse des Googelns "Cache-Blocking":

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

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

Eine nette Videoanimation eines optimierten Cache-Blocking-Algorithmus.

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

Loop-Tiling ist sehr eng miteinander verbunden:

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

22
Krazy Glew

Prozessoren arbeiten heute mit vielen Ebenen von kaskadierenden Speicherbereichen. Die CPU hat also eine Menge Speicher, der sich auf dem CPU-Chip selbst befindet. Es hat sehr schnellen Zugriff auf diesen Speicher. Es gibt verschiedene Cache-Ebenen, von denen jede langsamer (und größer) als die andere ist, bis Sie auf den Systemspeicher zugreifen, der sich nicht auf der CPU befindet und auf den relativ viel langsamer zugegriffen werden kann.

Der Befehlssatz der CPU bezieht sich logischerweise nur auf Speicheradressen in einem riesigen virtuellen Adressraum. Wenn Sie auf eine einzelne Speicheradresse zugreifen, ruft die CPU diese ab. Früher hat es nur diese eine Adresse geholt. Aber heute holt die CPU eine Menge Speicher um das Bit, das Sie angefordert haben, und kopiert es in den Cache. Wenn Sie nach einer bestimmten Adresse gefragt haben, ist es sehr wahrscheinlich, dass Sie sehr bald nach einer Adresse in der Nähe fragen werden. Wenn Sie zum Beispiel einen Puffer kopieren, lesen und schreiben Sie von aufeinanderfolgenden Adressen - einer nach dem anderen.

Wenn Sie heute eine Adresse abrufen, wird die erste Cache-Ebene überprüft, um festzustellen, ob diese Adresse bereits in den Cache eingelesen wurde. Wenn sie nicht gefunden wird, handelt es sich um einen Cache-Fehler, und die nächste Cache-Ebene wird aufgerufen Cache, um es zu finden, bis es schließlich in den Hauptspeicher gehen muss.

Cache-freundlicher Code versucht, die Zugriffe im Speicher eng zusammenzuhalten, damit Sie Cache-Fehler minimieren.

Stellen Sie sich als Beispiel vor, Sie wollten eine riesige zweidimensionale Tabelle kopieren. Es ist so organisiert, dass die Reach-Zeile im Speicher fortlaufend ist, und eine Zeile folgt der nächsten direkt danach.

Wenn Sie die Elemente zeilenweise von links nach rechts kopieren würden, wäre dies Cache-freundlich. Wenn Sie sich dazu entschließen, die Tabelle spaltenweise zu kopieren, kopieren Sie genau die gleiche Menge an Speicher - dies wäre jedoch ein unfreundlicher Cache.

13
Rafael Baptista

Es muss klargestellt werden, dass nicht nur Daten cachefreundlich sein sollten, sondern dass dies auch für den Code wichtig ist. Dies erfolgt zusätzlich zu der Verzweigungsvorhersage, der Neuordnung von Befehlen, der Vermeidung tatsächlicher Unterteilungen und anderer Techniken.

Je dichter der Code ist, desto weniger Cache-Zeilen sind normalerweise erforderlich, um ihn zu speichern. Dies führt dazu, dass mehr Cache-Zeilen für Daten verfügbar sind.

Der Code sollte nicht überall Funktionen aufrufen, da normalerweise eine oder mehrere eigene Cachezeilen erforderlich sind, was zu weniger Cachezeilen für Daten führt.

Eine Funktion sollte an einer Cache-Zeilenausrichtungs-freundlichen Adresse beginnen. Obwohl es (gcc) -Compiler-Schalter gibt, ist zu beachten, dass es bei sehr kurzen Funktionen möglicherweise verschwenderisch ist, wenn jeder eine ganze Cache-Zeile belegt. Wenn beispielsweise drei der am häufigsten verwendeten Funktionen in eine 64-Byte-Cache-Zeile passen, ist dies weniger verschwenderisch als wenn jede eine eigene Zeile hat und zwei Cache-Zeilen weniger für andere Zwecke verfügbar sind. Ein typischer Ausrichtungswert könnte 32 oder 16 sein.

Nehmen Sie sich also etwas Zeit, um den Code dichter zu machen. Testen Sie verschiedene Konstrukte, kompilieren und überprüfen Sie die generierte Codegröße und das generierte Profil.

4
Olof Forshell

Wie @Marc Claesen erwähnte, besteht eine der Möglichkeiten, Cache-freundlichen Code zu schreiben, darin, die Struktur auszunutzen, in der unsere Daten gespeichert sind. Darüber hinaus besteht eine weitere Möglichkeit, Cache-freundlichen Code zu schreiben: Ändern Sie die Art und Weise, in der unsere Daten gespeichert werden. Schreiben Sie dann neuen Code, um auf die in dieser neuen Struktur gespeicherten Daten zuzugreifen.

Dies ist sinnvoll, wenn Datenbanksysteme die Tupel einer Tabelle linearisieren und speichern. Es gibt zwei grundlegende Möglichkeiten, die Tupel einer Tabelle zu speichern, d. H. Zeilenspeicher und Spaltenspeicher. Wie der Name schon sagt, werden die Tupel im Zeilenspeicher zeilenweise gespeichert. Nehmen wir an, eine gespeicherte Tabelle mit dem Namen Product hat 3 Attribute, d. H. int32_t key, char name[56] und int32_t price, sodass die Gesamtgröße eines Tupels 64 Byte beträgt.

Wir können eine sehr einfache Ausführung von Zeilenspeicherabfragen im Hauptspeicher simulieren, indem wir ein Array von Product -Strukturen mit der Größe N erstellen, wobei N die Anzahl der Zeilen in der Tabelle ist. Ein solches Speicherlayout wird auch als Array von Strukturen bezeichnet. Die Struktur für Product kann also wie folgt aussehen:

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

/* create an array of structs */
Product* table = new Product[N];
/* now load this array of structs, from a file etc. */

In ähnlicher Weise können wir eine sehr einfache Ausführung von Spaltenspeicherabfragen im Hauptspeicher simulieren, indem wir 3 Arrays der Größe N erstellen, ein Array für jedes Attribut der Tabelle Product. Ein solches Speicherlayout wird auch als Struktur von Arrays bezeichnet. Die 3 Arrays für jedes Attribut von Product können also wie folgt aussehen:

/* create separate arrays for each attribute */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* now load these arrays, from a file etc. */

Nachdem wir nun sowohl das Array von Strukturen (Zeilenlayout) als auch die 3 separaten Arrays (Spaltenlayout) geladen haben, befinden sich in unserer Tabelle Product ein Zeilenspeicher und ein Spaltenspeicher.

Nun fahren wir mit dem cachefreundlichen Codeteil fort. Angenommen, die Arbeitslast in unserer Tabelle ist so, dass wir eine Aggregationsabfrage für das Preisattribut haben. Sowie

SELECT SUM(price)
FROM PRODUCT

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

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + table[i].price;

Für den Spaltenspeicher können wir die obige SQL-Abfrage in konvertieren

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + price[i];

Der Code für den Spaltenspeicher wäre in dieser Abfrage schneller als der Code für das Zeilenlayout, da nur eine Teilmenge von Attributen erforderlich ist und wir im Spaltenlayout genau das tun, d. H. Nur auf die Preisspalte zugreifen.

Angenommen, die Cache-Zeilengröße ist 64 Byte.

Beim Zeilenlayout wird beim Lesen einer Cache-Zeile der Preiswert von nur 1 (cacheline_size/product_struct_size = 64/64 = 1) Tupel gelesen, da unsere Strukturgröße von 64 Bytes unsere gesamte Cache-Zeile ausfüllt, also für jeden Tupel a Cache-Miss tritt bei einem Zeilenlayout auf.

Beim Spaltenlayout wird beim Lesen einer Cache-Zeile der Preiswert von 16 (cacheline_size/price_int_size = 64/4 = 16) Tupeln gelesen, da 16 aufeinanderfolgende Preiswerte, die im Speicher gespeichert sind, in den Cache gebracht werden, sodass für jeden sechzehnten Tupel ein Cache erstellt wird Miss tritt bei Spaltenlayout auf.

Daher ist das Spaltenlayout bei einer bestimmten Abfrage schneller und bei solchen Aggregationsabfragen für eine Teilmenge von Spalten der Tabelle schneller. Sie können ein solches Experiment mit den Daten aus TPC-H Benchmark selbst ausprobieren und die Laufzeiten für beide Layouts vergleichen. Der wikipedia Artikel über spaltenorientierte Datenbanksysteme ist auch gut.

Wenn also in Datenbanksystemen die Abfragearbeitsauslastung im Voraus bekannt ist, können wir unsere Daten in Layouts speichern, die den Abfragen in der Arbeitsauslastung entsprechen, und auf Daten aus diesen Layouts zugreifen. Im obigen Beispiel haben wir ein Spaltenlayout erstellt und unseren Code geändert, um die Summe so zu berechnen, dass er für den Cache geeignet ist.

2
user2603796

Beachten Sie, dass Caches nicht nur den fortlaufenden Speicher zwischenspeichern. Sie haben mehrere Zeilen (mindestens 4), sodass diskontinuierlicher und überlappender Speicher oft genauso effizient gespeichert werden kann.

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

0
Tuntable