什么是L1缓存未命中的成本？(What is the Cost of an L1 Cache Mis

编辑 ：作为参考（如果任何人碰到这个问题绊），伊戈尔·奥斯特洛夫斯基写了一个伟大的职位有关高速缓存未命中。 讨论了几个不同的问题，例如显示的数字。 编辑完

我做了一些测试<long story goes here> ，我想知道，如果性能差异是由于内存高速缓存未命中。 下面的代码演示了这个问题，并归结下来的关键时序部分。 下面的代码有一对夫妇，在随机访问存储器中，然后按升序地址顺序循环。

我跑了XP的机器（与VS2005编译：CL / O2）上（GCC -Os），并在Linux机器上。 二者产生相似的倍。 这些时间以毫秒为单位。 我相信所有的回路运行，而不是优化掉了（否则会运行“立即”）。

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

难道这些数字有意义吗？ 的区别主要是由于L1高速缓存未命中或别的东西怎么回事呢？ 有20,000平方公尺的内存访问，如果每个人都缓存未命中，即每小姐约3.2纳秒。 我测试在XP（P4）的机器是3.2GHz的，我怀疑（但不知道）具有32KB L1缓存和512KB L2。 20000项（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:

虽然我不能提供一个答案的编号是否没有意义了（我不是深谙缓存延迟，但备案〜10个周期的L1高速缓存未命中听起来是正确的），我可以为您提供Cachegrind作为工具来帮助你真正看到你的2次测试之间的缓存性能的差异。

Cachegrind是Valgrind的工具，它配置文件高速缓存和分支命中/未命中（该框架，权力总是可爱MEMCHECK）。 它会给你的缓存多少命中/想你实际上是在程序中获得的想法。

Answer 2:

下面是一个试图通过类比提供洞察高速缓存未命中的相对成本与烘焙巧克力曲奇饼...

你的手你的寄存器。 这需要你1秒钟巧克力片放入面团。

厨房柜台是你的L1缓存，比寄存器慢十二倍。 它采用12×1 = 12秒一步到柜台，拿起核桃的包，并清空一些在你们手里。

冰箱是您的L2缓存，比L1慢四倍。 它采用4×12 = 48秒步行到冰箱，打开它，将昨晚的剩饭闪开，取出鸡蛋的纸箱，打开纸箱，放在柜台上的3个鸡蛋，并把纸箱回冰箱。

柜子是你的L3高速缓存，L2相比要慢三倍。 这需要3×48 = 2分24秒，以采取三个步骤的柜子，弯腰，开门，根周围找到烘烤供给锡，从橱柜提取它，打开它，挖找到发酵粉，把它放在柜台上，扫除你在地板上洒了混乱。

和主内存？ 这是街头小店，比L3慢5倍。 它采用5×2:24 = 12分钟才找到你的钱包，把你的鞋子和外套，冲下马路，抢升牛奶，几许家，脱掉你的鞋子和外套，回到厨房。

注意， 所有这些访问都是恒定的复杂性- O（1） -但它们之间的差异可能会对性能产生巨大的影响。 纯粹优化大O的复杂性就像是决定是否巧克力片在同一时间或10一次添加到面糊1，但忘了把它们放在你的购物清单上。

这个故事的寓意：组织你的内存访问，因此CPU必须去杂货尽可能少。

数字是取自CPU缓存刷新谬误的博客文章，这表明对于特定的2012时代的英特尔处理器，符合下列条件：

• 每个周期寄存器存取= 4名的指令
• L1 =延迟3个周期（12×寄存器）
• L2延迟= 12个循环（4×L1，48个寄存器）
• L3延迟= 38个循环（3×L2，12×L1，144 X寄存器）
• DRAM等待时间= 65纳秒3 GHz的CPU上= 195个周期（5×L3，15×L2，60×L1，720×寄存器）

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

Answer 3:

对于L1高速缓存未命中3.2ns是完全可行的。 为了便于比较，在一个特定的现代多核PowerPC的CPU，一个L1思念是约40个循环-稍长一些核心比其他的，这取决于他们是如何远离二级缓存（是真的）。 的L2未命中是至少 600个周期。

缓存在性能上的一切; 现在的CPU是如此比内存要快得多，你真的几乎优化内存总线，而不是核心。

Answer 4:

好耶，它看起来就像是将主要是L1高速缓存未命中。

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

从RAM的读取是要采取100s的顺序，或者甚至可能1000（累得尝试做数学，现在;））的周期因此它仍然是一个巨大的胜利了这一点。

Answer 5:

如果你打算使用cachegrind，请注意，这只是一个缓存命中/缺失模拟器。 它不会总是准确的。 例如：如果你访问某些内存位置，说为0x1234在一个循环1000次，cachegrind总会告诉你，世界上只有一个高速缓存未命中（第一个访问），即使你有这样的：

CLFLUSH在循环×1234。

在x86上，这将导致所有1000个高速缓存未命中。

Answer 6:

从一个Lavalys珠峰运行一个3.4GHz的P4一些数字：

• 该L1 DCACHE为8K（高速缓存行64个字节）
• L2为512K
• L1提取等待时间是2个周期
• L2提取等待时间大约是你所看到的两倍：20次

这里更多： http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt

（对于延迟看看页面的底部）

Answer 7:

这很难肯定地说什么没有更多的测试，但在我的经验差别在于规模绝对可以归因于CPU的L1和/或L2高速缓存，尤其是在随机访问的情况。 你也许可以使它更通过确保每个接入至少从最近一些最小距离差。

Answer 8:

最容易做的事情是把目标CPU的缩放照片和物理测量核心与1级高速缓存之间的距离。 乘以距离电子该距离可以每秒行进铜。 然后找出你可以有多少个时钟周期内必须在同一时间。 那就是你在L1高速缓存未命中浪费CPU周期的最小数目。

您还可以制定出在以同样的方式浪费CPU周期数来获取RAM中的数据的最低成本。 你可能会很惊讶。

请注意，你会清楚看到这里有事情做与缓存缺失（不论是L1或L1和L2），因为通常缓存将拔出的数据在同一高速缓存行，一旦你在要求高速缓存行访问任何少游到RAM中。

但是，你很可能也看到的事实是，RAM（即使它调用随机存取存储器）仍然preferres线性存储器访问。

文章来源: What is the Cost of an L1 Cache Miss?