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?
Der in der Frage verlinkte Igor Ostrovsky ist ausgezeichnet. +1, nur um mich darauf hinzuweisen.
– Benutzer334911
9. Mai 2011 um 14:29 Uhr
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)
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
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 wenigstens600 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
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
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
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.
14175600cookie-checkWas kostet ein L1-Cache-Fehltreffer?yes
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