Was ist der Unterschied zwischen " Cache-unfreundlichem Code " und " Cache-freundlichem " Code?

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

Vorbereitungen

Auf modernen Computern können nur die Speicherstrukturen der niedrigsten Ebene (die Register ) Daten in einzelnen Taktzyklen verschieben. Register sind jedoch sehr teuer und die meisten Computerkerne haben weniger als ein paar Dutzend Register (insgesamt einige hundert bis vielleicht tausend Bytes ). Am anderen Ende des Speicherspektrums ( DRAM ) ist der Speicher sehr billig (dh buchstäblich millionenfach billiger ), benötigt jedoch nach einer Anforderung zum Empfangen der Daten Hunderte von Zyklen. Um diese Lücke zwischen superschnell und teuer und super langsam und billig zu schließen, sind die Cache-Speicher, genannt L1, L2, L3 in abnehmender Geschwindigkeit und Kosten. Die Idee ist, dass der größte Teil des ausgeführten 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, werden sie im L2-Cache angezeigt. Wenn nicht vorhanden, dann L3-Cache und wenn nicht vorhanden, Hauptspeicher. Jeder dieser "Fehlschläge" ist zeitlich teuer.

(Die Analogie ist, dass der Cache-Speicher dem Systemspeicher entspricht, da der Systemspeicher zu fest ist. Der Festplattenspeicher ist supergünstig, aber sehr langsam.)

Caching ist eine der Hauptmethoden, um die Auswirkungen der Latenz zu verringern . Um Herb Sutter zu paraphrasieren (siehe Links unten): Die Erhöhung der Bandbreite ist einfach, aber wir können uns keinen Weg aus der Latenz heraus kaufen .

Daten werden immer über die Speicherhierarchie abgerufen (kleinste == schnellste bis langsamste). Ein Cache-Treffer / Fehler bezieht sich normalerweise auf einen Treffer / Fehler in der höchsten Cache-Ebene der CPU - mit der höchsten Ebene meine ich den größten == langsamsten. Die Cache-Trefferquote ist entscheidend für die Leistung, da jeder Cache-Fehler dazu führt, dass Daten aus dem RAM abgerufen werden (oder schlimmer noch ...), was viel Zeit in Anspruch nimmt (Hunderte von Zyklen für RAM, zig Millionen Zyklen für HDD). Im Vergleich dazu dauert das Lesen von Daten aus dem Cache (höchster Ebene) normalerweise 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 noch verschlimmern. Die Erhöhung der Prozessorfrequenz ist derzeit für die Leistungssteigerung nicht mehr relevant. Das Problem ist der Speicherzugriff. Die Bemühungen zum Hardware-Design in CPUs konzentrieren sich daher 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 großartige Referenzen zu Caches, Speicherhierarchien und der richtigen Programmierung:

• Agner Fogs Seite . In seinen hervorragenden Dokumenten finden Sie detaillierte Beispiele für Sprachen von Assembler bis C ++.
• Wenn Sie sich für Videos interessieren , empfehle ich dringend, sich Herb Sutters Vortrag über Maschinenarchitektur (Youtube) anzuschauen (insbesondere ab 12:00 Uhr!).
• Folien zur Speicheroptimierung von Christer Ericson (Director of Technology @ Sony)
• LWN.nets Artikel " Was jeder Programmierer über Speicher wissen sollte "

Hauptkonzepte für cachefreundlichen Code

Ein sehr wichtiger Aspekt des cachefreundlichen Codes ist das Prinzip der Lokalität , dessen Ziel es ist, verwandte Daten nahe am Speicher abzulegen, um ein effizientes Caching zu ermöglichen. In Bezug 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 Caching von großer Bedeutung:

1. Zeitliche Lokalität : Wenn auf einen bestimmten Speicherort zugegriffen wurde, ist es wahrscheinlich, dass in naher Zukunft erneut auf denselben Speicherort zugegriffen wird. Im Idealfall werden diese Informationen zu diesem Zeitpunkt noch zwischengespeichert.
2. Räumliche Lokalität : Dies bezieht sich auf das nahe beieinander liegende Platzieren verwandter Daten. Das Caching erfolgt auf vielen Ebenen, nicht nur in der CPU. Wenn Sie beispielsweise aus dem RAM lesen, wird normalerweise ein größerer Teil des Speichers abgerufen, als speziell angefordert wurde, da das Programm diese Daten sehr oft bald benötigt. HDD-Caches folgen dem gleichen Gedankengang. Speziell für CPU-Caches ist der Begriff der Cache-Zeilen wichtig.

