处理器缓存影响大观园

　　大多数读者都明白缓存是一个用于存储最近访问的内存位置的高速小容量存储器。这个描述是相当准确的，但是处理器缓存如何工作的“无聊”细节可以更好的帮助我们了解程序的性能。

　　在这篇博客中，我会用代码示例来说明缓存工作的各个方面及其在实际运行中对程序性能的影响。

　　这些示例是用c#写的，但不同语言的实现将会对性能的得分以及得出的结论有一些小的影响。

　　Example 1: 内存访问和性能

　　你认为循环2的运行时间比循环1要快多少？

 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;

　　循环1将数组中的每个值都乘以3，循环2将数组中每隔16个元素的值乘以3。第二个循环仅仅只做了第一个循环所做的6%，但是在现在的机器上，这两个循环花费的时间几乎相同：分别为80ms和78ms。

　　这个现象出现的原因和内存有关。上述循环运行的时间主要花费在数组的内存访问上，而不是在整数乘法上。我会在例2中解释为什么硬件对两个循环执行了相同的内存访问。

　　Example 2: cache lines的影响

　　让我们深入探索这个例子。接下来我们将会使用其它步长值，不仅仅是1和16：

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

　　下面就是在循环中不同的步长值(K)的运行时间：

　　注意,步长在1到16之间变化，但是运行时间却几乎没有改变。但是从16以后，步长每增加一倍,运行时间就为原来的一半。

　　这种现象的原因就是现代的CPU并不是以1byte1byte的访问内存，而是，它们会一块为单位为取得，典型的就是64bytes，这就叫做cache lines.当你要读取特定的内存时，这cache line就会获取整块内存到缓存中，而且，从这cache line中访问其它值更快。

　　因为16 ints 就是64bytes（一个cache line）,for循环步长从1到16，都在会使用相同的cache lines: 所有的cache lines都在数组中。但是一旦步长是32,我们就会使用其它一个的cache line，步长为64时，就会使用4个cache line.

　　理解了cache line，对于某些类型的程序优化十分重要。例如，数据队列可能会影响到一个操作使用一个或者两个cache line。正如我们上面看到那样，在非线性的情况，这个操作可能会慢两倍。

　　Example 3: L1 和 L2缓存大小

　　现在的计算机都有二级或三级缓存，通常称为L1, L2可能还有L3。如果你想知道不同缓存的大小，可以使用CoreInfo 这样的SysInternals工具，或使用GetLogicalProcessorInfo 这样的Windows API 调用。两种方法都会在缓存大小之外，告诉你高速缓存行的大小。

　　在我的机器上，CoreInfo报告称我有一个32kB L1数据缓存，一个32kB L1指令缓存，以及一个4MB L2数据缓存。L1缓存是每个核一个，L2缓存则在双核之间共享：

 Logical Processor to Cache Map: *---  Data Cache          0, Level 1,   32 KB, Assoc   8, LineSize  64 *---  Instruction Cache   0, Level 1,   32 KB, Assoc   8, LineSize  64 -*--  Data Cache          1, Level 1,   32 KB, Assoc   8, LineSize  64 -*--  Instruction Cache   1, Level 1,   32 KB, Assoc   8, LineSize  64 **--  Unified Cache       0, Level 2,    4 MB, Assoc  16, LineSize  64 --*-  Data Cache          2, Level 1,   32 KB, Assoc   8, LineSize  64 --*-  Instruction Cache   2, Level 1,   32 KB, Assoc   8, LineSize  64 ---*  Data Cache          3, Level 1,   32 KB, Assoc   8, LineSize  64 ---*  Instruction Cache   3, Level 1,   32 KB, Assoc   8, LineSize  64 --**  Unified Cache       1, Level 2,    4 MB, Assoc  16, LineSize  64

　　我们通过实验来验证一下这些数字。为了做到这一点，我们逐步操作一个数组，这个数组每隔16个整数增加一——这是编辑每个缓存行的一种简单方法。当我们访问到最后一个数值，再从头循环。我们拿不同的数组大小进行实验，我们可以看到在数组大小溢出一个缓存级别的时候，性能有一个下降。

