Go语言中常见100问题-#91 Not understanding CPU caches

CPU缓存

机械同理心（mechanical sympathy）是三届F1世界冠军杰基·斯图尔特 (Jackie Stewart) 创造的一个术语。

❝不一定要成为一名工程师才能成为一名赛车手，但必须有机械同理心 ❞

简而言之，无论是F1赛车、飞机或计算机，在了解系统是如何设计使用的之后，我们可以遵循它们的工作方式，以获得最佳性能。

本文我们主要学习CPU缓存的工作方式，利用它帮助我们优化Go应用程序。

CPU架构

下面以 Intel Core i5-7300 为例说明CPU结构组成，现代CPU依靠缓存来加速内存访问，在大多数情况下有三个缓存级别：L1、L2和L3。在 i5-7300上，它们的大小如下：

• L1:64KB
• L2:256KB
• L3:4MB

i5-7300 有2颗物理核4个逻辑核（虚拟核或线程），在 Intel 家族中，将一个物理核分成多个逻辑核称为超线程。

整个概览图如下，图中Tn表示线程n，每个物理核（Core 0和Core 1）分别被划分成两个逻辑核（thread 0和thread 1）. L1缓存被分为两部分：L1D和L1I，L1D用于缓存数据，L1I用于缓存指令，每部分大小为32KB. 注意缓存不仅仅是缓存数据，当CPU执行应用程序时，缓存一些具有相同内容的指令，可以加快执行速度。

内存位置离逻辑核心越近，访问速度就越快，详情参考 http://mng.bz/o29v.

• L1: 大约1纳秒
• L2: 大约比L1慢4倍
• L3: 大约比L1慢10倍

缓存的位置也可以解释这些差异，从上图可以看到，L1和L2每个Core一个，称为片上缓存，意味着它们与处理器的其余部分属于同一块芯片.相反，L3 是片外缓存，这也解释了与L1和L2相比的延迟差异.

主存（RAM）平均访问时间比较L1慢50到100倍, 访问存储在L1上的100个变量代价与访问主存上1个变量的相同。因此，作为一个Gopher, 应该让我们编写的应用程序尽可能使用CPU缓存。

缓存行

理解什么是缓存行至关重要，在弄懂是什么之前我们先来了解为啥需要缓存行。当某个具体内存被访问时（例如读一个变量），接下来很可能发生下面的事情：

• 相同的位置可能会被再次访问
• 附近的位置将被访问

前者说的是时间局部性，后者说的是空间局部性，它们都是引用局部性原理中的一部分。

下面看一个求和代码例子，具体代码如下：

func sum(s []int64) int64 {
 var total int64
 length := len(s)
 for i := 0; i < length; i++ {
  total += s[i]
 }
 return total
}

上述程序中，被多次访问的局部变量有：i, length, total. 整个迭代过程中，这些变量会持续被访问。空间局部性适用于指令和切片s, 因为切片的底层是一个连续数组，在这种情况下，访问了s[0]后还会访问s[1]、s[2]等。

时间局部性也是我们需要CPU缓存行的原因之一：加快访问相同变量的速度。再加上有空间局部性，所以CPU在进行拷贝的时候不是将单一将一个变量的内容从内存拷贝到CPU缓存中，而是按缓存行拷贝。

缓存行是一个有固定大小的连续的内存段，大小通常为64字节（8个int64类型变量大小）。CPU在进行内存拷贝时一次性拷贝缓存行大小的内存块， 由于缓存有层级关系，当CPU要访问某个具体内存时，它会先检查是否已在L1缓存中，如果L1中没有再检查L2缓存，如果L2缓存也没有再检查L3缓存，如果L3缓存中也没有，最后才访问内存取内容。

sum函数第一次循环时会范围s[0]元素，但是s[0]的内容并不缓存中（L1/L2/L3）, 如果CPU决定缓存此变量内容，它会按缓存行拷贝，如下图所示，一次性拷贝8个int64到CPU缓存。

