L1缓存缺失的成本是多少？

Question

编辑:为了参考目的(如果有人偶然发现这个问题),伊戈尔奥斯特罗夫斯基写了一篇关于缓存未命中的精彩帖子.它讨论了几个不同的问题并显示了示例数字. 结束编辑

我做了一些测试<long story goes here>,我想知道性能差异是否是由于内存缓存未命中.以下代码演示了该问题,并将其归结为关键时序部分.以下代码有几个循环,以随机顺序访问内存,然后按升序地址顺序访问内存.

我在XP机器(使用VS2005:cl/O2编译)和Linux机器(gcc -Os)上运行它.两者产生了相似的时间 这些时间以毫秒为单位.我相信所有循环都在运行并且未被优化(否则它将"立即"运行).

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

这些数字有意义吗？差异主要是由于L1缓存未命中还是还有其他事情发生？存在20,000 ^ 2个存储器访问,并且如果每个都是高速缓存未命中,则每个未命中约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 );

}

Answer 1

以下是尝试通过与烘焙巧克力饼干类比来深入了解缓存未命中的相对成本......

你的手是你的注册.将巧克力碎片放入面团需要1秒钟.

厨房柜台是你的L1缓存,比寄存器慢十二倍.走到柜台需要12 x 1 = 12秒,拿起一袋核桃,然后把一些倒进你的手里.

冰箱是你的L2缓存,比L1慢四倍.步行到冰箱需要4 x 12 = 48秒,打开它,将昨晚的剩菜移开,取出一箱鸡蛋,打开纸箱,在柜台上放3个鸡蛋,然后将纸箱放回原处.冰箱.

橱柜是你的L3缓存,比L2慢三倍.需要3 x 48 = 2分24秒才能走三步到柜子里,向下弯曲,打开门,根部找到烘焙供应锡,从橱柜中取出,打开它,挖掘找到发酵粉把它放在柜台上,扫掉你洒在地板上的烂摊子.

和主要记忆？这是角落商店,比L3快5倍.需要5 x 2:24 = 12分钟才能找到你的钱包,穿上你的鞋子和夹克,冲下街道,抢一升牛奶,冲到家里,脱掉你的鞋子和夹克,然后回到厨房.

请注意,所有这些访问都是不变的复杂性 - O(1) - 但它们之间的差异会对性能产生巨大影响.纯粹为大O复杂化进行优化就像决定是一次添加巧克力片还是一次添加10个,但忘记将它们放在购物清单上.

故事的道德:组织你的内存访问,所以CPU必须尽可能少去杂货.

数字来自CPU Cache Flushing Fallacy博客文章,这表明对于特定的2012年英特尔处理器,以下情况属实:

• 寄存器访问=每个周期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寄存器)

该处理器高速缓存影响的画廊也使得有关这个主题的良好的阅读.

Answer 2

虽然我无法回答这些数字是否有意义(我不熟悉缓存延迟,但是对于记录~10个周期的L1缓存错过了正确的声音),我可以为你提供Cachegrind作为一个工具,以帮助您实际看到两个测试之间的缓存性能差异.

Cachegrind是一个Valgrind工具(为永远可爱的memcheck提供支持的框架),可以对缓存和分支命中/未命中进行分析.它会让您了解您在程序中实际获得的缓存命中/未命中数.

Answer 3

对于L1缓存未命中,3.2ns是完全合理的.相比之下,在一个特定的现代多核PowerPC CPU上,L1未命中约为40个周期 - 某些内核比其他内核稍长一些,具体取决于它们与L2高速缓存的距离(是的).L2未命中至少 600个周期.

缓存是性能的一切; CPU现在比内存快得多,你实际上几乎都在优化内存总线而不是内核.

Answer 4

好吧,看起来它确实会主要是L1缓存未命中.

L1高速缓存未命中的10个周期听起来很合理,可能有点偏低.

从RAM读取大约需要100秒或者甚至可能是1000秒(我现在太累了,不能尝试数学;))循环因此它仍然是一个巨大的胜利.