漫游CPU缓存效应,让你的程序性能飙升!-技术圈

推荐一个原创技术号-非科班大厂码农，号主是机械专业转行进入腾讯的后端程序员！

大多数读者都知道cache是一种快速小型的内存，用以存储最近访问内存位置。这种描述合理而准确，但是更多地了解一些处理器缓存工作中的“烦人”细节对于理解程序运行性能有很大帮助。

在这篇博客中，我将运用代码示例来详解 cache工作的方方面面，以及对现实世界中程序运行产生的影响。

下面的例子都是用C#写的，但语言的选择不影响程序运行状况以及得出的结论。

示例1：内存访问和运行

你认为相较于循环1，循环2会运行更快吗？

    
      int[] arr = new int[64 * 1024 * 1024];


    
    
      // Loop 1
    
    
      
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;


    
    
      // Loop 2
    
    
      
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

第一个循环将数组的每个值乘3，第二个循环将每16个值乘3，第二个循环只做了第一个约6%的工作，但在现代机器上，两者几乎运行相同时间：在我机器上分别是80毫秒和78毫秒。

两个循环花费相同时间的原因跟内存有关。这些循环执行时间长短由数组的内存访问次数决定的，而非整型数的乘法运算次数。而且下面第二个示例会解释硬件对这两个循环的内存访问次数是相同的。

示例2：缓存行的影响

让我们进一步探索这个例子。我们将尝试不同的循环步长，而不仅仅是1和16。

    
      for (int i = 0; i < arr.Length; i += K) arr[i] *= 3;

下图为该循环在不同步长(K)下的运行时间：

请注意，当步长在 1 到 16 的范围内时，for 循环的运行时间几乎没有变化。但从 16 开始，每次步长加倍，运行时间就会减半。其背后的原因是今天的 CPU 不再逐字节访问内存，而是以64 字节为单位的块形式获取内存，这个块称为 缓存行 。当您读取特定内存位置时，整个缓存行将从内存读取到缓存中。因此，访问同一缓存行中的其他内容速度是很快的！由于 16 个整数占用 64 个字节（一个缓存行），因此for 循环步长在 1 到 16 之间这16种情况，其访问的缓存行数量是相同的---数组中的所有缓存行。但是，当步长达为 32时，我们只需要访问数组中一半的缓存行---将仅触及大约每隔一个缓存行，当步长达到 64，我们只需要访问数组中四分之一的缓存行，则仅每隔四分之一触及一次。

理解缓存行对于某些类型的程序优化非常重要。例如，数据字节对齐可能觉定一次操作是接触一个还是两个缓存行。正如我们在上面的示例中看到的，这很容易意味着在未对齐的情况下，操作速度会慢两倍。

示例3：L1和L2缓存的大小

如今的计算机一般都配备两级( L1、L2)或三级(L3)高速缓存如果您想了解不同缓存的大小，可以使用CoreInfo SysInternals 工具，或使用GetLogicalProcessorInfo Windows API 调用。两者都将告诉你缓存行以及缓存本身的大小。

在我的机器上，CoreInfo 报告显示我有一个 32kB L1 数据缓存、一个 32kB L1 指令缓存和一个 4MB L2 数据缓存。L1 缓存是针对每个核心的，L2 缓存是在核心对之间共享的：让我们通过一个实验来验证这些数字。遍历一个整型数组，每16个值自增1——一种节约的方式改变每个缓存行。当遍历到最后一个值，就重头开始。我们将使用不同的数组大小，可以看到当数组溢出一级缓存大小，程序运行的性能将急剧滑落。

这是程序：

    
      int steps = 64 * 1024 * 1024;
// Arbitrary number of steps
int lengthMod = arr.Length - 1;
for (int i = 0; i < steps; i++)
{
    arr[(i * 16) & lengthMod]++; // (x & lengthMod) is equal to (x % arr.Length)
}

下图是运行时间图表：

您可以看到在 32kB 和 4MB（我的计算机上的 L1 和 L2 缓存的大小）之后明显下降。

示例4：指令级并行性

现在让我们看一看不同的东西。下面两个循环中你认为哪个较快？

    
      int steps = 256 * 1024 * 1024;
int[] a = new int[2];

// Loop 1

for (int i=0; i<steps; i++) {

a[0]++;

}


      
// Loop 2

for (int i=0; i<steps; i++) {

a[ 0 ]++;

a[ 1 ]++;

}

第一个循环体内，操作做是相互依赖的（译者注：下一次依赖于前一次）：

但第二个例子中，依赖性就不同了：

现代处理器中对不同部分指令拥有一点并发性（译者注：跟流水线有关，比如Pentium处理器就有U/V两条流水线，后面说明）。这使得CPU在同一时刻访问L1两处内存位置，或者执行两次简单算术操作。在第一个循环中，处理器无法发掘这种指令级别的并发性，但第二个循环中就可以。 [原文更新]：许多人在reddit上询问有关编译器优化的问题，像{ a[0]++; a[0]++; }能否优化为{ a[0]+=2; }。实际上，C#编译器和CLR JIT没有做优化——在数组访问方面。我用release模式编译了所有测试（使用优化选项），但我查询了JIT汇编语言证实优化并未影响结果。

示例5：缓存关联性

缓存设计的一个关键决定是确保每个主存块(chunk)能够存储在任何一个缓存槽里，或者只是其中一些（译者注：此处一个槽位就是一个缓存行）。

有三种方式将缓存槽映射到主存块中：

直接映射(Direct mapped cache) 每个内存块只能映射到一个特定的缓存槽。一个简单的方案是通过块索引chunk_index映射到对应的槽位(chunk_index % cache_slots)。被映射到同一内存槽上的两个内存块是不能同时换入缓存的。（译者注：chunk_index可以通过物理地址/缓存行字节计算得到）
N路组关联(N-way set associative cache) 每个内存块能够被映射到N路特定缓存槽中的任意一路。比如一个16路缓存，每个内存块能够被映射到16路不同的缓存槽。一般地，具有一定相同低bit位地址的内存块将共享16路缓存槽。（译者注：相同低位地址表明相距一定单元大小的连续内存）
完全关联(Fully associative cache) 每个内存块能够被映射到任意一个缓存槽。操作效果上相当于一个散列表。

直接映射缓存会引发冲突——当多个值竞争同一个缓存槽，它们将相互驱逐对方，导致命中率暴跌。另一方面，完全关联缓存过于复杂，并且硬件实现上昂贵。 N路组关联是处理器缓存的典型方案，它在电路实现简化和高命中率之间做出来良好的权衡。举个例子，4MB大小的L2缓存在我机器上是16路关联。所有64字节内存块将分割为不同组，映射到同一组的内存块将竞争L2缓存里的16路槽位。 L2缓存有65,536个缓存行（译者注：4MB/64），每个组需要16路缓存行，我们将获得4096个组。这样一来，块属于哪个组取决于块索引的低12位bit(2^12=4096)。因此缓存行对应的物理地址凡是以262,144字节(4096*64)的倍数区分的，将竞争同一个缓存槽。我机器上最多维持16个这样的缓存槽。（译者注：请结合上图中的2路关联延伸理解，一个块索引对应64字节，chunk0对应组0中的任意一路槽位，chunk1对应组1中的任意一路槽位，以此类推chunk4095对应组4095中的任意一路槽位，chunk0和chunk4096地址的低12bit是相同的，所以chunk4096、chunk8192将同chunk0竞争组0中的槽位，它们之间的地址相差262,144字节的倍数，而最多可以进行16次竞争，否则就要驱逐一个chunk）。

为了使得缓存关联效果更加明了，我需要重复地访问同一组中的16个以上的元素，通过如下方法证明：

    
      public static long UpdateEveryKthByte(byte[] arr, int K)
{
    Stopwatch sw = Stopwatch.StartNew();
    const int rep = 1024*1024; // Number of iterations – arbitrary
    int p = 0;
    for (int i = 0; i < rep; i++)
    {
        arr[p]++;
        p += K;
        if (p >= arr.Length) p = 0;
    }
    sw.Stop();
    return sw.ElapsedMilliseconds;
}

该方法每次在数组中迭代K个值，当到达末尾时从头开始。循环在运行足够长（2^20次）之后停止。

我使用不同的数组大小（每次增加1MB）和不同的步长传入UpdateEveryKthByte()。以下是绘制的图表，蓝色代表运行较长时间，白色代表较短时间：

蓝色区域（较长时间）表明当我们重复数组迭代时，更新的值无法同时放在缓存中。浅蓝色区域对应80毫秒，白色区域对应10毫秒。

让我们来解释一下图表中蓝色部分：

