利用CPU cache特性优化Go程序 | yoko blog
source link: https://pengrl.com/p/9125/?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
利用CPU cache特性优化Go程序
如下Go语言伪代码,开启两个协程,分别对一个结构体变量中的两个相邻的数据成员进行n次原子自增操作,当打开_ [56]byte
这个看似多余的代码后,程序运行速度加快了一倍!你知道是为什么吗?
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 | # macos 可以通过如下命令得到各级缓存大小: |
由于一个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 | // src/runtime/time.go |
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 | // src/runtime/mheap.go |
同样的,本文也不介绍内存管理的具体实现,我们只需要知道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/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK