利用CPU cache特性优化Go程序

demo

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...

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大小。

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

false sharing

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

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

1
2
3
4
5
6
7
# 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相关的代码如下:

1
2
3
4
5
6
7
8
9
// 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标准库中的例子,来自内存管理模块,代码如下:

1
2
3
4
5
6
7
8
9
10
// 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标准库中的例子,数组中的元素timersBucketmcentral的第一个数据成员都是mutex类型的变量,而mutex作为互斥锁,其内部实现就需要频繁读写自身状态。

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

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

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

参考资料:

原文链接: https://pengrl.com/p/9125/
原文出处: yoko blog (https://pengrl.com)
原文作者: yoko (https://github.com/q191201771)
版权声明: 本文欢迎任何形式转载,转载时完整保留本声明信息(包含原文链接、原文出处、原文作者、版权声明)即可。本文后续所有修改都会第一时间在原始地址更新。

fccxy

0%