七个例子帮你更好地理解 CPU 缓存

我的大多数读者都知道缓存是一种快速、小型、存储最近已访问的内存的地方。这个描述相当准确,但是深入处理器缓存如何工作的“枯燥”细节,会对尝试理解程序性能有很大帮助。

在这篇博文中,我将通过示例代码来说明缓存是如何工作的,以及它对现实世界中程序性能的影响。

虽然例子用的是 C#,但是不论哪种编程语言,对性能数据和最终结论的影响很小。

例1:内存访问和性能

你预计运行 循环2 比 循环1 快多少?

第一个循环对数组中的每个元素都乘以 3,而第二个循环对每隔 16 个元素的数据乘以 3。第二个循环只做了第一个循环的大约6%的计算量,但是在现代计算机上,这两个 for 循环运行的时间差不多相等:我电脑上分别是 80 和 78 毫秒。

这两个循环耗费相同时间的原因与内存有关。这些循环的运行时间主要由访问数组内存来决定,而不是整数乘法。并且我在例2中将解释,硬件对这两个循环执行相同的主存储器访问。

例2:缓存行(cache lines)的影响

(校对注:什么是 cache lines ?在内存和缓存直接传输的数据是大小固定的成块数据,称为 cache lines 。)

我们来深入地研究一下这个例子。我们尝试1和16之外的其他步长:

下面是这个循环运行不同步长(K)所花费的时间:

注意步长在1到16的范围内时,循环的运行时间几乎不变。但是从16开始,步长每增加一倍,其运行时间也减少一半。

其背后的原因是,如今的CPU并不是逐个字节地访问内存。相反,它以(典型的)64字节的块为单位取内存,称作缓存行(cache lines)。当你读取一个特定的内存地址时,整个缓存行都被从主内存取到缓存中。并且,此时读取同一个缓存行中的其他数值非常快!

因为16个整数占用了64字节(一个缓存行),因此步长从1到16的for循环都必须访问相同数量的缓存行:即数组中的所有缓存行。但是如果步长是32,我们只需要访问约一半的缓存行;步长是64时,只有四分之一。

理解缓存行对特定类型的程序优化非常重要。例如,数据对齐可能会决定一个操作访问一个还是两个缓存行。如我们上面例子中看到的,它意味着在不对齐的情形下,操作将慢一倍。

例3:一级缓存(L1)和二级缓存(L2)的大小

如今的计算机都有两级或者三级缓存,通常叫做L1,L2以及L3。如果你想知道不同缓存的大小,你可以使用SysInternals的CoreInfo工具,或者调用GetLogicalProcessorInfo Windows API。两个方法都会告诉你各级缓存的大小,以及缓存行的大小。

在我电脑上,CoreInfo报告我有一个32KB的L1数据缓存,一个32KB的L1指令缓存,和一个4MB的L2数据缓存。L1缓存是每个核心独享的,而每个L2缓存在两个核心间共享:

让我们通过实验来核实一下。要做到这一点,我们将以16个整数为步长遍历一个数组——这是修改每一个缓存行的一个简单方法。当我们遍历到最后一个值时,再回到开始向后遍历。我们将实验不同的数组长度,并且我们应该看到,每当数组长度超过一个缓存级别时,性能会随着降低。

下面是程序:

下面是时间计时:

你可以看到在 32KB 和 4MB 后有明显的下降——这正是我电脑上L1和L2缓存的大小。

例4:指令级并行

现在,让我们看一些不一样的东西。

下面这两个循环中,你认为哪个会更快一些?

结果是,至少在我测试过的所有电脑上,第二个循环都比第一个循环快一倍。为什么呢?这与两个循环主体中指令间的依赖关系有关。

在第一个循环主体中,指令间的依赖关系如下:

但是第二个循环中,依赖关系是这样的:

现代处理器包含多个有并行机制的部件:它能同时读取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个缓存槽容纳不下就会出现竞争)

这个方法对数组中每隔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缓存。具体来说,现代多核机器拥有多层次的缓存机制,其中更快和更小的缓存属于独立的处理器。

当一个处理器在它的缓存中修改一个值时,其他的处理器不能再使用旧的值了。在所有的缓存中,这个内存地址将变成无效地址。另外,由于缓存的粒度是缓存行,而不是单独的字节,因此在所有缓存中的整个缓存行都变成无效!

为了演示这个问题,考虑下面的例子:

在我的4核机器上,如果我在4个线程中调用UpdateCounter,参数分别是0、1、2、3,所有线程运行结束后花费的时间是4.3秒。

另一方面,如果我分别使用16、32、48、64的参数调用UpdateCounter,只花费了0.28秒!

为什么呢?在第一种情形下,所有的4个数据很可能位于同一个缓存行。内核每递增一个数值,它就使包含这4个值的那个缓存行无效。其他所有内核访问这个数值时,就会出现缓存未命中的情况。线程的这种行为使缓存失去了效果,消弱了程序的性能。

例7:硬件复杂性

即使你了解缓存工作的基本知识,但有时候硬件仍然会让你惊讶。在优化措施、启发式调度以及工作的细节上,不同的处理器存在差异。

在一些处理器上,当两次访问操作分别访问不同的内存体(Memory Bank)时,L1缓存能够并行执行这两次访问;而如果访问相同的内存体,则会串行执行。同样的,处理器的高级优化也会使你吃惊。例如,我过去在多台电脑上运行过的“缓存行共享假象”例子,在我家里的电脑上需要微调代码才能得到期望的结果——对于一些简单的情况电脑能够优化执行,以减少缓存失效。

下面是一个表明“硬件离奇性”的例子:

当我分别使用下面的三段不同代码替换“”时,我得到下面的运行时间:

对A、B、C、D的递增操作时间要比递增A、C、E、G的时间长。更离奇的是,只递增A和C使用了比递增A、C、E、G更长的时间!

我并不清楚这些时间数字背后的原因,但是我猜测它与内存体(Memory Bank)有关。如果有人能够解释它的原因,我将非常愿意倾听。

这个例子告诉我们,很难完全地预测硬件性能。你确实可以预测很多方面,但是最后,你需要测试并验证你的预测结果,这非常重要。

结论

真心希望本文能够帮助你理解缓存工作的细节,并在你的程序中应用这些知识。

校对注:维基百科上的“ CPU 缓存”词条,非常详细,可温习。

5 12 收藏 2 评论

关于作者:Sheng Gordon

目前在职,从事IT业。工作7年有余,使用过Delphi,C++,Python等工具和语言。我的新浪微博@GordonSheng 个人主页 · 我的文章 · 23

相关文章

可能感兴趣的话题



直接登录
最新评论
  • JackPy   2015/08/21

    第三个例子,代码写的太简略了,不知道写的什么意思,原文出处里面也有人有一样的疑惑

    • JackPy   2015/08/21

      哦,后面又看明白了,lengthMod 对应着坐标轴的横坐标, (i * 16) & lengthMod 的结果始终小于 lengthMod , 这样 (i * 16) 超过数组长度时就重新开始了,这样保证了每个测试用例的变量操作总次数是一样的

跳到底部
返回顶部