为何有垂直线？垂直线表明步长值过多接触到同一组中内存位置（大于16次）。在这些次数里，我的机器无法同时将接触过的值放到16路关联缓存中。一些糟糕的步长值为2的幂：256和512。举个例子，考虑512步长遍历8MB数组，存在32个元素以相距262,144字节空间分布，所有32个元素都会在循环遍历中更新到，因为512能够整除262,144（译者注：此处一个步长代表一个字节）。由于32大于16，这32个元素将一直竞争缓存里的16路槽位。（译者注：为何512步长的垂直线比256步长颜色更深？在同样足够多的步数下，512比256访问到存在竞争的块索引次数多一倍。比如跨越262,144字节边界512需要512步，而256需要1024步。那么当步数为2^20时，512访问了2048次存在竞争的块而256只有1024次。最差情况下步长为262,144的倍数，因为每次循环都会引发一个缓存行驱逐。）有些不是2的幂的步长运行时间长仅仅是运气不好，最终访问到的是同一组中不成比例的许多元素，这些步长值同样显示为蓝线。
为何垂直线在4MB数组长度的地方停止？因为对于小于等于4MB的数组，16路关联缓存相当于完全关联缓存。一个16路关联缓存最多能够维护16个以262,144字节分隔的缓存行，4MB内组17或更多的缓存行都没有对齐在262,144字节边界上，因为16*262,144=4,194,304。
为何左上角出现蓝色三角？在三角区域内，我们无法在缓存中同时存放所有必要的数据，不是出于关联性，而仅仅是因为L2缓存大小所限。举个例子，考虑步长128遍历16MB数组，数组中每128字节更新一次，这意味着我们一次接触两个64字节内存块。为了存储16MB数组中每两个缓存行，我们需要8MB大小缓存。但我的机器中只有4MB缓存（译者注：这意味着必然存在冲突从而延时）。即使我机器中4MB缓存是全关联，仍无法同时存放8MB数据。
为何三角最左边部分是褪色的？注意左边0~64字节部分——正好一个缓存行！就像上面示例1和2所说，额外访问相同缓存行的数据几乎没有开销。比如说，步长为16字节，它需要4步到达下一个缓存行，也就是说4次内存访问只有1次开销。

在相同循环次数下的所有测试用例中，采取省力步长的运行时间来得短。

将图表延伸后的模型：

缓存关联性理解起来有趣而且确能被证实，但对于本文探讨的其它问题比起来，它肯定不会是你编程时所首先需要考虑的问题。

示例6：错误的缓存行共享

在多核机器上，缓存遇到了另一个问题——一致性。不同的处理器拥有完全或部分分离的缓存。在我的机器上，L1缓存是分离的（这很普遍），而我有两对处理器，每一对共享一个L2缓存。这随着具体情况而不同，如果一个现代多核机器上拥有多级缓存，那么更快和更小的缓存是被处理器独占的。

当一个处理器修改了缓存中的一个值（假设该缓存对应在内存地址为x），其它处理器就不能再使用内存x对应的缓存值了，因为其对应的内存位置将在所有缓存中失效。而且由于缓存操作是以缓存行而不是字节为粒度，整个缓存行将在所有缓存中失效，无论是处理器独享的L1还是共享的L2缓存！

为证明这个问题，考虑如下例子：

    
      private static int[] s_counter = new int[1024];
private void UpdateCounter(int position)
{
    for (int j = 0; j < 100000000; j++)
    {
        s_counter[position] = s_counter[position] + 3;
    }
}

在我的四核机上，如果我通过四个线程传入参数0,1,2,3并调用UpdateCounter，所有线程将花费4.3秒。

另一方面，如果我传入16,32,48,64，整个操作花费0.28秒！为何会这样？第一个例子中的四个值很可能在同一个缓存行里，每次一个处理器增加计数，这四个计数所在的缓存行将被无效，而其它处理器在下一次访问自己的计数器，都会遭遇到缓存未命中。这种多线程行为有效地禁止了缓存功能，削弱了程序性能。

门示例7：硬件复杂性

即使你懂得了缓存的工作原理，但有时候硬件行为仍会使你惊讶。不同处理器在工作时有不同的优化细节。

有些处理器上，L1缓存能够并发处理两路访问，如果访问是来自不同的存储体，而对同一存储体的访问只能串行处理。而且处理器聪明的优化策略也会使你感到惊讶，比如在伪共享的例子中，以前在一些没有微调的机器上运行表现并不良好，但我家里的机器能够对最简单的例子进行优化来减少缓存刷新。

下面是一个“硬件怪事”的奇怪例子：

    
      private static int A, B, C, D, E, F, G;
private static void Weirdness()
{
    for (int i = 0; i < 200000000; i++)
    {
        // do something...
    }
}