　　这里是程序：

 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缓存的大小。

　　Example 4: 指令级并行性

　　现在，我们看一些不一样的东西。在这两个循环中，你认为哪一个会更快一些？

 int steps = 256 * 1024 * 1024; int[] a = new int[2];  // Loop 1 for (int i=0; i<steps; i++) { a[0]++; a[0]++; }  // Loop 2 for (int i=0; i<steps; i++) { a[0]++; a[1]++; }

　　结论是第二个循环大约是第一个循环的两倍快，至少在我测试的所有机器上是这样的。为什么呢？它与两个循环体之间的操作有关。

　　在第一个循环体内，操作之间相互依赖关系如下：

　　但在第二个例子中，我们只有这些依赖：

　　现代处理器有多种部件具有一定的并行性：它可以同时访问L1中的两个内存地址，或者执行两个简单的算术运算。在第一个循环中，处理器不能发挥这种指令级别的并行性，但在第二个循环中，它可以。

　　【更新】：reddit网站上许多人询问编译器优化，是否{ a[0]++; a[0]++; }会优化为{ a[0]+=2; }。实际上，C#编译器和CLR JIT（Common Language Runtime通用语言运行时 Just In-Time compile即时编译 ）不会做这种优化——当牵涉到访问数组时不会。我在发布模式创建了所有的测试（即具有优化模式），但是我观察了JIT-ted编译，验证了优化不会影响到这个结果。

　　Example 5: 缓存映射方式

　　缓存设计的一个最关键的因素就是主存块能否被存储在缓存槽当中或者就是缓存槽的一部分。

　　内存映射到缓存槽有三条可能的途径：

1. 直接映射方式：

   每个内存块只能被缓存中的一个特别的缓存槽所存储。一个简单的解决办法就是用内存块的索引chunk_index和缓存槽来进行映射（通过chunk_index和cache_slots求余的方式）。两个映射到相同缓存槽的内存块不能同时被储存在缓存当中。

2. N路组关联映射方式：
   

   任何一个内存块只能被缓存里的N个组中的一个缓存槽所存储。举个例子，在16路缓存中，每一个内存块可以被16个不同的缓存槽所存储，一般情况下，索引最低位字节相同的内存块将会共享16个缓存槽。

3. 全关联映射方式：

   每个内存块可以被任何缓存槽所存储。实际上，这种缓存的方式和哈希表是一样的。

　　直接缓存映射方式的效率将会受到冲突的影响——当多个值共同竞争同一缓存槽时，它们将不断相互驱逐，命中率直线下降。另一方面，全关联映射方式的硬件实现复杂而又昂贵。所以目前处理器缓存的典型解决方案是 N路组关联映射方式，因为它在实现的简单性和较好的命中率之间做了很好的权衡。

　　例如,我电脑上的4MB二级缓存采用的是16路组关联映射方式。所有64字节的内存块将被分成组（按照内存块索引的最低位字节来划分），相同组的内存块共同竞争二级缓存中的16个缓存槽。

　　由于二级缓存中有65536个缓存槽,每组需要16个缓存槽,二级缓存共可划分为4096个组。所以内存块将会映射到的组将由内存块索引的最低12位决定(212 = 4,096)。其结果就是cache line中262144个字节整数倍（4096*64）的内存地址将会共同竞争同一缓存槽。我电脑上的缓存可以容纳16路这样的cache line。

　　为了使缓存映射的效果更明显，我需要从同一组中重复取出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个元素的值将会增加1,一旦达到了数组的末尾，将从头开始再次循环。运行足够长时间后（2^20步），循环结束。

　　我用不同的数组长度（每次增加1MB）和不同的步长来运行UpdateEveryKthByte()，得到了如下结果，蓝色表示运行时间比较长，白色表示运行时间比较短:

