Was kostet ein L1-Cache-Fehltreffer?

Lesezeit: 9 Minuten

Benutzeravatar von Mark Wilkins
Markus Wilkins

Bearbeiten: Zu Referenzzwecken (falls jemand über diese Frage stolpert), schrieb Igor Ostrovsky a guter Eintrag über Cache-Miss. Es behandelt mehrere verschiedene Probleme und zeigt Beispielnummern. Bearbeiten beenden

Ich habe einige Tests gemacht <long story goes here> und ich frage mich, ob ein Leistungsunterschied auf Speichercachefehler zurückzuführen ist. Der folgende Code demonstriert das Problem und reduziert es auf den kritischen Timing-Teil. Der folgende Code hat ein paar Schleifen, die den Speicher in zufälliger Reihenfolge und dann in aufsteigender Adressreihenfolge besuchen.

Ich habe es auf einem XP-Rechner (kompiliert mit VS2005: cl /O2) und auf einer Linux-Box (gcc –Os) ausgeführt. Beide produzierten ähnliche Zeiten. Diese Zeiten sind in Millisekunden angegeben. Ich glaube alle Schleifen laufen und sind nicht optimiert (sonst würde es „sofort“ laufen).

*** Testing 20000 nodes
Total Ordered Time: 888.822899
Total Random Time: 2155.846268

