例子
我们先看两个例子,操作对象是一个MATRIXSIZE*8的整型矩阵。 (具体Benchmark代码已经上传到GitHub上,有兴趣的可以拉下来自己测试一下)
一、遍历矩阵
分别以行优先和列优先来遍历: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19func TraversalMatrixSumsByRow() int {
sum := 0
for i:= 0; i< MATRIXSIZE; i++ {
for j := 0; j<8; j++ {
sum += matrixs[i][j]
}
}
return sum
}
func TraversalMatrixSumsByColumn() int {
sum := 0
for i:= 0; i< 8; i++ {
for j := 0; j<MATRIXSIZE; j++ {
sum += matrixs[j][i]
}
}
return sum
}
1 | BenchmarkTraversalSumByRow-12 22184 53765 ns/op |
可以看出行优先遍历比列优先遍历快了40%多。
二、计算矩阵中偶数的个数
为了加速计算过程,我们通过协程来分块遍历矩阵,将结果存在一个整形数组中,在所有协程完成之后,遍历res数组取和。两个函数的区别是,在协程的循环里,一个是每次直接操作res数组对应的元素;而另一个是操作一个临时变量,循环结束后赋值给res数组对应的元素: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
func TraversalMatrixEven() int64 {
var count int64 = 0
res := make([]int64, GOROUTINENUM)
c := make(chan int, GOROUTINENUM)
for g := 0; g<GOROUTINENUM; g++ {
g := g
go func() {
chunkSize := MATRIXSIZE / GOROUTINENUM
start := g * chunkSize
end := start + chunkSize
if end > MATRIXSIZE {
end = MATRIXSIZE
}
for i := start; i < end; i++ {
for j := 0; j < 8; j++ {
if matrixs[i][j] %2 == 0 {
res[g]++ // use res[g]
}
}
}
c <- g
}()
}
for i := 0; i< GOROUTINENUM; i++ {
g := <- c
count += res[g]
}
return count
}
func TraversalMatrixEvenUseLocal() int64 {
var count int64 = 0
res := make([]int64, GOROUTINENUM)
c := make(chan int, GOROUTINENUM)
for g := 0; g<GOROUTINENUM; g++ {
g := g
go func() {
chunkSize := MATRIXSIZE / GOROUTINENUM
start := g * chunkSize
end := start + chunkSize
var localCount int64 = 0
if end > MATRIXSIZE {
end = MATRIXSIZE
}
for i := start; i < end; i++ {
for j := 0; j < 8; j++ {
if matrixs[i][j] %2 == 0 {
localCount++ // use local variable
}
}
}
res[g] = localCount
c <- g
}()
}
for i := 0; i< GOROUTINENUM; i++ {
g := <- c
count += res[g]
}
return count
}1
2BenchmarkMatrixEven-12 26013 45509 ns/op
BenchmarkMatrixEvenByLocal-12 46527 25937 ns/op
下面我们来分析一下为什么几乎完全一样的代码,会产生上面两种差异呢?在分析差异之前,先介绍一些基础知识。
CPU cache
什么是CPU cache?
摘抄一段wiki的解释: A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory.
即CPU cache是用来节省CPU访问主存时的平均消耗的一种硬件缓存。事实上CPU cache有三种通用的类型: 1. Data cache (D-Cache): 存储内容为数据的cache 2. Instruction cache (I-Cache): 存储内容为指令的cache 3. Translation lookaside buffer (TLB): 存储VA到PA映射的cache,主要是用来加速地址翻译
这里我们主要讨论D-Cache和I-Cache。
CPU Cache hierarchy
通常CPU的cache是分多个等级:L1,L2和L3,其中L1 cache分为L1 D-cache和L1 I-Cache。其中L1和L2 cache是每个CPU核独享的,L3 cache是多核共享的。以MBP上的6-Core Intel Core i7为例,我们使用 sysctl -a | grep cache
可以看到,L1的D-cache和I-cache分别是32KB,L2 cache是256KB,L3 cache是12MB: 1
2
3
4
5hw.cachelinesize: 64
hw.l1icachesize: 32768
hw.l1dcachesize: 32768
hw.l2cachesize: 262144
hw.l3cachesize: 12582912
Cache line
接下来是我们今天的主角Cache line,从上面的系统参数我们可以看到有一行 hw.cachelinesize: 64
,代表的就是Cache line的大小是64B。Cache是由很多个Cache line组成的,每一个Cache line是许多个相邻的数据组成,通常CPU的Cache line size是64B。
在填充Cache的时候,是以Cache line为单位,比如读取主存中的一个元素,会同时把相邻位置的元素当成一个Cache line填充到Cache中,甚至会prefetch相邻的cache line到cache中(HardWare Prefetching),以提高之后的访问速度。
这就解释了第一个例子:为什么矩阵的行优先遍历会比列优先遍历快这么多?因为矩阵也就是二维数组,在内存中是行优先存储的,当我们通过行优先遍历的时候,由于访问第一个元素,整行cache line会被读到L1 cache中,访问之后一个元素时,都是从L1 cache中拿到的;而列优先遍历则和矩阵的存储方式冲突,造成cache的命中率很低,增加访问时间。
Cache coherence
Cache coherence: In computer architecture, cache coherence is the uniformity of shared resource data that ends up stored in multiple local caches.
即缓存一致性,比如Core 1的L1 cache和Core 2的L1 cache分别维护了一个内存块的副本,当一个副本发生更改时,必须反映到其它副本上。缓存一致性旨在管理和实现这种一致性。
举个例子
拿6-Core Intel Core i7为例,假如Core1和Core2都缓存了地址A处的内容副本,记住,这里副本都是以cache line为单位的。当Core1的线程对这个副本进行写操作,修改了A的内容,为了保证缓存一致性,此时Core2上的A的缓存副本会被硬件置为失效状态。当Core2的线程需要访问地址A的时候,假如Core1把这个更新写回到了L3或者主存中了,Core2线程会从L3和主存中再读到地址A的内容,并缓存一份副本再L1/L2中。这种多个Core(多个线程)对同一份地址内容的读写,可以通过锁或者原子操作来保证一致性,代价是多消耗一些时间。
false sharing
结合缓存一致性和cache line,引出了今天的另一个主角:false sharing。什么是false sharing呢?我们想象这样一个场景:Core1的线程在读写地址A,Core2的线程在读写地址A+1,这是两个独立的地址,因此不存在任何读写竞争,也就不需要任何的锁或者原子操作来保证缓存一致性
但是,我们知道cache是以cache line为单位的,每个cache line通常是64B,因此地址A和地址A+1处的内容很大几率会落在同一个cache line上。当Core1读A地址时,会缓存cache line到Core1的L1/L2 cache上;当Core2读A+1地址时,也会缓存同一个cache line到Core2的L1/L2 cache上。根据上一个例子,当Core1写地址A的时候,会导致Core2的L1/L2 cache中对应的cache line失效;当Core2读写地址A+1的时候,会发生cache miss,并同时写A+1会导致Core1 cache中的cache line失效。类推下去……假如有多个线程在交替的读写位于同一个cache line上的相邻的地址,会导致各自的cache line频繁失效,这就是False sharing.
这就解释了第二个例子:为什么使用local variable会比直接操作res数组快这么多?就是因为多个goroutine在访问res数组时,造成了false sharing,大大降低了res数组的访问速度。
怎么避免False sharing
我们可以先分析False sharing产生的条件: 1. 相互独立的值落在了同一个cache line上 2. 多线程访问 3. 非常频繁 4. 至少有一个writer(会改变cache line的内容)
我们只需要打破任意一个产生条件,就可以避免产生False sharing。
比如第二个例子,就是增加一个local variable,只在每次循环结束时访问res数组,就是避免了频繁的访问同一个cache line,即使每个goroutine循环结束后会访问一次res数组,由于次数较少,对性能几乎无影响。
再比如更通用的做法,很多情况下可能无法控制访问者的具体使用场景,我们可以通过避免相互独立的值落在同一个cache line来避免False sharing的产生。比如下面这个例子: 1
2
3
4
5type paddedRWMutex struct {
_ [8]uint64 // Pad by cache-line size to prevent false sharing.
mu sync.RWMutex
}
type DRWMutex []paddedRWMutex
总结
CPU cache是CPU提升访问速度非常重要的硬件资源,根据程序的局部性原理,绝大多数的访问都会发生在cache上,并且由于访问速度的差异,应该发生在cache。因此编写cache友好的程序对于提升运行速度有重要的作用。另一方面,在多线程的场景里,避免False sharing是另一个提升程序性能的重要手段,需要很好的理解CPU cache的工作原理来避免False sharing的产生。
What's more?
文章开头给出的例子里,MATRIXSIZE和GOROUTINENUM我都没有贴出来,感兴趣的可以自己试一下不同的值对于性能差异的影响,并思考一下为什么?
欢迎在评论区留言讨论~