demo
如下Go語言偽代碼，開啟兩個(gè)協(xié)程，分別對一個(gè)結(jié)構(gòu)體變量中的兩個(gè)相鄰的數(shù)據(jù)成員進(jìn)行n次原子自增操作斩个，當(dāng)打開_ [56]byte這個(gè)看似多余的代碼后，程序運(yùn)行速度加快了一倍驯杜！你知道是為什么嗎受啥？
...
type Foo struct {
a uint64
// _ [56]byte
b uint64
// _ [56]byte
}
...
go func() {
for i := 0; i < 1000 * 1000; i++ {
atomic.AddUint64(&foo.a, 1)
}
}()
go func() {
for i := 0; i < 1000 * 1000; i++ {
atomic.AddUint64(&foo.b, 1)
}
}()
// 等待兩個(gè)協(xié)程執(zhí)行完畢，記錄總執(zhí)行時(shí)間
...
完整可運(yùn)行代碼見： https://github.com/q191201771/naza/blob/master/playground/p3/p3.go
CPU cache
大家都知道鸽心，內(nèi)存的速度遠(yuǎn)快于磁盤的速度滚局，但事實(shí)上，跟CPU的處理速度相比顽频，內(nèi)存還是太慢了藤肢。CPU不愿意老是等內(nèi)存，于是就有了CPU cache糯景。CPU cache的速度比內(nèi)存快數(shù)十倍嘁圈。
很多資料上都有關(guān)于不同存儲硬件速度和容量的對比，但是有的數(shù)據(jù)隨著硬件的發(fā)展已經(jīng)過期了莺奸，想對此有個(gè)大致了解的可以看看 《Latency Numbers Every Programmer Should Know》丑孩，這個(gè)網(wǎng)頁的數(shù)據(jù)是按年更新，且歷史數(shù)據(jù)都能看到灭贷。
CPU cache位于CPU和內(nèi)存之間，CPU讀取數(shù)據(jù)時(shí)略贮，并不是直接從內(nèi)存讀取甚疟，而是先從CPU cache中讀仗岖，讀不到再從內(nèi)存讀。
顯然览妖，CPU cache命中率越高轧拄，程序執(zhí)行速度就越快。但是受限于制造工藝以及成本讽膏，CPU cache的容量遠(yuǎn)小于內(nèi)存檩电。所以必須要有一種緩存策略，用于決定哪些數(shù)據(jù)緩存在CPU cache中府树。
CPU cache的緩存策略是基于局部性原理設(shè)計(jì)的俐末。局部性分兩點(diǎn)：時(shí)間局部性，即最近剛被訪問的數(shù)據(jù)大概率會被再次訪問奄侠；空間局部性卓箫，即最近剛被訪問的數(shù)據(jù)，相鄰的數(shù)據(jù)大概率會被訪問垄潮。
CPU cache line
根據(jù)以上原理烹卒，CPU cache在緩存數(shù)據(jù)時(shí)，并不是以單個(gè)字節(jié)為單位緩存的弯洗，而是以CPU cache line大小為單位緩存旅急，CPU cache line在一般的x86環(huán)境下為64字節(jié)。也就是說牡整，即使從內(nèi)存讀取1個(gè)字節(jié)的數(shù)據(jù)藐吮，也會將鄰近的64個(gè)字節(jié)一并緩存至CPU cache中。
linux下果正，可以通過
getconf -a | grep CACHE命令獲取cache line大小炎码。
這也是訪問數(shù)組通常比鏈表快的原因之一。
false sharing
但是在多核多線程環(huán)境下秋泳，cache line的優(yōu)化方式會帶來一個(gè)問題潦闲。
這里需要先對CPU cache的知識做些擴(kuò)充。事實(shí)上迫皱，CPU cache也是分多級的歉闰，常見的有三級，分別是L1卓起，L2和敬，L3，這三級緩存也遵循存儲器的金字塔原理戏阅，即從L1到L3昼弟，速度遞減，容量遞增奕筐。一般來說舱痘，L1和L2是每個(gè)CPU核都有的变骡，L3則是所有CPU核共有。
# macos 可以通過如下命令得到各級緩存大邪攀拧：
$sysctl -a | grep cachesize
# 輸出如下：
hw.l1icachesize: 32768 #表示L1指令cache為32KB
hw.l1dcachesize: 32768 #表示L1數(shù)據(jù)cache為32KB
hw.l2cachesize: 262144 #表示L2 cache為256KB
hw.l3cachesize: 3145728 #表示L3 cache為3MB
由于一個(gè)CPU核在讀取一個(gè)變量時(shí)塌碌，以cache line的方式將后續(xù)的變量也讀取進(jìn)來，緩存在自己這個(gè)核的cache中旬盯，而后續(xù)的變量也可能被其他CPU核并行緩存台妆。當(dāng)前面的CPU對前面的變量進(jìn)行寫入時(shí)，該變量同樣是以cache line為單位寫回內(nèi)存胖翰。此時(shí)接剩，在其他核上，盡管緩存的是該變量之后的變量泡态，但是由于沒法區(qū)分自身變量是否被修改搂漠，所以它只能認(rèn)為自己的緩存失效，重新從內(nèi)存中讀取某弦。這種現(xiàn)象叫做false sharing桐汤。
cache line padding
在高性能系統(tǒng)編程場景下，一般解決false sharing的方法是靶壮，在變量間添加無意義的填充數(shù)據(jù)（cache line padding）怔毛。使得我們真正需要高頻并發(fā)讀寫的不同變量，不出現(xiàn)在一個(gè)cache line中腾降。
Go標(biāo)準(zhǔn)庫
我們來看看Go標(biāo)準(zhǔn)庫中使用cache line padding的兩個(gè)例子拣度。
第一個(gè)例子來自Go標(biāo)準(zhǔn)庫中的Timer定時(shí)器。和cache line padding相關(guān)的代碼如下：
// src/runtime/time.go
const timersLen = 64
var timers [timersLen]struct {
timersBucket
pad [cpu.CacheLinePadSize - unsafe.Sizeof(timersBucket{})%cpu.CacheLinePadSize]byte
}
timers這個(gè)數(shù)組變量是全局變量螃壤，數(shù)組大小固定為64抗果。關(guān)于Timer的具體實(shí)現(xiàn)原理不在本文描述范圍內(nèi)，感興趣的可以看看我之前寫的文章 《golang源碼閱讀之定時(shí)器以及避坑指南》奸晴。這里你只需要知道冤馏，Go中創(chuàng)建的Timer會被哈希到一個(gè)timersBucket上，數(shù)組中的timersBucket對象會被并行訪問寄啼。
數(shù)組元素類型是一個(gè)匿名結(jié)構(gòu)體逮光，結(jié)構(gòu)體包含了兩個(gè)數(shù)據(jù)成員：真正與業(yè)務(wù)邏輯功能相關(guān)的timersBucket，這里是將timersBucket類型作為一個(gè)匿名數(shù)據(jù)成員嵌入到匿名結(jié)構(gòu)體中墩划，另一個(gè)數(shù)據(jù)成員是pad涕刚，做cache line padding優(yōu)化用。
如果去掉cache line padding的優(yōu)化乙帮，上面的匿名結(jié)構(gòu)體數(shù)組等價(jià)于var timers [timersLen]timersBucket杜漠。
匿名結(jié)構(gòu)體對timersBucket的封裝，相當(dāng)于在原本一個(gè)接一個(gè)的timersBucket數(shù)組元素之間，插入了pad碑幅。從而保證不同的timersBucket對象不會出現(xiàn)在同一個(gè)cache line中戴陡。
再來分析pad數(shù)據(jù)成員塞绿。
其中的cpu.CacheLinePadSize變量定義在src/internal/cpu下沟涨，它通過 構(gòu)建標(biāo)簽的方式 在不同環(huán)境下定義了不同的值，比如在cpu_x86.go文件下被定義為64异吻。
unsafe.Sizeof(timersBucket{})用于計(jì)算一個(gè)timersBucket變量的大小裹赴。
取余CacheLinePadSize是為了處理結(jié)構(gòu)體大小超過64的情況，只取尾部不夠64的部分诀浪。
最后再用64減去剛才的值棋返，得到需要填充多大空間才能填滿這個(gè)cache line，填充時(shí)使用[]byte類型雷猪。
再看一個(gè)Go標(biāo)準(zhǔn)庫中的例子睛竣，來自內(nèi)存管理模塊，代碼如下：
// src/runtime/mheap.go
type mheap struct {
// ...
central [numSpanClasses]struct {
mcentral mcentral
pad [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
}
// ...
}
同樣的求摇，本文也不介紹內(nèi)存管理的具體實(shí)現(xiàn)射沟，我們只需要知道mheap類型只會定義一個(gè)全局變量，central數(shù)組大小固定与境，其中的mcentral會被并行訪問验夯。可以看到摔刁，幾乎和上面定時(shí)器的例子如出一轍挥转，原來的配方，熟悉的味道共屈。
最后绑谣，說回本文開頭的demo，由于我已經(jīng)知道我的macos的cache line是64拗引，而一個(gè)uint64占8個(gè)字節(jié)借宵，所以直接使用[56]byte作為padding。
總結(jié)
cache line padding適用于多個(gè)相鄰的變量頻繁被并發(fā)讀寫的場景寺擂。事實(shí)上暇务，剛才所舉的兩個(gè)Go標(biāo)準(zhǔn)庫中的例子，數(shù)組中的元素timersBucket和mcentral的第一個(gè)數(shù)據(jù)成員都是mutex類型的變量怔软，而mutex作為互斥鎖垦细，其內(nèi)部實(shí)現(xiàn)就需要頻繁讀寫自身狀態(tài)。
但cache line padding也不是萬能的挡逼，首先括改，內(nèi)容無實(shí)際意義的padding增加了內(nèi)存使用量開銷。
更重要的是家坎，在某些場景下增加padding嘱能，意味著你放棄了CPU cache提供給你的空間局部性相關(guān)的預(yù)讀取的獎(jiǎng)勵(lì)吝梅。
本文為了簡潔（其實(shí)是個(gè)人能力有限），省略了很多計(jì)算機(jī)系統(tǒng)方面的細(xì)節(jié)惹骂，比如內(nèi)存對齊苏携，數(shù)據(jù)寫入緩存后何時(shí)寫入內(nèi)存，多個(gè)CPU核如何保證緩存一致性对粪，MESI協(xié)議右冻，CPU如何知道原本想訪問的內(nèi)存地址存放在cache的什么位置等。希望以后有機(jī)會再寫些相關(guān)的文章著拭。
參考資料：
原文鏈接： https://pengrl.com/p/9125/
原文出處： yoko blog (https://pengrl.com)
原文作者： yoko (https://github.com/q191201771)
版權(quán)聲明： 本文歡迎任何形式轉(zhuǎn)載纱扭，轉(zhuǎn)載時(shí)完整保留本聲明信息（包含原文鏈接、原文出處儡遮、原文作者乳蛾、版權(quán)聲明）即可。本文后續(xù)所有修改都會第一時(shí)間在原始地址更新鄙币。
本篇文章由一文多發(fā)平臺ArtiPub自動(dòng)發(fā)布
