阅读 454

golang和cache一致性

之前关于golang调度以及垃圾回收相关文章中,都有提到cache一致性的问题。今天来简单说一下cache相关内容,以及在golang中需要注意的事情。

cache结构

图中是一个存储结构示意图,cpu和主存直接使用的是L3的结构。金字塔越上面,相互之间的访问速度越快但是数据量越小,越往下访问速度越慢但数据量越大。

在单核CPU结构中,为了缓解CPU指令流水中cycle冲突,L1分成了指令(L1P)和数据(L1D)两部分,而L2则是指令和数据共存。多核CPU增设了L3三级缓存,L1和L2是CPU核自己使用,但是L3缓存是多核共享的。

cache局部性原理

局部性分为时间局部性空间局部性,时间局部性是说,当前访问到的数据随后时间也可能会访问到。空间局部性是指,当前访问的的地址附近的地址,之后可能会被访问到。根据局部性原理,我们把容易访问到的数据缓存在cache中,这样可以提高数据访问速度和效率。

时间局部性

举两个例子(忽略代码意图)

//代码1
for (loop=0; loop<100; loop++) {
    for (i=0; i<N; i++) {
        count = count + x[i]
    }
}
//代码2
for (i=0; i<N; i++) {
    for (loop=0; loop<100; loop++) {
        count = count + x[i]
    }
}
复制代码

很明显,下面的代码具有更好的时间局部性,因为在代码2中内层的loop循环,x[i]被重复使用。

空间局部性

//代码1
for(j=0; j<500; j++){
	for(i=0; i<500; i++){
	    a[i][j]=i;
	}    
}
//代码2
for(i=0; i<500; i++){
    for(j=0; j<500; j++){
        a[i][j]=i;
    }    
}

复制代码

相比之下,代码2执行性能更高。代码1是按列遍历,每次都需要跳过N个数组元素去找下一个,代码2按行遍历,具有较好的空间局部性。

cache伪共享

处理器和主存使用缓存行(cache lines)进行数据交换。一个缓存行是一个64 byte的内存块,它在内存和缓存系统之间进行交换。每个内核会分配它自己需要的cache副本。

当多线程并行运行,正在访问相同数据,甚至是相邻的数据单元,他们会访问相同的缓存行。任何内核上运行的任何线程能够从相同的缓存行获取各自的拷贝。

如果给一个内核,他上面的线程修改它的cache行副本,然后会通过硬件MESI机制,同一cache行的所有其他副本都会被标记为无效。当一个线程尝试读写脏cache行,需要重新访问主存去获取新的cache行副本(大约要100~300个时钟周期)。

goroutines并发中的cache一致性问题

这里我写了一个很简单的例子,数字从1加到100000。测试了三个版本,分别是开100000个goroutines处理,开cpu数量的goroutines处理,以及单个线程去处理。

package main

import (
	"fmt"
	"runtime"
	"sync"
	"sync/atomic"
	"time"
)

func addConcurrent(bignum int) {
	var c int32
	atomic.StoreInt32(&c, 0)

	start := time.Now()

	for i := 0; i < bignum; i++ {
		go atomic.AddInt32(&c, 1)
	}
	for {
		if c == int32(bignum) {
			fmt.Println(time.Since(start))
			break
		}
	}
}

func addCPUNum(bignum int) {
	var c int32
	wg := &sync.WaitGroup{}
	core := runtime.NumCPU()
	start := time.Now()
	wg.Add(core)
	for i := 0; i < core; i++ {
		go func(wg *sync.WaitGroup) {
			for j := 0; j < bignum/core; j++ {
				atomic.AddInt32(&c, 1)
			}
			wg.Done()
		}(wg)

	}
	wg.Wait()
	fmt.Println(time.Since(start))
}

func addOneThread(bignum int) {
	var c int32
	start := time.Now()
	for i := 0; i < bignum; i++ {
		atomic.AddInt32(&c, 1)
	}
	fmt.Println(time.Since(start))
}

func main() {

	bigNum := 100000
	addConcurrent(bigNum)
	addCPUNum(bigNum)
	addOneThread(bigNum)

}
复制代码

直接运行代码,按顺序得到如下输出

26.995877ms
1.789892ms
508.077µs
复制代码

100000 goroutines花费26ms、cpu num数量goroutines花费1.78ms,单线程只用了508us。 简单来分析一下,显然100000个goroutines处理这种cpu-bound的工作很不利,我之前go调度文章里讲过,线程上下文切换有延迟代价。io-bound处理可以在io wait的时候去切换别的线程做其他事情,但是对于cpu-bound,它会一直处理work,线程切换会损害性能。

这里还有另外一个重要因素,那就是cache伪共享(false sharing)。每个core都会去共享变量c的相同cache行,频繁操作c会导致内存抖动(cache和主存直接的换页操作)。

可以看到cpu number个线程并行处理时间是单线程处理时间的三倍,这个延迟代价还是很大的。

因此,在golang程序中需要避免因为cache伪共享导致的内存抖动,尽量避免多个线程去频繁操作一个相同变量或者是地址相邻变量。

参考资料

zhuanlan.zhihu.com/p/30127242 blog.csdn.net/yhb10478183…