Quel est le coût d'un cache L1 manquant?

Question

Edit: à des fins De référence (si quelqu'un bute sur cette question), Igor Ostrovsky a écrit un super article sur les défauts de cache. Il traite de plusieurs questions différentes et montre l'exemple des nombres. Fin Edit

J'ai fait quelques tests <long story goes here> et je me demande si une différence de performance est due à la mémoire cache. Le code suivant illustre le problème et bout vers le bas à la critique de chronométrage de la partie. Le code suivant a un couple de boucles que la visite de la mémoire dans un ordre aléatoire, puis dans l'ordre croissant des adresses.

Je l'ai exécuté sur une machine XP (compilé avec VS2005: cl /O2) et sur une machine Linux (gcc –Os). À la fois produit des temps similaires. Ces temps sont en millisecondes. Je crois que toutes les boucles sont en cours d'exécution et ne sont pas optimisés (sinon il irait "instantanément").

*** Le test de 20000 nœuds
Total Temps Commandé: 888.822899
Hasard Total Du Temps: 2155.846268

Ces numéros de sens? Est la différence principalement en raison de L1 cache ou autre chose? Il y a 20 000^2 accès à la mémoire et si tous étaient un cache miss, qui est sur le point 3.2 de nanosecondes par miss. L'XP (P4) de la machine je l'ai testé sur est de 3.2 GHz, et je crois (mais ne le savent pas) a un 32 ko de cache L1 et 512KB L2. Avec plus de 20 000 entrées (80 KO), je suppose, n'est pas un nombre important de L2 manque. Ce serait donc (3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss. Qui semble élevé pour moi. C'est peut-être pas, ou peut-être que mon calcul est mauvais. J'ai essayé de mesurer le cache avec VTune, mais j'ai eu un BSOD. Et maintenant je n'arrive pas à se connecter au serveur de licence (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 );

}

Answer 1

Bien que je ne peux pas proposer une réponse à savoir si ou non le compte est bon (je ne suis pas très versé dans le cache de latences, mais pour le dossier ~10 cycle de cache L1 manque de sons sur la droite), je peux vous offrir Cachegrind comme un outil pour vous aider à voir les différences dans les performances du cache entre tes 2 tests.

Cachegrind est un outil Valgrind (le cadre des pouvoirs de la toujours belle memcheck) les profils de cache et de la direction générale hits/rate. Il vous donnera une idée de combien de cache/manque vous sont effectivement obtenir dans votre programme.

Answer 2

3.2ns pour un cache L1 manquant est entièrement plausible. À titre de comparaison, sur un processeur PowerPC multicœur moderne, un échec L1 correspond à environ 40 cycles, un peu plus long pour certains cœurs que pour d’autres, en fonction de leur distance par rapport au cache L2 (en effet). Un échec L2 correspond à au moins 600 cycles.

Le cache est tout en performance; Les processeurs sont tellement plus rapides que la mémoire, maintenant que vous optimisez presque pour le bus de mémoire plutôt que pour le cœur.

Answer 3

Vous devriez lire «Ce que tous les programmeurs devraient savoir sur la mémoire» d’Ulrich Drepper - cela approfondit le calendrier d’accès à la mémoire, ainsi que les interactions entre les modèles d’accès et le cache.

Answer 4

Eh bien, oui, il semblerait que ce sera principalement les échecs de cache L1.

10 cycles pour un manque de cache L1 ne semblent pas trop graves, probablement un peu bas.

Une lecture dans la mémoire vive va prendre de l’ordre de 100 voire même des milliers (je suis trop fatigué pour essayer de faire le calcul en ce moment;)) de cycles, c’est donc toujours un gain énorme.

Answer 5

Si vous prévoyez d’utiliser Cachegrind, veuillez noter qu’il s’agit d’un simulateur de hit / miss en cache. Ce ne sera pas toujours précis. Par exemple: si vous accédez à un emplacement mémoire, disons 0x1234 dans une boucle 1000 fois, cachegrind vous montrera toujours qu'il n'y a qu'un seul manquement de cache (le premier accès), même si vous avez quelque chose comme:

clflush 0x1234 dans votre boucle.

Sur x86, cela causera tous les 1000 échecs de cache.