Verwenden Sie entsprechend c ++ Behälter

Ein einfaches Beispiel für Cache-freundlich gegenüber Cache-unfreundlich ist c ++ist std::vectorgegen std::list. Elemente von a std::vectorwerden in einem zusammenhängenden Speicher gespeichert, und als solcher ist der Zugriff auf sie viel cachefreundlicher als der Zugriff auf Elemente in a std::list, das seinen Inhalt überall speichert. Dies ist auf die räumliche Lokalität zurückzuführen.

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

Vernachlässigen Sie nicht den Cache in Bezug auf Datenstruktur und Algorithmusdesign

Versuchen Sie nach Möglichkeit, Ihre Datenstrukturen und die Reihenfolge der Berechnungen so anzupassen, dass der Cache maximal genutzt wird. Eine in dieser Hinsicht übliche Technik ist das Blockieren des Cache (Archive.org-Version) , was beim Hochleistungsrechnen von extremer Bedeutung ist (vgl. Beispielsweise ATLAS ).

Kennen und nutzen Sie die implizite Struktur von Daten

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

1 2
3 4

In der Hauptreihenfolge wird dies im Speicher gespeichert als 1 2 3 4; in der Reihenfolge der Spaltenmajore würde dies als gespeichert 1 3 2 4. Es ist leicht zu erkennen, dass bei Implementierungen, die diese Reihenfolge nicht ausnutzen, schnell (leicht vermeidbare!) Cache-Probleme auftreten. Leider sehe ich solche Dinge sehr oft in meiner Domäne (maschinelles Lernen). @MatteoItalia hat dieses Beispiel in seiner Antwort ausführlicher gezeigt.

Beim Abrufen eines bestimmten Elements einer Matrix aus dem Speicher werden auch Elemente in der 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).