首次访问s[0]会导致cache miss，因为它的地址还未进行过缓存。这种失效称为强制失效（compulsory miss）. 但是，一旦CPU获取到 0x000 内存块，接下来访问s[1]到s[7]就会缓存命中，同理在访问s[8]的时候也会导致cache miss，然后将 0x100 内存块拷贝到缓存中。

概括起来，整个循环过程一共产生了2次强制失效和14次缓存命中。

❝CPU缓存策略：也许你想知道CPU拷贝内存块的策略是什么？例如，它是将内存中的数据向L1、L2和L3都复制一份吗？还是只复制到L1,此时，L2和L3咋办呢？答案是存在不同的拷贝策略，有时缓存具有包含性（例如，L2中的数据在L3中也存在），也有时缓存具有互斥性（例如，牺牲性缓存（victim cahce）L3只能从L2中获取内容），通常这些缓存策略被CPU供应商隐藏，所以，本文不会深入讨论这个话题。 ❞

现在通过具体的例子来看看CPU缓存对速度提升效果。实现两个求和函数sum2和sum8，sum2每次跳过2个元素相加，sum8每次跳过8个元素相加，实现代码如下。

func sum2(s []int64) int64 {
    var total int64
    for i := 0; i < len(s); i+=2 {
        total += s[i]
    }
    return total
}
 
func sum8(s []int64) int64 {
    var total int64
    for i := 0; i < len(s); i += 8 {
        total += s[i]
    }
    return total
}

对上面函数分别进行benchmark性能测试，我们初步感受sum8应该比sum2块4倍，因为sum8在对s进行求和时步进是sum2的4倍。但是实测结果不是这样，sum8只比sum2快大概10%。

为啥与我们预期的不一致呢？答案是与缓存行有关。一个缓存行通常是64字节，最多包含8个 int64 类型变量。上述程序中循环占用的时间主要来自内存访问而不是加法指令。sum2中 3/4 的情况都是缓存命中的，所以sum8和sum2在执行时间上没有显著差别。通过这个例子说明了为啥缓存行很重要，如果我们没有“机械同理心”（这里指CPU是如何缓存数据），很容易被自己的直觉所蒙蔽。

结构体切片 vs 切片结构体

下面继续讨论局部性问题，并通过一个具体的空间局部性示例进行说明。第一个函数sumFoo代码如下，定义了一个Foo结构体，在sumFoo中对Foo结构体切片进行求和。

type Foo struct {
 a int64
 b int64
}

func sumFoo(foos []Foo) int64 {
 var total int64
 for i := 0; i < len(foos); i++ {
  total += foos[i].a
 }
 return total
}

第二个函数sumBar对结构体Bar中的切片a进行求和，完整代码如下。

type Bar struct {
 a []int64
 b []int64
}

func sumBar(bar Bar) int64 {
 var total int64
 for i := 0; i < len(bar.a); i++ {
  total += bar.a[i]
 }
 return total
}

猜猜这个两个函数的执行时间是否一样？在运行benchmark之前，先来看看它们在内存中的布局是啥样的。如下图所示，切片中含有的元素个数都是16个。Foo切片的大小为16，每个切片中的元素是Foo结构体，含有a和b, 结构体Bar中切片a的大小也是16. 图中标记为黑色条块的元素即为求和时要使用到。

在sumFoo函数中，接收的是一个切片参数，切片中的元素类型为Foo, 它包含两个元素a和b, 在内存中的布局是一系列的a和b交替排列。相反在sumBar函数中，接收的是一个结构体对象，它含有两个切片a和b两个字段，所以在内存中的布局是一连串的a,然后是一连串的b. 两种布局占用的内存空间是一样的，区别在于迭代所有的a, 第一种需要4个行缓存，而第二种只需要2个行缓存。

对这两个函数进行基准测试，测试结果 sumBar 会更快（大约快了 20%），主要原因是第二种有更好的空间局部性使得 CPU 获取更少缓存行，访问内存次数更少。

通过上述程序，我们认识到了程序的空间局部性，为了使程序有更好性能，应该合理组织数据以充分利用每个单独的缓存行的内容。

可预测性

