http://blog.jobbole.com/89759/
我的大多数读者都知道缓存是一种快速、小型、存储最近已访问的内存的地方。这个描述相当准确，但是深入处理器缓存如何工作的“枯燥”细节，会对尝试理解程序性能有很大帮助。
在这篇博文中，我将通过示例代码来说明缓存是如何工作的，以及它对现实世界中程序性能的影响。
虽然例子用的是 C#，但是不论哪种编程语言，对性能数据和最终结论的影响很小。
例1：内存访问和性能
你预计运行 循环2 比 循环1 快多少？
|
1
2
3
4
5
6
7
8
9
|
int
[] arr =
new
int
[64 * 1024 * 1024];
// 循环1
for
(
int
i = 0; i < arr.Length; i++)
arr[i] *= 3;
// 循环2
for
(
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之外的其他步长：
|
1
2
|
for
(
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）的大小
如今的计算机都有两级或者三级缓存，通常叫做L1，L2以及L3。如果你想知道不同缓存的大小，你可以使用SysInternals的CoreInfo工具，或者调用GetLogicalProcessorInfo Windows API。两个方法都会告诉你各级缓存的大小，以及缓存行的大小。
在我电脑上，CoreInfo报告我有一个32KB的L1数据缓存，一个32KB的L1指令缓存，和一个4MB的L2数据缓存。L1缓存是每个核心独享的，而每个L2缓存在两个核心间共享：
|
1
2
3
4
5
6
7
8
9
10
11
|
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个整数为步长遍历一个数组——这是修改每一个缓存行的一个简单方法。当我们遍历到最后一个值时，再回到开始向后遍历。我们将实验不同的数组长度，并且我们应该看到，每当数组长度超过一个缓存级别时，性能会随着降低。
下面是程序：
|
1
2
3
4
5
6
|
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：指令级并行
现在，让我们看一些不一样的东西。
下面这两个循环中，你认为哪个会更快一些？
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int
steps = 256 * 1024 * 1024;
int
[] a =
new
int
[2];
// 循环1
for
(
int
i=0; i < steps; i++) {
a[0]++;
a[0]++;
}
// 循环2
for
(
int
i=0; 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个缓存槽容纳不下就会出现竞争）。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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大小），和不同的步长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缓存。具体来说，现代多核机器拥有多层次的缓存机制，其中更快和更小的缓存属于独立的处理器。
当一个处理器在它的缓存中修改一个值时，其他的处理器不能再使用旧的值了。在所有的缓存中，这个内存地址将变成无效地址。另外，由于缓存的粒度是缓存行，而不是单独的字节，因此在所有缓存中的整个缓存行都变成无效！
为了演示这个问题，考虑下面的例子：
|
1
2
3
4
5
6
7
8
|
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;
}
}
|
在我的4核机器上，如果我在4个线程中调用UpdateCounter，参数分别是0、1、2、3，所有线程运行结束后花费的时间是4.3秒。
另一方面，如果我分别使用16、32、48、64的参数调用UpdateCounter，只花费了0.28秒！
为什么呢？在第一种情形下，所有的4个数据很可能位于同一个缓存行。内核每递增一个数值，它就使包含这4个值的那个缓存行无效。其他所有内核访问这个数值时，就会出现缓存未命中的情况。线程的这种行为使缓存失去了效果，消弱了程序的性能。
例7：硬件复杂性
即使你了解缓存工作的基本知识，但有时候硬件仍然会让你惊讶。在优化措施、启发式调度以及工作的细节上，不同的处理器存在差异。
在一些处理器上，当两次访问操作分别访问不同的内存体（Memory Bank）时，L1缓存能够并行执行这两次访问；而如果访问相同的内存体，则会串行执行。同样的，处理器的高级优化也会使你吃惊。例如，我过去在多台电脑上运行过的“缓存行共享假象”例子，在我家里的电脑上需要微调代码才能得到期望的结果——对于一些简单的情况电脑能够优化执行，以减少缓存失效。
下面是一个表明“硬件离奇性”的例子：
|
1
2
3
4
5
6
7
8
|
private
static
int
A, B, C, D, E, F, G;
private
static
void
Weirdness()
{
for
(
int
i = 0; i < 200000000; i++)
{
<something>
}
}
|
当我分别使用下面的三段不同代码替换“”时，我得到下面的运行时间：
|
1
2
3
4
|
<something> Time
A++; B++; C++; D++; 719 ms
A++; C++; E++; G++; 448 ms
A++; C++; 518 ms
|
对A、B、C、D的递增操作时间要比递增A、C、E、G的时间长。更离奇的是，只递增A和C使用了比递增A、C、E、G更长的时间！
我并不清楚这些时间数字背后的原因，但是我猜测它与内存体（Memory Bank）有关。如果有人能够解释它的原因，我将非常愿意倾听。
这个例子告诉我们，很难完全地预测硬件性能。你确实可以预测很多方面，但是最后，你需要测试并验证你的预测结果，这非常重要。
结论
真心希望本文能够帮助你理解缓存工作的细节，并在你的程序中应用这些知识。
校对注：*上的“ CPU 缓存”词条，非常详细，可温习。