Nehmen Sie der Einfachheit halber an, dass der Cache eine einzelne Cache-Zeile umfasst, die 2 Matrixelemente enthalten kann, und dass, wenn ein bestimmtes Element aus dem Speicher abgerufen wird, auch das nächste Element abgerufen wird. Angenommen, wir möchten die Summe über alle Elemente in der obigen Beispiel-2x2-Matrix übernehmen (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

Die Reihenfolge nicht ausnutzen (z. B. zuerst den Zeilenindex ändern 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 das Ausnutzen der Reihenfolge ungefähr die Ausführungsgeschwindigkeit (da der Speicherzugriff viel mehr Zyklen erfordert als das Berechnen 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) Verzweigungen 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 ist die Verarbeitung eines sortierten Arrays schneller als die Verarbeitung eines unsortierten Arrays?

Vermeiden Sie virtuelle Funktionen

Im Zusammenhang mit c ++, virtualMethoden stellen eine umstrittene Frage in Bezug auf Cache - Misses (ein allgemeiner Konsens besteht , dass sie , wenn möglich , in Bezug auf Leistung vermieden werden sollen). Virtuelle Funktionen können beim Nachschlagen zu Cache-Fehlern führen. Dies geschieht jedoch nur, wenn die jeweilige Funktion nicht häufig aufgerufen wird (andernfalls wird sie wahrscheinlich zwischengespeichert), sodass dies von einigen als kein Problem angesehen wird. Weitere Informationen zu diesem Problem finden Sie unter: Wie hoch sind die Leistungskosten für eine virtuelle Methode in einer C ++ - Klasse?

Allgemeine Probleme

Ein häufiges Problem in modernen Architekturen mit Multiprozessor-Caches ist das falsche Teilen . Dies tritt auf, wenn jeder einzelne Prozessor versucht, Daten in einem anderen Speicherbereich zu verwenden und versucht, sie 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 verursachen. Siehe auch (danke an @Matt für den Link): Wie und wann muss die Ausrichtung auf die Cache- Zeilengröße erfolgen ?

Ein extremes Symptom für ein schlechtes Caching im RAM-Speicher (was Sie in diesem Zusammenhang wahrscheinlich nicht meinen) ist das sogenannte Thrashing . Dies tritt auf, wenn der Prozess kontinuierlich Seitenfehler generiert (z. B. Zugriff auf Speicher, der sich nicht auf der aktuellen Seite befindet), für die Festplattenzugriff erforderlich ist.

Zusätzlich zu der Antwort von @Marc Claesen denke ich, dass ein lehrreiches klassisches Beispiel für cache-unfreundlichen Code Code ist, der ein zweidimensionales C-Array (z. B. ein Bitmap-Bild) spaltenweise anstatt zeilenweise scannt.

Elemente, die in einer Reihe benachbart sind, sind auch im Speicher benachbart. Wenn Sie also nacheinander auf sie zugreifen, bedeutet dies, dass Sie in aufsteigender Speicherreihenfolge auf sie zugreifen. 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 Größe der Zeile). Wenn Sie also dieses Zugriffsmuster verwenden, werden Sie springen im Speicher herum und verschwenden möglicherweise den Aufwand des Caches, um die Elemente in der Nähe des Speichers 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 bei der Arbeit mit großen Arrays (z. B. 10+ Megapixel 24 bpp-Bilder auf aktuellen Computern) ziemlich dramatisch sein (Geschwindigkeit um mehrere Größenordnungen). Wenn Sie daher viele vertikale Scans durchführen müssen, ist es häufig besser, das Bild zuerst um 90 Grad zu drehen und später die verschiedenen Analysen durchzuführen, um den cache-unfreundlichen Code nur auf die Drehung zu beschränken.

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

Referenzort

Der erste Faktor (auf den andere bereits hingewiesen haben) ist die Bezugslokalität. Die Referenzlokalitä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 (zum Beispiel), dass Sie die Rechenkomplexität erheblich verbessern müssen, um Datenstrukturen zu rechtfertigen, die auf kleinen Knoten basieren, die durch Zeiger verbunden sind.

Zweitens möchten wir, dass Informationen, die zusammen verarbeitet werden, auch zusammen lokalisiert werden. Ein typischer Cache arbeitet in "Zeilen". Wenn Sie also auf einige Informationen zugreifen, werden andere Informationen an nahe gelegenen 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 sein kann als erwartet. 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 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 an einigen Daten ausführen, (so viel wie möglich) alle Operationen an diesen Daten gleichzeitig ausfü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Überlastungen meisten arithmetischen Operatoren, so kann ich (zum Beispiel) sagen a = b + c + d;(wo a, b, cund dsind alle valarrays) elementweise Addition dieser Arrays zu tun.

Das Problem dabei ist, dass es durch ein Paar von Eingaben geht, Ergebnisse in ein temporäres Ergebnis einfügt, durch ein anderes Paar von Eingängen geht und so weiter. Bei vielen Daten verschwindet das Ergebnis einer Berechnung möglicherweise aus dem Cache, bevor es für die nächste Berechnung verwendet wird. Daher lesen (und schreiben) wir die Daten wiederholt, bevor wir unser Endergebnis erhalten. Wenn jedes Element des Endergebnisses so etwas wie sein wird (a[n] + b[n]) * (c[n] + d[n]);, würden wir in der Regel jeweils lesen bevorzugen a[n], b[n], c[n]und d[n]einmal, tun die Berechnung, schreiben Sie das Ergebnis, erhöht nund wiederholen, bis wir fertig sind. ²

Leitungsfreigabe

Der zweite wichtige Faktor ist die Vermeidung von Leitungsfreigabe. Um dies zu verstehen, müssen wir wahrscheinlich ein wenig sichern und uns ansehen, wie Caches organisiert sind. Die einfachste Form des Cache ist die direkte Zuordnung. 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, aber diese Elemente verwenden keine anderen Teile des Caches.

Um dies zu verhindern, werden die meisten Caches als "set assoziative" 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 verwendeten ³ Element unter diesen vier, leert es in den Hauptspeicher und lädt das neue Element an seiner Stelle.

Das Problem liegt wahrscheinlich auf der Hand: 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 Anzahl von 2 auf N + 1. Das Organisieren eines Caches auf mehr "Arten" erfordert zusätzliche Schaltkreise und läuft im Allgemeinen langsamer, so dass (zum Beispiel) ein assoziativer 8192-Wege-Cache auch selten eine gute Lösung ist.

Letztendlich ist dieser Faktor in tragbarem Code jedoch schwieriger zu kontrollieren. Ihre Kontrolle darüber, wo Ihre Daten abgelegt 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 sich jedoch lohnen, einen großen Puffer zuzuweisen und dann nur Teile Ihrer Zuweisung zu verwenden, um sicherzustellen, dass Daten nicht dieselben Cache-Zeilen gemeinsam nutzen (obwohl Sie wahrscheinlich den genauen Prozessor und ermitteln müssen entsprechend handeln).

• Falsches Teilen

Es gibt noch einen anderen verwandten Punkt namens "Falsches Teilen". Dies tritt in einem Multiprozessor- oder Multicore-System auf, in dem zwei (oder mehr) Prozessoren / Kerne Daten haben, die getrennt sind, aber in dieselbe Cache-Zeile fallen. Dies zwingt die beiden Prozessoren / Kerne, ihren Zugriff auf die Daten zu koordinieren, obwohl jeder sein eigenes, separates Datenelement hat. Insbesondere wenn die beiden die 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 ähnliches organisiert wird. Der primäre Weg, 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, an denen Daten zugewiesen werden).

1. Diejenigen, die C ++ gut kennen, fragen sich vielleicht, 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. Ich bin mir jedoch nicht bewusst, dass jemand dies getan hat, und angesichts der Tatsache, wie wenig valarrayverwendet wird, wäre ich zumindest ein wenig überrascht, wenn jemand dies auch tun würde.

2. Falls sich jemand fragt, wie valarray(speziell für die Leistung entwickelt) dies so schlimm falsch sein könnte, kommt es auf eines 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, aber sie verwenden eine Heuristik, die dem nahe kommt, ohne dass für jeden Zugriff ein vollständiger Zeitstempel erforderlich ist.

Willkommen in der Welt des datenorientierten Designs. Das grundlegende Mantra besteht darin, Zweige zu sortieren, zu eliminieren, zu stapeln und virtualAnrufe zu eliminieren - alles Schritte in Richtung einer besseren Lokalität.

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

Nur aufstapeln: Das klassische Beispiel für cache-unfreundlichen versus cache-freundlichen Code ist das "Cache-Blockieren" der Matrix-Multiplikation.

Naive Matrix Multiplikation 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 Nes groß ist, z. B. wenn N * sizeof(elemType)es 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 Cache-Zeile 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 wir mit 32-Bit-Floats (4 Byte) arbeiten, gibt es 16 Elemente pro Cache-Zeile. Und die Anzahl der Cache-Fehlschläge durch diese einfache Transformation wird ungefähr um das 16-fache reduziert.

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

Einige Ergebnisse des Googelns "Cache-Blockierung":

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

Eine schöne Videoanimation eines optimierten Cache-Blocking-Algorithmus.

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

Schleifenkacheln sind sehr eng miteinander verbunden:

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

Prozessoren arbeiten heute mit vielen Ebenen kaskadierender Speicherbereiche. Die CPU verfügt also über 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 nächste ist, bis Sie zum Systemspeicher gelangen, der sich nicht auf der CPU befindet und auf den der Zugriff relativ viel langsamer ist.

Logischerweise beziehen Sie sich auf den Befehlssatz der CPU nur auf Speicheradressen in einem riesigen virtuellen Adressraum. Wenn Sie auf eine einzelne Speicheradresse zugreifen, wird diese von der CPU abgerufen. früher holte es nur diese eine Adresse. Aber heute wird die CPU eine Menge Speicher um das von Ihnen angeforderte Bit abrufen und in den Cache kopieren. Es wird davon ausgegangen, dass Sie sehr bald nach einer Adresse in der Nähe fragen werden, wenn Sie nach einer bestimmten Adresse gefragt haben. Wenn Sie beispielsweise einen Puffer kopieren, lesen und schreiben Sie von aufeinanderfolgenden Adressen - eine nach der 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, ist dies ein Cache-Fehler und sie muss zur nächsten Ebene von wechseln Cache, um es zu finden, bis es schließlich in den Hauptspeicher gehen muss.

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