可预测性指CPU预测应用程序对其加快执行速度。下面看一个缺乏预测性的例子，以及对程序性能产生的影响。

函数linkedList实现对一个链表中的数据进行求和，依次遍历每个元素，获取元素值，然后移动到下一个节点。

type node struct {
 value int64
 next  *node
}

func linkedList(n *node) int64 {
 var total int64
 for n != nil {
  total += n.value
  n = n.next
 }
 return total
}

函数sum2对一个切片中的元素间隔一个进行求和，实现如下。

func sum2(s []int64) int64 {
 var total int64
 for i := 0; i < len(s); i += 2 {
  total += s[i]
 }
 return total
}

假设链表元素是连续分配的，在64位体系结构中，字长为64位。下图描述了上述两个函数接收的数据在内存中的布局,图中黑色格子表示求和中使用元素的位置, 可以看到，链表和切片结构在内存中的结构是一样的。结构体node中，value占8个字节，指针next也占8个字节，所以每次求和元素间隔一个指针空间。为了排除干扰，sum2在求和时也间隔一个元素。

它们执行时间是不是一样呢？答案不是，第二函数比第一个快的多（大约块70%），为啥呢？弄懂原因前，先讨论跨步（stride）的概念。跨步涉及到 CPU 如何通过数据工作,根据步幅分为三种类型:

• 单步长(unit stride):所有要访问的元素内容都是连续分配的，例如，一个元素为int64类型的切片，对CPU来说，这种步进是可以预测的，并且是最高效的，因为它需要最少数量的缓存行就能遍历完所有元素。
• 常数步长(constant stride):对CPU来说，步长是可以预测的，例如在遍历切片的时候，间隔两个元素访问，这种需要较多的缓存行才能遍历完所有元素，没有单步长高效。
• 步长不定(non-unit stride):CPU难以预测，例如，像访问链表中的元素，CPU无法知道元素是否连续分配，所以它不会获取任何缓存行。

sum2函数是常数步长，但是对于链表结构，就是不固定步长，尽管我们知道linkedList中是连续分配的，但是CPU并不知道，难以预测如何执行。遍历链表比切片慢得多。通常应该编写支持单步长的程序，因为它有更好的空间局部性，不固定步幅无论数据如何分配，对CPU来说是不可预测的，从而导致比较差的性能。

缓存替换策略

在Go语言中常见100问题-#89 Writing inaccurate benchmarks中举了一个对矩阵中前八列元素求和的例子，当时没有分析为啥传入513列的矩阵比512列矩阵在性能上存在很大差异原因。这看起来非常违反直觉：为啥计算的都是前8列，并且矩阵的行数也一样，只是矩阵总列数不一样，改变总列数会影响执行时间。现在来分析具体的原因。

func calculateSum512(s [][512]int64) int64 {
    var sum int64
    for i := 0; i < len(s); i++ {
        for j := 0; j < 8; j++ {
            sum += s[i][j]
        }
    }
    return sum
}
 
func calculateSum513(s [][513]int64) int64 {
    // Same implementation as calculateSum512
}

进行基准测试时，如果每次都使用一个新矩阵，calculateSum512和calculateSum513没有啥差异，但是，如果使用相同的矩阵，calculateSum513大约块50%。详细实验结果见Go语言中常见100问题-#89 Writing inaccurate benchmarks最后一小节。

造成上述差异的原因是CPU缓存以及如何将内存块复制到缓存行。下面开始详细分析：

当CPU决定复制一个内存块并将其放入缓存时，必须遵守特定的策略。假设L1D缓存为32KB, 缓存行大小为64字节，如果将一个块随机放入L1D，CPU在最坏情况下不得不迭代512个缓存行来读取一个变量。这种缓存叫做全相联（fully associative）.

为了提高从CPU缓存中访问地址的速度，设计人员在缓存放置方面制定了不同的策略.下面讨论当前使用最广泛的组相联缓存策略，该策略依赖于缓存分区。

• 方便画图，简化L1D的大小为512字节（8个缓存行大小）
• 待计算的矩阵由4行32列组成，只读取前8列进行求和

