建设公司网站需要多少钱,电商详情页模板免费下载,住房和城乡建设部网站执业资格注册中心,wordpress给用户发送邮件我的大多数读者都知道缓存是一种快速、小型、存储最近已访问的内存的地方。这个描述相当准确#xff0c;但是深入处理器缓存如何工作的“枯燥”细节#xff0c;会对尝试理解程序性能有很大帮助。在这篇博文中#xff0c;我将通过示例代码来说明缓存是如何工作的#xff0c;…我的大多数读者都知道缓存是一种快速、小型、存储最近已访问的内存的地方。这个描述相当准确但是深入处理器缓存如何工作的“枯燥”细节会对尝试理解程序性能有很大帮助。在这篇博文中我将通过示例代码来说明缓存是如何工作的以及它对现实世界中程序性能的影响。虽然例子用的是 C#但是不论哪种编程语言对性能数据和最终结论的影响很小。例1内存访问和性能你预计运行 循环2 比 循环1 快多少123456789int[] arr new int[64 * 1024 * 1024];// 循环1for (int i 0; i arr.Length; i) arr[i] * 3;// 循环2for (int i 0; i arr.Length; i 16) arr[i] * 3;第一个循环对数组中的每个元素都乘以 3而第二个循环对每隔 16 个元素的数据乘以 3。第二个循环只做了第一个循环的大约6%的计算量但是在现代计算机上这两个 for 循环运行的时间差不多相等我电脑上分别是 80 和 78 毫秒。这两个循环耗费相同时间的原因与内存有关。这些循环的运行时间主要由访问数组内存来决定而不是整数乘法。并且我在例2中将解释硬件对这两个循环执行相同的主存储器访问。例2缓存行(cache lines)的影响校对注什么是 cache lines 在内存和缓存直接传输的数据是大小固定的成块数据称为 cache lines 。我们来深入地研究一下这个例子。我们尝试1和16之外的其他步长12for (int i 0; i arr.Length; i K) arr[i] * 3;下面是这个循环运行不同步长K所花费的时间注意步长在1到16的范围内时循环的运行时间几乎不变。但是从16开始步长每增加一倍其运行时间也减少一半。其背后的原因是如今的CPU并不是逐个字节地访问内存。相反它以典型的64字节的块为单位取内存称作缓存行cache lines。当你读取一个特定的内存地址时整个缓存行都被从主内存取到缓存中。并且此时读取同一个缓存行中的其他数值非常快因为16个整数占用了64字节一个缓存行因此步长从1到16的for循环都必须访问相同数量的缓存行即数组中的所有缓存行。但是如果步长是32我们只需要访问约一半的缓存行步长是64时只有四分之一。理解缓存行对特定类型的程序优化非常重要。例如数据对齐可能会决定一个操作访问一个还是两个缓存行。如我们上面例子中看到的它意味着在不对齐的情形下操作将慢一倍。例3一级缓存L1和二级缓存L2的大小如今的计算机都有两级或者三级缓存通常叫做L1L2以及L3。如果你想知道不同缓存的大小你可以使用SysInternals的CoreInfo工具或者调用GetLogicalProcessorInfo Windows API。两个方法都会告诉你各级缓存的大小以及缓存行的大小。在我电脑上CoreInfo报告我有一个32KB的L1数据缓存一个32KB的L1指令缓存和一个4MB的L2数据缓存。L1缓存是每个核心独享的而每个L2缓存在两个核心间共享1234567891011Logical 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个整数为步长遍历一个数组——这是修改每一个缓存行的一个简单方法。当我们遍历到最后一个值时再回到开始向后遍历。我们将实验不同的数组长度并且我们应该看到每当数组长度超过一个缓存级别时性能会随着降低。下面是程序123456int steps 64 * 1024 * 1024; // Arbitrary number of stepsint 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指令级并行现在让我们看一些不一样的东西。下面这两个循环中你认为哪个会更快一些1234567891011121314int steps 256 * 1024 * 1024;int[] a new int[2];// 循环1for (int i0; i steps; i) { a[0]; a[0]; }// 循环2for (int i0; i steps; i) { a[0]; a[1]; }结果是至少在我测试过的所有电脑上第二个循环都比第一个循环快一倍。为什么呢这与两个循环主体中指令间的依赖关系有关。在第一个循环主体中指令间的依赖关系如下但是第二个循环中依赖关系是这样的现代处理器包含多个有并行机制的部件它能同时读取L1的两个内存地址或者同时运行两条简单的算数指令。在第一个循环内处理器不能施展这种指令级并行但是第二个循环中可以。[更新]reddit上很多人问编译器优化的事情以及是否能够把 { a[0]; a[0]; } 优化成 { a[0]2; }。事实上在涉及数组访问时C# 编译器和 CLR JIT 不会做这个优化。我在 release 模式下即包含优化选项编译了所有的例子并在JIT之后的代码中检查是否有这个优化但是没有发现。例5缓存相关性缓存设计的一个重要决策是主存的每个块是否能够放入任何一个缓存槽或某几个缓存槽中的一个。译者注这里一个缓存槽和前面的缓存行相同按照槽的大小把主存分成若干块以块为单位与缓存槽映射。下文提到的块索引chunk index等于主存大小除以槽大小。把缓存槽映射到内存块有 3 种可选方案1. 直接映射缓存Direct mapped cache每个内存块只能存储到一个缓存槽。一个简单方案是通过块索引把内存块映射到缓存槽块索引 % 缓存槽数量即取余数操作。映射到同一个槽的内存块不能同时存储在缓存中。2. N路关联缓存N-way set associative cache每个内存块映射到N个特定缓存槽的任意一个槽。例如一个16路缓存任何一个内存块能够被映射到16个不同的缓存槽。通常具有相同低bit位地址的内存块共享相同的16个槽。3. 完全关联缓存Fully associative cache每个内存块可以被映射到任意一个缓存槽cache slot。事实上缓存操作和哈希表很像。直接映射会遭遇冲突的问题——当多个块同时竞争缓存的同一个槽时它们不停地将对方踢出缓存这将降低命中率。另一方面完全关联过于复杂很难在硬件层面实现。N路关联是典型的处理器缓存设计方案因为它在实现难度和提高命中率之间做了良好的折衷。例如我电脑上的4M L2 缓存采用 16 路关联的方案。所有的64字节大小的内存块被分配到集合中基于块索引的低字节同一个集合中的块竞争使用 L2 缓存的16个槽。由于 L2 缓存有65536 个槽而每个集合需要16个槽因此我们有4096个集合。由此块索引的低12比特能够确定这个块所在的集合(2^12 4096)。进而可以计算出相差262144字节倍数的地址4096*64会竞争同一个槽。为了使缓存相关性的影响表现出来我需要重复地访问同一个集合中的超过16个块译者注这样16个缓存槽容纳不下就会出现竞争。12345678910111213141516public 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大小和不同的步长K来运行UpdateEveryKthByte()。下面的图呈现了结果颜色越绿表示运行时间越长颜色越白表示运行时间越短。蓝色区域运行时间较长部分表示当我们重复更新数组值时这些值不能同时保存在缓冲中。比较亮的区域对应的运行时间约是80毫秒接近白色的区域对饮运行时间约是10毫秒。让我来解释一下图中的蓝色部分1. 为什么会出现竖直线竖直线对应的这些步长在一次循环中访问到的值跨越了同一个集合中的多个内存块大于16个。对于这些步长访问到的值我电脑上的16路关联缓存不能同时保存这些值。一些糟糕的步长是2的幂次方256和512。例如当数组是8MB步长是512时。8MB的缓存行包含地址互相间隔262144字节倍数的32个值。由于512能够整除262144因此在一次循环内这32个值都会被访问到。由于32大于16因此这32个值将一直竞争缓存中相同的16个槽。而一些不是2幂次方的值则是因为不够幸运它们刚好访问到了同一个集合内的很多值。这些步长同样会显示成蓝色线。2. 为什么蓝色线在4MB位置结束了呢当数组长度为4MB或者更小时16路关联缓存的表现和完全关联缓存相同。16路关联缓存最多可以保存以262144字节长度分割的16个缓存行。在4MB中由于16 * 262144 4194304 4MB因此不会出现第17个或者更多个集合。3. 为什么蓝色的三角形位于左上角在三角形的区域我们不能把所需的数据同时放入缓存——与缓存相关性无关而与L2缓存大小有关系。举个数组长度为16MB、步长为128时的例子。我们重复地每隔128个字节更新数组中的值即每次跨越了一个64字节的内存块。对于16MB的数组每隔一个块存储到缓存这样我们需要8MB大小的缓存。但是我机器的缓存只有4MB。即使我电脑上的4MB缓存使用完全关联的方式它仍然无法容纳8MB的数据。4. 为什么三角形最左侧颜色变淡了呢注意变淡部分是从0开始到64结束——正好是一个缓存行正如例1和例2中解释的访问同一个缓存行内的其他数据非常快。例如当步长为16时需要4步到达下一个缓存行。因此这4次内存访问的代价和1次访问差不多。由于对于所有用例步数是相同因此步数越少运行时间越短。当扩展这个图时规律是一样的缓存相关性非常有趣并且容易被证实但是与本文中讨论的其他问题相比它并不是一个很大的问题。当你编写程序时它不应该是你首先要考虑的问题。例6缓存行共享假象在多核机器上缓存遇到了另一个问题——一致性。不同的核有完全独立或者部分独立的缓存。在我的电脑上L1缓存是独立的这很常见有两组处理器每组处理器共享一个L2缓存。具体来说现代多核机器拥有多层次的缓存机制其中更快和更小的缓存属于独立的处理器。当一个处理器在它的缓存中修改一个值时其他的处理器不能再使用旧的值了。在所有的缓存中这个内存地址将变成无效地址。另外由于缓存的粒度是缓存行而不是单独的字节因此在所有缓存中的整个缓存行都变成无效为了演示这个问题考虑下面的例子12345678private 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; }}在我的4核机器上如果我在4个线程中调用UpdateCounter参数分别是0、1、2、3所有线程运行结束后花费的时间是4.3秒。另一方面如果我分别使用16、32、48、64的参数调用UpdateCounter只花费了0.28秒为什么呢在第一种情形下所有的4个数据很可能位于同一个缓存行。内核每递增一个数值它就使包含这4个值的那个缓存行无效。其他所有内核访问这个数值时就会出现缓存未命中的情况。线程的这种行为使缓存失去了效果消弱了程序的性能。例7硬件复杂性即使你了解缓存工作的基本知识但有时候硬件仍然会让你惊讶。在优化措施、启发式调度以及工作的细节上不同的处理器存在差异。在一些处理器上当两次访问操作分别访问不同的内存体Memory Bank时L1缓存能够并行执行这两次访问而如果访问相同的内存体则会串行执行。同样的处理器的高级优化也会使你吃惊。例如我过去在多台电脑上运行过的“缓存行共享假象”例子在我家里的电脑上需要微调代码才能得到期望的结果——对于一些简单的情况电脑能够优化执行以减少缓存失效。下面是一个表明“硬件离奇性”的例子12345678private static int A, B, C, D, E, F, G;private static void Weirdness(){ for (int i 0; i 200000000; i) { something }}当我分别使用下面的三段不同代码替换“”时我得到下面的运行时间1234something TimeA; B; C; D; 719 msA; C; E; G; 448 msA; C; 518 ms对A、B、C、D的递增操作时间要比递增A、C、E、G的时间长。更离奇的是只递增A和C使用了比递增A、C、E、G更长的时间我并不清楚这些时间数字背后的原因但是我猜测它与内存体Memory Bank有关。如果有人能够解释它的原因我将非常愿意倾听。这个例子告诉我们很难完全地预测硬件性能。你确实可以预测很多方面但是最后你需要测试并验证你的预测结果这非常重要。结论真心希望本文能够帮助你理解缓存工作的细节并在你的程序中应用这些知识。来源 http://blog.jobbole.com/89759/ 来自为知笔记(Wiz)转载于:https://www.cnblogs.com/ssslinppp/p/4750310.html