Sind diese Zahlen sinnvoll? Ist der Unterschied hauptsächlich auf L1-Cache-Fehler zurückzuführen oder passiert noch etwas anderes? Es gibt 20.000 ^ 2 Speicherzugriffe, und wenn jeder ein Cache-Miss wäre, wären das ungefähr 3,2 Nanosekunden pro Miss. Die XP (P4)-Maschine, auf der ich getestet habe, hat 3,2 GHz und ich vermute (aber weiß nicht), dass sie einen 32 KB L1-Cache und 512 KB L2 hat. Bei 20.000 Einträgen (80 KB) gehe ich davon aus, dass es keine signifikante Anzahl von L2-Fehlschlägen gibt. Das wäre also (3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss. Das erscheint mir hoch. Vielleicht ist es nicht, oder vielleicht ist meine Mathematik schlecht. Ich habe versucht, Cache-Fehler mit VTune zu messen, aber ich habe einen BSOD erhalten. Und jetzt bekomme ich keine Verbindung zum Lizenzserver (grrrr).

typedef struct stItem
{
   long     lData;
   //char     acPad[20];
} LIST_NODE;



#if defined( WIN32 )
void StartTimer( LONGLONG *pt1 )
{
   QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2, llFreq;

   QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
   QueryPerformanceFrequency( (LARGE_INTEGER*)&llFreq );
   *pdMS = ((double)( t2 - t1 ) / (double)llFreq) * 1000.0;
}
#else
// doesn't need 64-bit integer in this case
void StartTimer( LONGLONG *pt1 )
{
   // Just use clock(), this test doesn't need higher resolution
   *pt1 = clock();
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2 = clock();
   *pdMS = (double)( t2 - t1 ) / ( CLOCKS_PER_SEC / 1000 );
}
#endif



long longrand()
{
   #if defined( WIN32 )
   // Stupid cheesy way to make sure it is not just a 16-bit rand value
   return ( rand() << 16 ) | rand();
   #else
   return rand();
   #endif
}

// get random value in the given range
int randint( int m, int n )
{
   int ret = longrand() % ( n - m + 1 );
   return ret + m;
}

// I think I got this out of Programming Pearls (Bentley).
void ShuffleArray
(
   long *plShuffle,  // (O) return array of "randomly" ordered integers
   long lNumItems    // (I) length of array
)
{
   long i;
   long j;
   long t;

   for ( i = 0; i < lNumItems; i++ )
      plShuffle[i] = i;

   for ( i = 0; i < lNumItems; i++ )
      {
      j = randint( i, lNumItems - 1 );

      t = plShuffle[i];
      plShuffle[i] = plShuffle[j];
      plShuffle[j] = t;
      }
}



int main( int argc, char* argv[] )
{
   long          *plDataValues;
   LIST_NODE     *pstNodes;
   long          lNumItems = 20000;
   long          i, j;
   LONGLONG      t1;  // for timing
   double dms;

   if ( argc > 1 && atoi(argv[1]) > 0 )
      lNumItems = atoi( argv[1] );

   printf( "\n\n*** Testing %u nodes\n", lNumItems );

   srand( (unsigned int)time( 0 ));

   // allocate the nodes as one single chunk of memory
   pstNodes = (LIST_NODE*)malloc( lNumItems * sizeof( LIST_NODE ));
   assert( pstNodes != NULL );

   // Create an array that gives the access order for the nodes
   plDataValues = (long*)malloc( lNumItems * sizeof( long ));
   assert( plDataValues != NULL );

   // Access the data in order
   for ( i = 0; i < lNumItems; i++ )
      plDataValues[i] = i;

   StartTimer( &t1 );

   // Loop through and access the memory a bunch of times
   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Ordered Time: %f\n", dms );

   // now access the array positions in a "random" order
   ShuffleArray( plDataValues, lNumItems );

   StartTimer( &t1 );

   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Random Time: %f\n", dms );

}

  • Seine Frage lautet: “Sind diese Zahlen sinnvoll?”

    – Tim Sylvester

    14. Juli 2009 um 16:32 Uhr

  • Entschuldigung – ich habe die Frage irgendwie in zu viel Text vergraben. Aber ja, die Frage ist, ob die Zahlen Sinn machen. Sind 10 Zyklen für einen L1-Cache-Fehltreffer ungefähr richtig?

    – Mark Wilkins

    14. Juli 2009 um 17:06 Uhr

  • Sollte man sich mal durchlesen “Was jeder Programmierer über Speicher wissen sollte” von Ulrich Drepper – es geht tief in das Timing von Speicherzugriffen und Zugriffsmustern und Cache-Interaktionen ein.

    – Café

    15. Juli 2009 um 8:03 Uhr

  • Der in der Frage verlinkte Igor Ostrovsky ist ausgezeichnet. +1, nur um mich darauf hinzuweisen.

    Benutzer334911

    9. Mai 2011 um 14:29 Uhr

Benutzeravatar von yoyo
Yoyo

Hier ist ein Versuch, in Analogie zum Backen von Schokoladenkeksen einen Einblick in die relativen Kosten von Cache-Misses zu geben …

Ihre Hände sind Ihre Register. Es dauert 1 Sekunde, um Schokoladenstückchen in den Teig fallen zu lassen.

Die Küchentheke ist Ihr L1-Cache, zwölfmal langsamer als Register. Es dauert 12 x 1 = 12 Sekunden, um zum Tresen zu gehen, die Tüte mit Walnüssen aufzuheben und etwas davon in deine Hand zu leeren.

Der Kühlschrank ist Ihr L2-Cache, viermal langsamer als L1. Es dauert 4 x 12 = 48 Sekunden, um zum Kühlschrank zu gehen, ihn zu öffnen, die Reste der letzten Nacht aus dem Weg zu räumen, einen Karton mit Eiern herauszunehmen, den Karton zu öffnen, 3 Eier auf die Theke zu legen und den Karton wieder hineinzustellen der Kühlschrank.

Der Schrank ist Ihr L3-Cache, dreimal langsamer als L2. Es dauert 3 x 48 = 2 Minuten und 24 Sekunden, um drei Schritte zum Schrank zu gehen, sich zu bücken, die Tür zu öffnen, nach der Backvorratsdose zu wühlen, sie aus dem Schrank zu ziehen, sie zu öffnen, zu graben, um das Backpulver zu finden , legen Sie es auf den Tresen und fegen Sie die Unordnung auf, die Sie auf dem Boden verschüttet haben.

Und Hauptspeicher? Das ist der Laden an der Ecke, 5 mal langsamer als L3. Es dauert 5 x 2:24 = 12 Minuten, um Ihre Brieftasche zu finden, Schuhe und Jacke anzuziehen, die Straße entlang zu flitzen, einen Liter Milch zu schnappen, nach Hause zu flitzen, Schuhe und Jacke auszuziehen und zurück in die Küche zu gelangen.

Beachten Sie, dass alle diese Zugriffe sind konstante Komplexität – O(1) – aber die Unterschiede zwischen ihnen können a haben riesig Auswirkungen auf die Leistung. Die reine Optimierung auf Big-O-Komplexität ist wie die Entscheidung, ob Sie dem Teig 1 oder 10 Schokoladenstückchen auf einmal hinzufügen, aber vergessen, sie auf Ihre Einkaufsliste zu setzen.

Moral der Geschichte: Organisieren Sie Ihre Speicherzugriffe so, dass die CPU so selten wie möglich einkaufen gehen muss.

Zahlen wurden aus der übernommen Fehlschluss beim Leeren des CPU-Cache Blog-Beitrag, der darauf hinweist, dass für einen bestimmten Intel-Prozessor der Ära 2012 Folgendes gilt:

  • Registerzugriff = 4 Befehle pro Zyklus
  • L1-Latenz = 3 Zyklen (12 x Register)
  • L2-Latenz = 12 Zyklen (4 x L1, 48 x Register)
  • L3-Latenz = 38 Zyklen (3 x L2, 12 x L1, 144 x Register)
  • DRAM-Latenz = 65 ns = 195 Zyklen auf einer 3-GHz-CPU (5 x L3, 15 x L2, 60 x L1, 720 x Register)

Das Galerie der Prozessor-Cache-Effekte macht auch gute lektüre zu diesem thema.

Hmm, Kekse ...

  • Diese 1 in O(1) ist immer ein Widerstand. nette antwort, hätte die annehmen sollen!

    – g24l

    30. Dezember 2015 um 21:28 Uhr


  • Gute Antwort! Darüber hinaus könnte dies auf mehrere Küchenzeilen (Kerne) erweitert werden, die sich dieselben Schränke teilen (L3-Cache); Wenn ein Koch in den Laden geht, um mehr Mehl zu holen, können alle anderen es von dort holen.

    – rosuav

    19. August 2016 um 22:13 Uhr

  • Ich würde auch hinzufügen: Im Fall von virtuellem Speicher ist ein Zugriff auf eine ausgelagerte Seite (dh eine, die das Einlesen von Daten von der Festplatte erfordert) so, als würde man feststellen, dass der Laden für dieses Zimtpulver nicht vorrätig ist und sie es bestellen müssen eine neue Charge aus China – mit einer Lieferzeit von 6 Wochen.

    – Smiheey

    15. November 2016 um 9:25 Uhr

Benutzeravatar von Falaina
Falaina

Obwohl ich keine Antwort darauf geben kann, ob die Zahlen sinnvoll sind oder nicht (ich kenne mich mit den Cache-Latenzen nicht gut aus, aber für die Aufzeichnung klingen L1-Cache-Fehlschläge von ~ 10 Zyklen ungefähr richtig), kann ich Ihnen anbieten Cachegrind als ein Werkzeug, das Ihnen hilft, die Unterschiede in der Cache-Leistung zwischen Ihren beiden Tests tatsächlich zu erkennen.

Cachegrind ist ein Valgrind-Tool (das Framework, das den allseits beliebten Memcheck unterstützt), das Cache- und Branch-Hits/Fehlschläge profiliert. Es gibt Ihnen eine Vorstellung davon, wie viele Cache-Treffer/Fehltreffer Sie tatsächlich in Ihrem Programm erhalten.

  • Sehr schön. Danke für den Hinweis darauf. Ich kenne Valgrind, habe es aber noch nie verwendet (der größte Teil meiner Entwicklung findet unter Win32 statt). Ich habe es gerade auf einer Linux-Box ausgeführt und es hat eine Fehlerquote von 41 % für den “zufälligen” Teil des Tests gemeldet. Und der “in Ordnung”-Teil des Tests hatte eine vernachlässigbare Fehlerquote. Kein Teil hatte eine nennenswerte L2-Fehlquote.

    – Mark Wilkins

    15. Juli 2009 um 15:34 Uhr

3,2 ns für einen L1-Cache-Miss sind durchaus plausibel. Zum Vergleich: Auf einer bestimmten modernen Multicore-PowerPC-CPU liegt ein L1-Miss vor 40 Zyklen – für einige Kerne etwas länger als für andere, je nachdem, wie weit sie vom L2-Cache entfernt sind (ja, wirklich). Ein L2-Miss ist wenigstens 600 Fahrräder.

Cache ist alles in Sachen Leistung; CPUs sind jetzt so viel schneller als Speicher, dass Sie wirklich fast für den Speicherbus statt für den Kern optimieren.

Nun ja, das sieht so aus, als würden es hauptsächlich L1-Cache-Fehler sein.

10 Zyklen für einen L1-Cache-Miss klingen ungefähr vernünftig, wahrscheinlich ein wenig zu niedrig.

Ein Lesevorgang aus dem RAM wird in der Größenordnung von 100s oder sogar 1000s (bin zu müde, um jetzt zu rechnen;)) von Zyklen dauern, also ist es immer noch ein großer Gewinn darüber.