Ein Beispiel wäre also, Sie wollten eine riesige zweidimensionale Tabelle kopieren. Es ist so organisiert, dass die Erreichungszeile nacheinander im Speicher liegt und eine Zeile unmittelbar danach der nächsten folgt.

Wenn Sie die Elemente zeilenweise von links nach rechts kopieren würden, wäre dies cachefreundlich. Wenn Sie die Tabelle spaltenweise kopieren würden, würden Sie genau die gleiche Speichermenge kopieren - dies wäre jedoch cacheunfreundlich.

Es muss klargestellt werden, dass nicht nur Daten cachefreundlich sein sollten, sondern auch für den Code wichtig sind. Dies erfolgt zusätzlich zur Verzweigungsvorhersage, Neuanordnung von Anweisungen, Vermeidung tatsächlicher Unterteilungen und anderer Techniken.

Je dichter der Code ist, desto weniger Cache-Zeilen werden normalerweise benötigt, 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 Cache-Zeilen erforderlich sind, was zu weniger Cache-Zeilen für Daten führt.

Eine Funktion sollte an einer Cache-Zeilenausrichtungs-freundlichen Adresse beginnen. Obwohl es dafür (gcc) Compiler-Switches gibt, sollten Sie sich bewusst sein, 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.

Wie @Marc Claesen erwähnte, besteht eine der Möglichkeiten, cachefreundlichen Code zu schreiben, darin, die Struktur auszunutzen, in der unsere Daten gespeichert sind. Darüber hinaus besteht eine andere Möglichkeit, cachefreundlichen Code zu schreiben, darin, die Art und Weise zu ändern, 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 zum Speichern der Tupel einer Tabelle, z. B. Zeilen- und Spaltenspeicher. Wie der Name schon sagt, werden die Tupel im Zeilenspeicher zeilenweise gespeichert. Nehmen wir an, eine Tabelle mit dem Namen Product, die gespeichert wird, hat 3 Attribute, dh int32_t key, char name[56]und int32_t price, also beträgt die Gesamtgröße eines Tupels 64Bytes.

Wir können eine sehr einfache Ausführung von ProductZeilenspeicherabfragen im Hauptspeicher simulieren, indem wir ein Array von 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 das Produkt 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 ProductTabelle. Ein solches Speicherlayout wird auch als Struktur von Arrays bezeichnet. Die 3 Arrays für jedes Attribut des Produkts 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 drei separaten Arrays (Spaltenlayout) geladen haben, haben wir den Zeilenspeicher und den Spaltenspeicher in unserer Tabelle Productin unserem Speicher.

Nun gehen wir zum cachefreundlichen Codeteil über. 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 schneller als der Code für das Zeilenlayout in dieser Abfrage, da nur eine Teilmenge von Attributen erforderlich ist. Im Spaltenlayout tun wir genau das, dh wir greifen nur auf die Preisspalte zu.

Angenommen, die Cache-Zeilengröße beträgt 64Bytes.

Im Fall eines Zeilenlayouts 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 64 Byte beträgt und unsere gesamte Cache-Zeile ausfüllt, sodass für jedes Tupel ein Cache-Fehler auftritt eines Zeilenlayouts.

Im Fall eines Spaltenlayouts, wenn eine Cache-Zeile gelesen wird, wird der Preiswert von 16 ( cacheline_size/price_int_size = 64/4 = 16) Tupeln gelesen, da 16 zusammenhängende Preiswerte, die im Speicher gespeichert sind, in den Cache gebracht werden, so dass für jedes sechzehnte Tupel ein Cache-Fehler im Fall von auftritt Spaltenlayout.

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

Wenn in Datenbanksystemen die Abfragearbeitslast im Voraus bekannt ist, können wir unsere Daten in Layouts speichern, die den Abfragen in der Arbeitslast entsprechen, und auf Daten aus diesen Layouts zugreifen. Im obigen Beispiel haben wir ein Spaltenlayout erstellt und unseren Code so geändert, dass die Summe berechnet wird, sodass er cachefreundlich wird.

Beachten Sie, dass Caches nicht nur den kontinuierlichen Speicher zwischenspeichern. Sie haben mehrere Zeilen (mindestens 4), so dass 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.