下图显示了这个矩阵如何存储在内存中，使用二进制表示内存块地址。图中灰色块代表我们想要迭代的前8个int64元素首地址，剩余的块在迭代过程中会跳过。

每个存储块大小为64个字节，因此可以容纳8个int64元素。第一个内存块从0x000000000000开始，第二个从0001000000000(512个bit)开始，依此类推。缓存cache大小为8个缓存行。

使用组相联缓存策略，缓存被划分为多个组（set), 假设缓存是双向关联的（2-way)。这意味着每个组包含两个缓存行。一个内存块只能属于一个组，为了方便索引存储器地址，将内存块地址分成三个部分：

• 块偏移是基于块大小的，这里块的大小是512字节，512等于2^9。因此，地址的低9位代表块偏移(BO)
• 分组索引表示一个地址所属的集合。因为高速缓存是双向关联的，并且包含8行，所以有 8/2 = 4个组。4等于2^2，因此接下来的两位表示分组索引(SI)
• 地址的其余部分由标签位(TB)组成。下图中，为了简单起见，用13位来表示一个地址。TB位数等于 13 - BO - SI，意味着剩余的两位代表标签位

假设函数启动并试图读取地址000000000000的s[0][0]，由于这个地址还不在缓存cache中，CPU计算该地址的所属分组索引并将其复制到相应的缓存集合中，如下图所示。

内存地址000000000000被复制到分组0中。紧挨着bo的两位是si，即分组索引位，内容为00，所以该存储块被复制到set0中。当函数从s[0][1]读取到s[0][7]时，数据已经在缓存cache中。CPU是怎么知道缓存中已有数据的？CPU根据存储块的地址，取出其分组索引位和标记tag位，然后定位到分组，再在分组内比较tag值即可判断。

接下来函数读取s[0][8],此地址缓存中没有，同上原理复制内存块0100000000000，如下图所示,010000000000 被复制到分组0中，因为该地址分组索引也是00，所以它也属于set0。此时读取s[1][1]到s[1][7]时，会缓存命中。

同理，当读取s[2][0]时，由于该地址不在缓存cache中，也要进行复制操作。地址1000000000000的分组索引也是00，但是此时set0已满，如何处理呢？将它复制到其他分组？不是的，CPU会替换现有的缓存之一，具体的替换策略依赖于CPU, 它通常是一个伪LRU策略（真正的 LRU（最久未使用）会太复杂而难以处理）。如下图所示，将地址000000000000踢掉，然后1000000000000填充到该位置。

当读取s[3][0]时，由于其地址1100000000000所属的分组也是set0，也会替换现有的缓存行。

现在，假设进行基准测试时，执行函数使用到的切片从地址0000000000000开始。当函数读取s[0][0]时，该地址不在缓存中，要进行缓存替换。切换到下一次迭代时，不能使用缓存导致更多的缓存未命中，这种类型的缓存未命中称为冲突未命中，如果缓存没有分组就不会发生，我们迭代的所有变量都属于分组set0，只能使用一个缓存集合，而不是分布在整个缓存中。

前面讨论了步长的概念，步长约定CPU遍历访问数据的方式，本小节中遍历时的步长恰好又是关键步长：导致访问具有相同分组索引的内存地址，因此存储到相同的内存缓存分组中。

回到开头的例子，对 calculateSum512 和 calculateSum513 进行基准测试，是在一个32KB的8路（8-way)组关联的L1D缓存上执行的，一共有64个分组（set), cacheline是64字节，所以关键步距等于 64*64B = 4KB, 512个int64类型元素占用的空间恰好是4KB, 因此使用512列的矩阵刚好达到一个临界步长，所以缓存分布非常差。而513列的矩阵不会触发临界步长，这就是我们观察到两个基准测试表现很大差异原因。

总之，我们必须意识到缓存是分组的。根据步距的不同，在某些情况下只使用一组，这可能会影响应用性能并导致冲突未命中。这种跨长叫做关键跨步。对于性能密集型应用，应该避免关键跨步，以充分利用CPU缓存。