cpu cache 相关

[loadlj]

关于CPU cache

简要

一般来说x86 结构cpu cache line 的大小是64 byte, arm cacheline 是32 byte。 CPU 的 Cache 从上至下可以分为 L1(L1d 数据缓存, L1i指令缓存), L2, L3(多个 core 共享一个) 三层cache. 每层的访问速度由上至下依次递减, 可以使用lscpu命令查看.

L1d cache:             32K          
L1i cache:             32K
L2 cache:              1024K
L3 cache:              39424K

CPU从Cache数据的最小单位是字节，Cache从Memory拿数据的最小单位是64Bytes，Memory从硬盘拿数据通常最小是4092Bytes。

CPU Cache 的 prefetch

CPU每次从地址空间拿地址的时候不是按照一个一个地址去拿的，而是有一个 prefetch 的操作，每次会拿一个 cache line(大部分 CPU 的 cache line 是 64 byte)的数据加载。 下面可以测试一下 prefetch 命中和没命中的情况:

本机测试环境 MBP

CPU: Intel(R) Core(TM) i7-8850H CPU @ 2.60GHz
内存: 16 GB 2400 MHz DDR4

代码测试

func main() {
        a := make([][]int, 1024)
        r := 0
        for i := 0; i < 1024; i++ {
                a[i] = make([]int, 1024)
        }
        fmt.Printf("address of a[0][0] %p a[0][1] %p a[1][0] %p a[0][1023] %p \n", &a[0][0], &a[0][1], &a[1][0], &a[0][1023])
        for i := 0; i < 1023; i++ {
                for j := 0; j < 1023; j++ {
                        r += a[i][j]
                        //r += a[j][i]
                }
        }
        fmt.Println(r)
}

a[i][j] 赋值的时间

➜  time go run slice.go
 go run slice.go  0.34s user 0.29s system 54% cpu 1.166 total

a[j][i] 赋值的时间

go run slice.go  0.29s user 0.23s system 51% cpu 0.998 total

从上面的测试可以看到 a[i][j] 的花费时间为0.29s, 但是a[j][i]的花费时间为 0.34s. 因为我们在声明二维数组的时候可以发现其在内存里面连续分配的，代码输出地址a[0][0] 与 a[0][1] 相差一个int。但是a[0][0]与 a[1][0] 相差 1024 个int。 当我们从j开始从小到大依次便利的时候，CPU会一直从 cache line 里面去拿数据，如果是从i 开始的时候每次的cache line都会reload。从下面打印的数组地址也可以看出来:

address of a[0][0] 0xc000114000 a[0][1] 0xc000114008 a[1][0] 0xc000116000 a[0][1023] 0xc000115ff8

CPU Cache 的 false sharing

True sharing: 多核竞争的，是同一份将要访问的数据，比如全局变量的修改。

False sharing: 当一组相邻变量被多个核共享的时候(与true sharing不同的是访问的不是同一变量)，其中一个core 改变了里面的值就会导致另外一个 core 里面的cache line reload，造成cache miss。

贴一下相关的代码以及本机的测试

type MyAtomic interface {
    IncreaseAllEles()
    GetEles() uint64
}

type NoPad struct {
    a uint64
    b uint64
    c uint64
}

func (myatomic *NoPad) IncreaseAllEles() {
    atomic.AddUint64(&myatomic.a, 1)
    atomic.AddUint64(&myatomic.b, 1)
    atomic.AddUint64(&myatomic.c, 1)
}

func (myatomic *NoPad) GetEles() uint64 {
    return myatomic.a + myatomic.b + myatomic.c
}

type Pad struct {
    a   uint64
    _p1 [8]uint64
    b   uint64
    _p2 [8]uint64
    c   uint64
    _p3 [8]uint64
}

func (myatomic *Pad) IncreaseAllEles() {
    atomic.AddUint64(&myatomic.a, 1)
    atomic.AddUint64(&myatomic.b, 1)
    atomic.AddUint64(&myatomic.c, 1)
}

func (myatomic *Pad) GetEles() uint64 {
    return myatomic.a + myatomic.b + myatomic.c
}

func testParallelAtomicIncrease(myatomic MyAtomic) {
    paraNum := 1000
    addTimes := 1000
    var wg sync.WaitGroup
    wg.Add(paraNum)
    for i := 0; i < paraNum; i++ {
        go func() {
            for j := 0; j < addTimes; j++ {
                myatomic.IncreaseAllEles()
            }
            wg.Done()
        }()
    }
    wg.Wait()

}

测试结果

➜  test go test -bench=.
goos: darwin
goarch: amd64
BenchmarkNoPad-12             20      61637165 ns/op
BenchmarkPad-12               50      27061445 ns/op
PASS

解决false sharing的办法就是加padding，增加一些无意义的变量(64byte), 让原本相邻的变量不相邻，这样prefetch的时候就不会更改相应的 cache line , 产生cache reload 的现象。具体可以参考篇文章

TLB的影响

TLB是Translation Lookaside Buffer的简称, 为了避免CPU每次取页表的时候都访问MMU，所以引入了TLB这一层的cache。

所以在写程序的时候需要注意TLB的reload，Page的大小一般为4KB, 假设TLB的最大limit数是x, 当程序的内存使用超过 4xKb之后就会开始影响性能

由于手头上只有MAC，GCP上的虚拟机对perf的支持不是太友好，所以这边只贴一下perf的相关命令, 具体的测试结果可以参看下面的文章

perf stat -e dTLB-load,dTLB-load-misses,LLC-load,LLC-load-misses,LLC-prefetches,LLC-prefetch-misses,L1-dcache-loads,L1-dcache-misses,cycles:u,instructions:u -p PROCID sleep 10

相关测试可以参考

小结

在写代码的时候，同时注意到上面的东西很困难，但是我们也需要知道在代码里面发生了什么。 一般从cpu cache line reload -> cpu cache miss -> TLB miss -> page fault -> disk cache miss，这里面的每一层的miss其实都会带来损耗。所以实际上在写业务代码的时候需要根据各个方面去做trade-off.

[hyndaniel]

老哥写的好