　　蓝色区域（运行时间比较长）中更新的值由于不断被重复遍历，所以不能够被同时保存在缓存中。亮蓝色区域的运行时间花费在80ms左右，白色区域的运行时间花费在10ms左右。

　　解释一下图标的蓝色部分：

　　1. 为什么会出现蓝色的竖线？蓝色竖线表示步长会访问很多（>16)相同集合中的内存。对于这些步长我们不能同时把所有的访问内存保持在一个16路相关的缓存中。一些很差的步长是2的整数次幂：256 和 512。 例如，考虑步长512和数组大小为8M. 一个8M的缓存行包含32个被262,144分割的值。所有这些值都会被我们的每一次循环更新，因为262,144 可以被512整除。所以这32个值会互相竞争同一个16slot的集合。一些不是2的整数次幂的也不幸地不成比例的过多访问同一个集合中的值.(什么样的值会不幸？）

　　2. 为什么竖线会在数据大小为4M时结束？ 当数组大小为4MB或者更小时，16路相关的cache正好跟全相关缓存一样。262,144*14 = 4M，一个16路的相关cache能缓存所有以262,144对齐的数据。

　　3. 为什么蓝色的三角形在左上方？ 在三角形区域，我们不能同时保存必须的数据…不是因为相关方式，而是简单的因为L2缓存大小限制。例如，假设数组大小为16MB步长为128,。 我们不断更新间隔为128的字节，这意味着我们会访问另外的64个字节的内存块。所以为了保存每一个 缓存行，我们需要8M的cache。但我的机器只有4MB的缓存。即使采用全相关，仍然不能缓存8MB的数据。

　　4. 为什么在左边三角形淡化？步长从0到64， 一个缓存行！就像在example1和2里所阐释的，额外的对同一个缓存行的访问几乎是免费的。例如，如果 步长为16， 每四步会访问另一个缓存行，所以我们用一行的代价得到了四次内存访问。

　　当你扩展这幅图的时候，这些模式一直都是如此：

　　缓存结合性理解了就很有趣，而且它当然可以被证明，不过和本文讨论的其他问题比起来，它应该是一个较小的问题。当然，它并不是在你写程序的时候，脑海里应该浮现出来的东西。

　　Example 6: 错误的缓存线共享

　　在多核的机器上，缓存又遇到另外一个问题——一致性。不同的核心有完全或者部分分离的缓存。在我的机器上，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调用UpdateCounter，需要0.28秒！

　　为什么？在第一种情况中，所有四个值可能出现在同一个缓存线。每次一个核心增加counter，它会使含有所有四个counter的缓存线失效。所有其它核心下次访问自己的counter的时候都会出现缓存不命中。这种线程行为使缓存失效，严重影响程序的性能。

　　Example 7: 硬件复杂性

　　即使你知道了缓存工作的基本方式，硬件有时也会让你惊讶。不同的处理器在优化、启发和微妙的细节上有所不同。

　　对于某些处理器，如果从不同的bank访问缓存线，L1缓存可以并行处理两个访问，如果属于同一个bank那么就串行执行。另外处理器的优化也会让你惊讶。例如错误的共享的例子，我在许多机器上都试过，但是在我的机器上就不正常——我的机器可以优化执行减少缓存失效。

　　这是一个“硬件不可思议”的古怪的例子：

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

　　当我用三个不同的代码块替换"<something>"，获得下述结果：

　　增加A,B,C,D比增加A,C,E,G花费时间长。更不可思议的是增加A,C比增加A,C,E,G花费时间长！

　　我不太确定其中的原因，但是我怀疑与内存有关。如果有人可以解释其中的原因，我会很谦虚的聆听。

　　这个例子教给我们完全预测硬件性能是很难的。有很多你觉得可以预测，但是最后，测量和验证你的程序是非常重要的。

　　英文来源：http://igoro.com/archive/gallery-of-processor-cache-effects/

欢迎大家阅读《处理器缓存影响大观园》,跪求各位点评,若觉得好的话请收藏本文，by 搞代码

喜欢 (0)赏

[搞代码]

分享 (0)