利用CPU cache特性优化Go程序

demo

如下Go语言伪代码，开启两个协程，分别对一个结构体变量中的两个相邻的数据成员进行n次原子自增操作，当打开_ [56]byte这个看似多余的代码后，程序运行速度加快了一倍！你知道是为什么吗？

...

type Foo struct {
    a uint64
    // _ [56]byte
    b uint64
    // _ [56]byte
}

...
go func() {
    for i := 0; i < 1000 * 1000; i++ {
        atomic.AddUint64(&foo.a, 1)
    }
}()

go func() {
    for i := 0; i < 1000 * 1000; i++ {
        atomic.AddUint64(&foo.b, 1)
    }
}()

// 等待两个协程执行完毕，记录总执行时间
...

完整可运行代码见： https://github.com/q191201771/naza/blob/master/playground/p3/p3.go

CPU cache

大家都知道，内存的速度远快于磁盘的速度，但事实上，跟CPU的处理速度相比，内存还是太慢了。CPU不愿意老是等内存，于是就有了CPU cache。CPU cache的速度比内存快数十倍。

很多资料上都有关于不同存储硬件速度和容量的对比，但是有的数据随着硬件的发展已经过期了，想对此有个大致了解的可以看看《Latency Numbers Every Programmer Should Know》，这个网页的数据是按年更新，且历史数据都能看到。

CPU cache位于CPU和内存之间，CPU读取数据时，并不是直接从内存读取，而是先从CPU cache中读，读不到再从内存读。

显然，CPU cache命中率越高，程序执行速度就越快。但是受限于制造工艺以及成本，CPU cache的容量远小于内存。所以必须要有一种缓存策略，用于决定哪些数据缓存在CPU cache中。

CPU cache的缓存策略是基于局部性原理设计的。局部性分两点：时间局部性，即最近刚被访问的数据大概率会被再次访问；空间局部性，即最近刚被访问的数据，相邻的数据大概率会被访问。

CPU cache line

根据以上原理，CPU cache在缓存数据时，并不是以单个字节为单位缓存的，而是以CPU cache line大小为单位缓存，CPU cache line在一般的x86环境下为64字节。也就是说，即使从内存读取1个字节的数据，也会将邻近的64个字节一并缓存至CPU cache中。

linux下，可以通过getconf -a | grep CACHE命令获取cache line大小。

这也是访问数组通常比链表快的原因之一。

但是在多核多线程环境下，cache line的优化方式会带来一个问题。

这里需要先对CPU cache的知识做些扩充。事实上，CPU cache也是分多级的，常见的有三级，分别是L1，L2，L3，这三级缓存也遵循存储器的金字塔原理，即从L1到L3，速度递减，容量递增。一般来说，L1和L2是每个CPU核都有的，L3则是所有CPU核共有。

# macos 可以通过如下命令得到各级缓存大小：  
$sysctl -a | grep cachesize
# 输出如下：
hw.l1icachesize: 32768  #表示L1指令cache为32KB
hw.l1dcachesize: 32768  #表示L1数据cache为32KB
hw.l2cachesize: 262144  #表示L2 cache为256KB
hw.l3cachesize: 3145728 #表示L3 cache为3MB

由于一个CPU核在读取一个变量时，以cache line的方式将后续的变量也读取进来，缓存在自己这个核的cache中，而后续的变量也可能被其他CPU核并行缓存。当前面的CPU对前面的变量进行写入时，该变量同样是以cache line为单位写回内存。此时，在其他核上，尽管缓存的是该变量之后的变量，但是由于没法区分自身变量是否被修改，所以它只能认为自己的缓存失效，重新从内存中读取。这种现象叫做false sharing。

cache line padding

在高性能系统编程场景下，一般解决false sharing的方法是，在变量间添加无意义的填充数据（cache line padding）。使得我们真正需要高频并发读写的不同变量，不出现在一个cache line中。

Go标准库

我们来看看Go标准库中使用cache line padding的两个例子。

第一个例子来自Go标准库中的Timer定时器。和cache line padding相关的代码如下：

// src/runtime/time.go

const timersLen = 64

var timers [timersLen]struct {
  timersBucket

  pad [cpu.CacheLinePadSize - unsafe.Sizeof(timersBucket{})%cpu.CacheLinePadSize]byte
}

timers这个数组变量是全局变量，数组大小固定为64。关于Timer的具体实现原理不在本文描述范围内，感兴趣的可以看看我之前写的文章《golang源码阅读之定时器以及避坑指南》。这里你只需要知道，Go中创建的Timer会被哈希到一个timersBucket上，数组中的timersBucket对象会被并行访问。

数组元素类型是一个匿名结构体，结构体包含了两个数据成员：真正与业务逻辑功能相关的timersBucket，这里是将timersBucket类型作为一个匿名数据成员嵌入到匿名结构体中，另一个数据成员是pad，做cache line padding优化用。

如果去掉cache line padding的优化，上面的匿名结构体数组等价于var timers [timersLen]timersBucket。

匿名结构体对timersBucket的封装，相当于在原本一个接一个的timersBucket数组元素之间，插入了pad。从而保证不同的timersBucket对象不会出现在同一个cache line中。

再来分析pad数据成员。

其中的cpu.CacheLinePadSize变量定义在src/internal/cpu下，它通过构建标签的方式在不同环境下定义了不同的值，比如在cpu_x86.go文件下被定义为64。
unsafe.Sizeof(timersBucket{})用于计算一个timersBucket变量的大小。
取余CacheLinePadSize是为了处理结构体大小超过64的情况，只取尾部不够64的部分。
最后再用64减去刚才的值，得到需要填充多大空间才能填满这个cache line，填充时使用[]byte类型。

再看一个Go标准库中的例子，来自内存管理模块，代码如下：

// src/runtime/mheap.go

type mheap struct {
  // ...
  central [numSpanClasses]struct {
    mcentral mcentral
    pad      [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
  }
  // ...
}

同样的，本文也不介绍内存管理的具体实现，我们只需要知道mheap类型只会定义一个全局变量，central数组大小固定，其中的mcentral会被并行访问。可以看到，几乎和上面定时器的例子如出一辙，原来的配方，熟悉的味道。

最后，说回本文开头的demo，由于我已经知道我的macos的cache line是64，而一个uint64占8个字节，所以直接使用[56]byte作为padding。

总结

cache line padding适用于多个相邻的变量频繁被并发读写的场景。事实上，刚才所举的两个Go标准库中的例子，数组中的元素timersBucket和mcentral的第一个数据成员都是mutex类型的变量，而mutex作为互斥锁，其内部实现就需要频繁读写自身状态。

但cache line padding也不是万能的，首先，内容无实际意义的padding增加了内存使用量开销。

更重要的是，在某些场景下增加padding，意味着你放弃了CPU cache提供给你的空间局部性相关的预读取的奖励。

本文为了简洁（其实是个人能力有限），省略了很多计算机系统方面的细节，比如内存对齐，数据写入缓存后何时写入内存，多个CPU核如何保证缓存一致性，MESI协议，CPU如何知道原本想访问的内存地址存放在cache的什么位置等。希望以后有机会再写些相关的文章。

参考资料：

本文完，作者yoko，尊重劳动人民成果，转载请注明原文出处： https://pengrl.com/p/9125/