L1 Cache Missのコストとは？

質問

編集 : 参考までに（もし誰かがこの問題に出くわしたら）、Igor Ostrovskyが書いた 偉大な投稿 を書きました。この記事では、いくつかの異なる問題について議論し、数値の例を示しています。 編集を終了する

いくつかのテストを行いました <long story goes here> を実行し、パフォーマンスの違いはメモリ キャッシュ ミスに起因するのかどうか疑問に思っています。 次のコードは、この問題を実証し、重要なタイミング部分まで煮詰めたものです。 次のコードには、ランダムな順序でメモリを訪問し、次にアドレスの昇順で訪問するループがいくつかあります。

XP マシン (VS2005: cl /O2 でコンパイル) と Linux ボックス (gcc -Os) でこれを実行しました。 どちらも同じような時間を生成しました。 これらの時間はミリ秒単位です。 私は、すべてのループが実行されており、最適化されていないと考えています (そうでなければ、「即座に」実行されるでしょう)。

*** 20000ノードでのテスト
総順序付け時間: 888.822899
総ランダム時間: 2155.846268

これらの数値は意味があるのでしょうか？ この差は主に L1 キャッシュのミスによるものなのでしょうか、それとも何か他の要因があるのでしょうか? 20,000^2 回のメモリ アクセスがあり、そのすべてがキャッシュ ミスだった場合、ミスあたり約 3.2 ナノ秒になります。 テストしたXP（P4）マシンは3.2GHzで、L1キャッシュが32KB、L2が512KBと思われる（ただしわからない）。 20,000エントリ(80KB)なので、L2ミスはそれほど多くないと推測されます。 ということは、これは (3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss . 私には高いように思えます。そうでないのかもしれないし、私の計算が悪いのかもしれません。 VTuneでキャッシュミスを計測してみたけど、BSODになっちゃった。 そして今、私はライセンスサーバーに接続させることができません (grrr)。

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 );

}

どのように解決するのですか？

この数字が意味を持つかどうかについての答えは出せませんが (私はキャッシュ レイテンシに詳しくはありませんが、L1 キャッシュ ミスが約 10 サイクルという記録は正しいようです)、次のようなことを提案することができます。 キャッシュグラインド を提供して、2 つのテスト間のキャッシュ パフォーマンスの違いを実際に確認するのに役立ちます。

CachegrindはValgrindツール（いつも素敵なmemcheckを動かすフレームワーク）であり、キャッシュとブランチのヒット/ミスをプロファイル化するものです。これは、プログラムで実際に得ているキャッシュ ヒット/ミスの数のアイデアを提供します。