編集: 参考までに(誰かがこの質問に遭遇した場合)、Igor Ostrovskyは素晴らしい投稿キャッシュ ミスについて。さまざまな問題について説明し、例の数値を示します。編集終了
いくつかテストしてみました<long story goes here>
が、パフォーマンスの違いはメモリ キャッシュ ミスによるものではないかと考えています。次のコードはこの問題を示しており、重要なタイミング部分に絞り込んでいます。次のコードには、メモリをランダムな順序でアクセスし、その後アドレスの昇順でアクセスするループがいくつかあります。
私はこれを XP マシン (VS2005: cl /O2 でコンパイル) と Linux ボックス (gcc –Os) で実行しました。どちらも同様の時間が生成されました。これらの時間はミリ秒単位です。すべてのループが実行されており、最適化されていないと思います (そうでなければ「瞬時に」実行されます)。
*** 20000ノードをテスト中 合計注文時間: 888.822899 合計ランダム時間: 2155.846268
これらの数字は意味をなしていますか? 違いは主に L1 キャッシュ ミスによるものでしょうか、それとも他に何か起きているのでしょうか? 20,000^2 のメモリ アクセスがあり、そのすべてがキャッシュ ミスだった場合、ミス 1 回あたり約 3.2 ナノ秒になります。私がテストした XP (P4) マシンは 3.2GHz で、おそらく (ただし確証はありません) 32KB の L1 キャッシュと 512KB の L2 キャッシュがあります。20,000 エントリ (80KB) なので、L2 ミスの数はそれほど多くないと思われます。したがって、これは になります(3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss
。私には高いように思えます。実際は高くないか、私の計算が間違っているのかもしれません。VTune でキャッシュ ミスを計測しようとしましたが、BSOD になりました。そして、ライセンス サーバーに接続できなくなりました (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 );
}
ベストアンサー1
ここでは、チョコレート チップ クッキーを焼くことに例えて、キャッシュ ミスの相対的なコストについての洞察を提供しようとします...
あなたの手はあなたのレジスターです。チョコチップを生地に落とすのに1秒かかります。
キッチンカウンターは L1 キャッシュであり、レジスターよりも 12 倍遅いです。カウンターまで歩いて、クルミの袋を手に取り、手に少し取り出すのに、12 x 1 = 12 秒かかります。
冷蔵庫は L2 キャッシュであり、L1 より 4 倍遅いです。冷蔵庫まで歩いて行き、開けて、昨晩の残り物をどかし、卵のパックを取り出し、パックを開けて、カウンターに卵 3 個を置き、パックを冷蔵庫に戻すまでには、4 x 12 = 48 秒かかります。
戸棚は L3 キャッシュで、L2 より 3 倍遅いです。食器棚まで 3 歩進み、かがんでドアを開け、ベーキング用品の缶を探し回り、それを食器棚から取り出し、開け、ベーキングパウダーを探し出し、それをカウンターに置き、床にこぼした汚れを掃き集めるには、3 x 48 = 2 分 24 秒かかります。
ではメインメモリはどうでしょうか? それはコーナーストアで、L3 より 5 倍遅いです。財布を探し、靴とジャケットを履き、道を駆け下り、牛乳 1 リットルを手に取り、家に駆け戻り、靴とジャケットを脱いでキッチンに戻るまでには、5 x 2:24 = 12 分かかります。
ご了承ください全てこれらのアクセスは一定の計算量(O(1))であるが、それらの違いは巨大なパフォーマンスへの影響。big-O の複雑さだけを最適化することは、生地にチョコチップを 1 個ずつ加えるか 10 個ずつ加えるかを決定しながら、買い物リストにそれを入れるのを忘れるようなものです。
この話の教訓:メモリ アクセスを整理して、CPU ができるだけ頻繁にアクセスしなくても済むようにします。
数字はCPU キャッシュ フラッシュの誤りブログ投稿によると、特定の 2012 年世代の Intel プロセッサの場合、次のことが当てはまります。
- レジスタアクセス = 1サイクルあたり4命令
- L1レイテンシ = 3サイクル(12 x レジスタ)
- L2レイテンシ = 12サイクル(4 x L1、48 xレジスタ)
- L3 レイテンシ = 38 サイクル (3 x L2、12 x L1、144 x レジスタ)
- DRAM レイテンシ = 65 ns = 3 GHz CPU で 195 サイクル (5 x L3、15 x L2、60 x L1、720 x レジスタ)
のプロセッサ キャッシュ効果のギャラリーこのトピックに関する良い読み物でもあります。