CPU伪共享的浅析

前言

在java开发的过程中有遇到过一个高性能内存队列 -- Disruptor, 被其巧妙的环形数组基础数据所吸引，同时也了解到cpu的伪共享带来的性能瓶颈。后来通过各种搜索引擎，浅显的了解了一下什么是CPU的伪共享，在这里稍作记录

Disruptor是英国外汇交易公司LMAX开发的一个高性能队列，
研发的初衷是解决内存队列的延迟问题（在性能测试中发现竟然与I/O操作处于同样的数量级）。
基于Disruptor开发的系统单线程能支撑每秒600万订单，2010年在QCon演讲后，获得了业界关注。
2011年，企业应用软件专家Martin Fowler专门撰写长文介绍。同年它还获得了Oracle官方的Duke大奖。

CPU的缓存

想要了解伪共享，首先得知道CPU的缓存是如何工作的
1.CPU执行指令的速度是非常快，但是在获取内存数据时会有较长的时延（毕竟我们都知道cpu运行速度是远高于内存的），这对于执行指令来说是完全不能接受的，所以就出现了CPU缓存这个东西，CPU缓存是直接集成在CPU中，离CPU最近，所以CPU在获取数据的时候不会直接去内存中获取，而是先从CPU缓存中获取，不需要通地址总线（就是主板上的一个通道）去内存中去获取，从而提升了程序执行效率，采取了就近的原则。这里的根本原因就是CPU运算速度与内存读写速度不匹配导致，这也和我们中的Redis类似，读取数据库非常慢，但是读Redis非常快，所以获取数据先从Redis中获取，如果没有再去数据库中读，以加快程序响应速度。编程思想:觉得程序执行慢，加缓存业务就完事了

2.缓存的加载：假设程序中读取某一个int变量，CPU并不是只从主存中读取4个字节，而是会一次性读取64个字节，然后放到cpu cache中。因为往往紧挨着的数据，更有可能在接下来会被使用到。比如遍历一个数组，因为数组空间是连续的，所以并不是每次取数组中的元素都要从主存中去拿，第一次从主存把数据放到cache line中，后续访问的数据很有可能已经在cache中了

cacheline的验证：
构建一个二维数组通过顺序遍历和间隔遍历来验证

顺序遍历：A1->A2->A3->...->B1->B2->B3->...
顺序遍历：A1->B1->C1->...->A2->B2->C2->...

我们都知道数组是连续内存地址，如果cacheline存在，那么顺序遍历可以就可以充分利用到cpu缓存，而间隔遍历则无法使用cpu缓存

最近一直在学习golang，就用go代码来验证了

func CacheLine() {

    //申明一个二维数组
    //内层为16个int大小，刚好64byte为一个cache line
    var array [1000000][16]int

    var sum int

    //构建一个二维数组
    for i := 0; i < 1000000; i++ {
        for j := 0; j < 16; j++ {
            array[i][j] = 8
        }
    }

    //顺序遍历 with cacheLine
    start1 := time.Now()
    for i := 0; i < 1000000; i++ {
        for j := 0; j < 16; j++ {
            sum = array[i][j]
        }
    }
    elapsed1 := time.Since(start1)
    fmt.Println("顺序遍历 with cacheLine：", elapsed1)

    //间隔遍历 without cacheLine
    start2 := time.Now()
    for j := 0; j < 16; j++ {
        for i := 0; i < 1000000; i++ {
            sum = array[i][j]
        }
    }
    elapsed2 := time.Since(start2)
    fmt.Println("间隔遍历 without cacheLine：", elapsed2)

    fmt.Println(sum)

}

我机器上的结果：

顺序遍历 with cacheLine： 17.906923ms
间隔遍历 without cacheLine： 126.782966ms

很明显，顺序遍历快了一个数量级，证明cacheline确实存在

缓存一致性

有缓存就会涉及到缓存的一致性
CPU这里是使用到MSEI缓存一致性协议来保证的，这个协议也是造成伪共享的关键
想详细了解协议的请戳这里
这里大家可以只用知道协议里有4中状态，状态之间会互相转换，并有如下特点：

伪共享

MSEI怎么导致伪共享, 数据X、Y、Z被加载到同一Cache Line中，线程A在Core1修改X，线程B在Core2上修改Y。根据MESI大法，假设是Core1是第一个发起操作的CPU核，Core1上的L1 Cache Line由S（共享）状态变成M（修改，脏数据）状态，然后告知其他的CPU核，图例则是Core2，引用同一地址的Cache Line已经无效了；当Core2发起写操作时，首先导致Core1将X写回主存，Cache Line状态由M变为I（无效），而后才是Core2从主存重新读取该地址内容，Cache Line状态由I变成E（独占），最后进行修改Y操作， Cache Line从E变成M。可见多个线程操作在同一Cache Line上的不同数据，相互竞争同一Cache Line，导致线程彼此牵制影响，变成了串行程序，降低了并发性。

此时我们则需要将共享在多线程间的数据进行隔离，使他们不在同一个Cache Line上，从而提升多线程的性能

继续用go来验证

func main(){
    FalseShare()
}

const iteration = 1000000

func FalseShare() {
    var array1 [8]ValuePadding

    var array2 [8]ValueNoPadding

    var wg sync.WaitGroup

    start1 := time.Now()
    //8个协程竞争
    for i := 0; i < 8; i++ {
        wg.Add(1)
        array1[i] = ValuePadding{}
        go work1(&wg, &array1, i)
    }

    wg.Wait()

    elapsed1 := time.Since(start1)
    fmt.Println("value padding ：", elapsed1)

    start2 := time.Now()
    for i := 0; i < 8; i++ {
        wg.Add(1)
        array2[i] = ValueNoPadding{}
        go work2(&wg, &array2, i)
    }

    wg.Wait()

    elapsed2 := time.Since(start2)
    fmt.Println("value no padding ：", elapsed2)

}

func work1(wg *sync.WaitGroup, array *[8]ValuePadding, index int) {
    defer wg.Done()
    i := 0
    for {
        i++
        array[index].value = 90
        if i > iteration {
            break
        }
    }
}

func work2(wg *sync.WaitGroup, array *[8]ValueNoPadding, index int) {
    defer wg.Done()
    i := 0
    for {
        i++
        array[index].value = 90
        if i > iteration {
            break
        }
    }
}

type ValuePadding struct {
    P1, P2, P3, P4, P5, P6, P7      int64
    value                           int64
    P8, P9, P10, P11, P12, P13, P14 int64
}

type ValueNoPadding struct {
    value int64
}

ValuePadding的数组中的每个元素被确保在单独的cacheline中，ValueNoPadding的数组元素极有可能存在于同一个cacheline中，同样用8个协程来竞争访问，后者会出现伪共享！

运行结果也证明了这一点:

value padding ： 5.326418ms
value no padding ： 26.600039ms

到此完结！