Wenn Sie Cachegrind verwenden möchten, beachten Sie bitte, dass es sich nur um einen Cache-Hit/Miss-Simulator handelt. Es wird nicht immer genau sein. Zum Beispiel: Wenn Sie auf einen Speicherort zugreifen, sagen wir 0x1234 in einer Schleife 1000 Mal, wird cachegrind Ihnen immer zeigen, dass es nur einen Cache-Mißerfolg gab (der erste Zugriff), selbst wenn Sie etwas haben wie:

clflush 0x1234 in Ihrer Schleife.

Auf x86 führt dies zu allen 1000 Cache-Fehlern.

  • Könnten Sie bitte erklären, warum auf x86 1000 Cache-Fehlschläge erforderlich sind?

    – Anis LOUNIS alias AnixPasBesoin

    19. August 2020 um 6:21 Uhr

  • Wenn dies zutrifft, könnte Cachegrind die Unterstützung nicht einfach hinzufügen clflush Anleitung zu ihrer Cache-Simulation?

    – Edmund

    6. April 2021 um 1:25 Uhr

Benutzeravatar von Terminus
Endstation

Einige Zahlen für einen 3,4-GHz-P4 von einem Lavalys-Everest-Lauf:

  • der L1-Dcache ist 8K groß (Cacheline 64 Byte)
  • L2 ist 512K
  • Die L1-Abruflatenz beträgt 2 Zyklen
  • Die L2-Abruflatenz ist etwa das Doppelte dessen, was Sie sehen: 20 Zyklen

Mehr hier:
http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt

(für die Latenzen siehe unten auf der Seite)

  • Könnten Sie bitte erklären, warum auf x86 1000 Cache-Fehlschläge erforderlich sind?

    – Anis LOUNIS alias AnixPasBesoin

    19. August 2020 um 6:21 Uhr

  • Wenn dies zutrifft, könnte Cachegrind die Unterstützung nicht einfach hinzufügen clflush Anleitung zu ihrer Cache-Simulation?

    – Edmund

    6. April 2021 um 1:25 Uhr

Benutzeravatar von Tim Sylvester
Tim Sylvester

Es ist schwierig, ohne viel mehr Tests etwas mit Sicherheit zu sagen, aber meiner Erfahrung nach kann dieser Unterschied definitiv dem CPU-L1- und/oder L2-Cache zugeschrieben werden, insbesondere in einem Szenario mit zufälligem Zugriff. Sie könnten es wahrscheinlich noch schlimmer machen, indem Sie sicherstellen, dass jeder Zugriff mindestens einen Mindestabstand zum letzten hat.

1417560cookie-checkWas kostet ein L1-Cache-Fehltreffer?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy