CACHE基礎(chǔ)

對(duì)cache的掌握，對(duì)于Linux工程師（其他的非Linux工程師也一樣）寫(xiě)出高效能代碼，以及優(yōu)化Linux系統(tǒng)的性能是至關(guān)重要的。簡(jiǎn)單來(lái)說(shuō)，cache快，內(nèi)存慢，硬盤(pán)更慢。在一個(gè)典型的現(xiàn)代CPU中比較接近改進(jìn)的哈佛結(jié)構(gòu)，cache的排布大概是這樣的：

L1速度》 L2速度》 L3速度》 RAM

L1容量《 L2容量《 L3容量《 RAM

現(xiàn)代CPU，通常L1 cache的指令和數(shù)據(jù)是分離的。這樣可以實(shí)現(xiàn)2條高速公路并行訪問(wèn)，CPU可以同時(shí)load指令和數(shù)據(jù)。當(dāng)然，cache也不一定是一個(gè)core獨(dú)享，現(xiàn)代很多CPU的典型分布是這樣的，比如多個(gè)core共享一個(gè)L3。比如這臺(tái)的Linux里面運(yùn)行l(wèi)stopo命令：

人們也常常稱呼L2cache為MLC（MiddleLevel Cache），L3cache為L(zhǎng)LC（Last LevelCache）。這些Cache究竟有多塊呢？我們來(lái)看看Intel的數(shù)據(jù)，具體配置：Intel i7-4770 （Haswell）， 3.4 GHz （Turbo Boostoff）， 22 nm. RAM： 32 GB （PC3-12800 cl11 cr2）

訪問(wèn)延遲：

數(shù)據(jù)來(lái)源：https://www.7-cpu.com/cpu/Haswell.html

由此我們可以知道，我們應(yīng)該盡可能追求cache的命中率高，以避免延遲，最好是低級(jí)cache的命中率越高越好。

CACHE的組織

現(xiàn)代的cache基本按照這個(gè)模式來(lái)組織：SET、WAY、TAG、INDEX，這幾個(gè)概念是理解Cache的關(guān)鍵。隨便打開(kāi)一個(gè)數(shù)據(jù)手冊(cè)，就可以看到這樣的字眼：

翻譯成中文就是4路（way）組（set）相聯(lián)，VIPT表現(xiàn)為（behave as）PIPT --這尼瑪什么鬼？，cacheline的長(zhǎng)度是64字節(jié)。

下面我們來(lái)想象一個(gè)16KB大小的cache，假設(shè)是4路組相聯(lián)，cacheline的長(zhǎng)度是64字節(jié)。Cacheline的概念比較簡(jiǎn)單，cache的整個(gè)替換是以行為單位的，一行64個(gè)字節(jié)里面讀了任何一個(gè)字節(jié)，其實(shí)整個(gè)64字節(jié)就進(jìn)入了cache。

比如下面兩段程序，前者的計(jì)算量是后者的8倍：

但是它的執(zhí)行時(shí)間，則遠(yuǎn)遠(yuǎn)不到后者的8倍：

16KB的cache是4way的話，每個(gè)set包括4*64B，則整個(gè)cache分為16KB/64B/4 = 64set，也即2的6次方。當(dāng)CPU從cache里面讀數(shù)據(jù)的時(shí)候，它會(huì)用地址位的BIT6-BIT11來(lái)尋址set，BIT0-BIT5是cacheline內(nèi)的offset。

比如CPU訪問(wèn)地址

0 000000 XXXXXX

或者

1 000000 XXXXXX

或者

YYYY 000000 XXXXXX

由于它們紅色的6位都相同，所以他們?nèi)慷紩?huì)找到第0個(gè)set的cacheline。第0個(gè)set里面有4個(gè)way，之后硬件會(huì)用地址的高位如0，1，YYYY作為tag，去檢索這4個(gè)way的tag是否與地址的高位相同，而且cacheline是否有效，如果tag匹配且cacheline有效，則cache命中。

所以地址YYYYYY000000XXXXXX全部都是找第0個(gè)set，YYYYYY000001XXXXXX全部都是找第1個(gè)set，YYYYYY111111XXXXXX全部都是找第63個(gè)set。每個(gè)set中的4個(gè)way，都有可能命中。

中間紅色的位就是INDEX，前面YYYY這些位就是TAG。具體的實(shí)現(xiàn)可以是用虛擬地址或者物理地址的相應(yīng)位做TAG或者INDEX。如果用虛擬地址做TAG，我們叫VT；如果用物理地址做TAG，我們叫PT；如果用虛擬地址做INDEX，我們叫VI；如果用物理地址做TAG，我們叫PT。工程中碰到的cache可能有這么些組合：

VIVT、VIPT、PIPT。

VIVT的硬件實(shí)現(xiàn)開(kāi)銷(xiāo)最低，但是軟件維護(hù)成本高；PIPT的硬件實(shí)現(xiàn)開(kāi)銷(xiāo)最高，但是軟件維護(hù)成本最低；VIPT介于二者之間，但是有些硬件是VIPT，但是behave as PIPT，這樣對(duì)軟件而言，維護(hù)成本與PIPT一樣。

在VIVT的情況下，CPU發(fā)出的虛擬地址，不需要經(jīng)過(guò)MMU的轉(zhuǎn)化，直接就可以去查cache。

而在VIPT和PIPT的場(chǎng)景下，都涉及到虛擬地址轉(zhuǎn)換為物理地址后，再去比對(duì)cache的過(guò)程。VIPT如下：

PIPT如下：

從圖上看起來(lái)，VIVT的硬件實(shí)現(xiàn)效率很高，不需要經(jīng)過(guò)MMU就可以去查cache了。不過(guò)，對(duì)軟件來(lái)說(shuō)，這是個(gè)災(zāi)難。因?yàn)閂IVT有嚴(yán)重的歧義和別名問(wèn)題。

歧義：一個(gè)虛擬地址先后指向兩個(gè)（或者多個(gè)）物理地址

別名：兩個(gè)（或者多個(gè)）虛擬地址同時(shí)指向一個(gè)物理地址

這里我們重點(diǎn)看別名問(wèn)題。比如2個(gè)虛擬地址對(duì)應(yīng)同一個(gè)物理地址，基于VIVT的邏輯，無(wú)論是INDEX還是TAG，2個(gè)虛擬地址都是可能不一樣的（盡管他們的物理地址一樣，但是物理地址在cache比對(duì)中完全不摻和），這樣它們完全可能在2個(gè)cacheline同時(shí)命中。

由于2個(gè)虛擬地址指向1個(gè)物理地址，這樣CPU寫(xiě)過(guò)第一個(gè)虛擬地址后，寫(xiě)入cacheline1。CPU讀第2個(gè)虛擬地址，讀到的是過(guò)時(shí)的cacheline2，這樣就出現(xiàn)了不一致。所以，為了避免這種情況，軟件必須寫(xiě)完虛擬地址1后，對(duì)虛擬地址1對(duì)應(yīng)的cache執(zhí)行clean，對(duì)虛擬地址2對(duì)應(yīng)的cache執(zhí)行invalidate。

而PIPT完全沒(méi)有這樣的問(wèn)題，因?yàn)闊o(wú)論多少虛擬地址對(duì)應(yīng)一個(gè)物理地址，由于物理地址一樣，我們是基于物理地址去尋找和比對(duì)cache的，所以不可能出現(xiàn)這種別名問(wèn)題。

那么VIPT有沒(méi)有可能出現(xiàn)別名呢？答案是有可能，也有可能不能。如果VI恰好對(duì)于PI，就不可能，這個(gè)時(shí)候，VIPT對(duì)軟件而言就是PIPT了：

VI=PI

PT=PT

那么什么時(shí)候VI會(huì)等于PI呢？這個(gè)時(shí)候我們來(lái)回憶下虛擬地址往物理地址的轉(zhuǎn)換過(guò)程，它是以頁(yè)為單位的。假設(shè)一頁(yè)是4K，那么地址的低12位虛擬地址和物理地址是完全一樣的?；貞浳覀兦懊娴牡刂罚?/p>

YYYYY000000XXXXXX

其中紅色的000000是INDEX。在我們的例子中，紅色的6位和后面的XXXXXX（cache內(nèi)部偏移）加起來(lái)正好12位，所以這個(gè)000000經(jīng)過(guò)虛實(shí)轉(zhuǎn)換后，其實(shí)還是000000的，這個(gè)時(shí)候VI=PI，VIPT沒(méi)有別名問(wèn)題。

我們?cè)燃僭O(shè)的cache是：16KB大小的cache，假設(shè)是4路組相聯(lián)，cacheline的長(zhǎng)度是64字節(jié)，這樣我們正好需要紅色的6位來(lái)作為INDEX。但是如果我們把cache的大小增加為32KB，這樣我們需要 32KB/4/64B=128=2^7，也即7位來(lái)做INDEX。

YYYY0000000XXXXXX

這樣VI就可能不等于PI了，因?yàn)榧t色的最高位超過(guò)了2^12的范圍，完全可能出現(xiàn)如下2個(gè)虛擬地址，指向同一個(gè)物理地址：

這樣就出現(xiàn)了別名問(wèn)題，我們?cè)诠こ汤?，可能可以通過(guò)一些辦法避免這種別名問(wèn)題，比如軟件在建立虛實(shí)轉(zhuǎn)換的時(shí)候，把虛實(shí)轉(zhuǎn)換往2^13而不是2^12對(duì)齊，讓物理地址的低13位而不是低12位與物理地址相同。

這樣強(qiáng)行繞開(kāi)別名問(wèn)題，下圖中，2個(gè)虛擬地址指向了同一個(gè)物理地址，但是它們的INDEX是相同的，這樣VI=PI，就繞開(kāi)了別名問(wèn)題。這通常是PAGE COLOURING技術(shù)中的一種技巧。

如果這種PAGE COLOURING的限制對(duì)軟件仍然不可接受，而我們又想享受VIPT的INDEX不需要經(jīng)過(guò)MMU虛實(shí)轉(zhuǎn)換的快捷？有沒(méi)有什么硬件技術(shù)來(lái)解決VIPT別名問(wèn)題呢？確實(shí)是存在的，現(xiàn)代CPU很多都是把L1 CACHE做成VIPT，但是表現(xiàn)地（behave as）像PIPT。這是怎么做到的呢？

這要求VIPT的cache，硬件上具備alias detection的能力。比如，硬件知道YYYY0000000XXXXXX既有可能出現(xiàn)在第0000000，又可能出現(xiàn)在1000000這2個(gè)set，然后硬件自動(dòng)去比對(duì)這2個(gè)set里面是否出現(xiàn)映射到相同物理地址的cacheline，并從硬件上解決好別名同步，那么軟件就完全不用操心了。

下面我們記住一個(gè)簡(jiǎn)單的規(guī)則：

對(duì)于VIPT，如果cache的size除以WAY數(shù)，小于等于1個(gè)page的大小，則天然VI=PI，無(wú)別名問(wèn)題；

對(duì)于VIPT，如果cache的size除以WAY數(shù)，大于1個(gè)page的大小，則天然VI≠PI，有別名問(wèn)題；這個(gè)時(shí)候又分成2種情況：

硬件不具備alias detection能力，軟件需要pagecolouring；

硬件具備alias detection能力，軟件把cache當(dāng)成PIPT用。

比如cache大小64KB，4WAY，PAGE SIZE是4K，顯然有別名問(wèn)題；這個(gè)時(shí)候，如果cache改為16WAY，或者PAGE SIZE改為16K，不再有別名問(wèn)題。為什么？感覺(jué)小學(xué)數(shù)學(xué)知識(shí)也能算得清

CACHE的一致性

Cache的一致性有這么幾個(gè)層面

1. 一個(gè)CPU的icache和dcache的同步問(wèn)題

2. 多個(gè)CPU各自的cache同步問(wèn)題

3. CPU與設(shè)備（其實(shí)也可能是個(gè)異構(gòu)處理器，不過(guò)在Linux運(yùn)行的CPU眼里，都是設(shè)備，都是DMA）的cache同步問(wèn)題

先看一下ICACHE和DCACHE同步問(wèn)題。由于程序的運(yùn)行而言，指令流的都流過(guò)icache，而指令中涉及到的數(shù)據(jù)流經(jīng)過(guò)dcache。所以對(duì)于自修改的代碼（Self-Modifying Code）而言，比如我們修改了內(nèi)存p這個(gè)位置的代碼（典型多見(jiàn)于JIT compiler），這個(gè)時(shí)候我們是通過(guò)store的方式去寫(xiě)的p，所以新的指令會(huì)進(jìn)入dcache。但是我們接下來(lái)去執(zhí)行p位置的指令的時(shí)候，icache里面可能命中的是修改之前的指令。

所以這個(gè)時(shí)候軟件需要把dcache的東西clean出去，然后讓icache invalidate，這個(gè)開(kāi)銷(xiāo)顯然還是比較大的。

但是，比如ARM64的N1處理器，它支持硬件的icache同步，詳見(jiàn)文檔：The Arm Neoverse N1 Platform： Building Blocks for the Next-Gen Cloud-to-Edge Infrastructure SoC

特別注意畫(huà)紅色的幾行。軟件維護(hù)的成本實(shí)際很高，還涉及到icache的invalidation向所有核廣播的動(dòng)作。

接下來(lái)的一個(gè)問(wèn)題就是多個(gè)核之間的cache同步。下面是一個(gè)簡(jiǎn)化版的處理器，CPU_A和B共享了一個(gè)L3，CPU_C和CPU_D共享了一個(gè)L3。實(shí)際的硬件架構(gòu)由于涉及到NUMA，會(huì)比這個(gè)更加復(fù)雜，但是這個(gè)圖反映層級(jí)關(guān)系是足夠了。

比如CPU_A讀了一個(gè)地址p的變量？CPU_B、C、D又讀，難道B，C，D又必須從RAM里面經(jīng)過(guò)L3，L2，L1再讀一遍嗎？這個(gè)顯然是沒(méi)有必要的，在硬件上，cache的snooping控制單元，可以協(xié)助直接把CPU_A的p地址cache拷貝到CPU_B、C和D的cache。

這樣A-B-C-D都得到了相同的p地址的棕色小球。

假設(shè)CPU B這個(gè)時(shí)候，把棕色小球?qū)懗杉t色，而其他CPU里面還是棕色，這樣就會(huì)不一致了：

這個(gè)時(shí)候怎么辦？這里面顯然需要一個(gè)協(xié)議，典型的多核cache同步協(xié)議有MESI和MOESI。MOESI相對(duì)MESI有些細(xì)微的差異，不影響對(duì)全局的理解。下面我們重點(diǎn)看MESI協(xié)議。

MESI協(xié)議定義了4種狀態(tài)：

M（Modified）： 當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)已被修改而且與內(nèi)存中的數(shù)據(jù)不一致，數(shù)據(jù)只在當(dāng)前cache里存在；類(lèi)似RAM里面是棕色球，B里面是紅色球（CACHE與RAM不一致），A、C、D都沒(méi)有球。

E（Exclusive）：當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)與內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)只在當(dāng)前cache里存在；類(lèi)似RAM里面是棕色球，B里面是棕色球（RAM和CACHE一致），A、C、D都沒(méi)有球。

S（Shared）：當(dāng)前cache的內(nèi)容有效，數(shù)據(jù)與內(nèi)存中的數(shù)據(jù)一致，數(shù)據(jù)在多個(gè)cache里存在。類(lèi)似如下圖，在CPU A-B-C里面cache的棕色球都與RAM一致。

I（Invalid）： 當(dāng)前cache無(wú)效。前面三幅圖里面cache沒(méi)有球的那些都是屬于這個(gè)情況。

然后它有個(gè)狀態(tài)機(jī)

這個(gè)狀態(tài)機(jī)比較難記，死記硬背是記不住的，也沒(méi)必要記，它講的cache原先的狀態(tài)，經(jīng)過(guò)一個(gè)硬件在本cache或者其他cache的讀寫(xiě)操作后，各個(gè)cache的狀態(tài)會(huì)如何變遷。所以，硬件上不僅僅是監(jiān)控本CPU的cache讀寫(xiě)行為，還會(huì)監(jiān)控其他CPU的。只需要記住一點(diǎn)：這個(gè)狀態(tài)機(jī)是為了保證多核之間cache的一致性，比如一個(gè)干凈的數(shù)據(jù)，可以在多個(gè)CPU的cache share，這個(gè)沒(méi)有一致性問(wèn)題；但是，假設(shè)其中一個(gè)CPU寫(xiě)過(guò)了，比如A-B-C本來(lái)是這樣：

然后B被寫(xiě)過(guò)了：

這樣A、C的cache實(shí)際是過(guò)時(shí)的數(shù)據(jù)，這是不允許的。這個(gè)時(shí)候，硬件會(huì)自動(dòng)把A、C的cache invalidate掉，不需要軟件的干預(yù)，A、C其實(shí)變地相當(dāng)于不命中這個(gè)球了：

這個(gè)時(shí)候，你可能會(huì)繼續(xù)問(wèn)，如果C要讀這個(gè)球呢？它目前的狀態(tài)在B里面是modified的，而且與RAM不一致，這個(gè)時(shí)候，硬件會(huì)把紅球clean，然后B、C、RAM變地一致，B、C的狀態(tài)都變化為S（Shared）：

這一系列的動(dòng)作雖然由硬件完成，但是對(duì)軟件而言不是免費(fèi)的，因?yàn)樗馁M(fèi)了時(shí)間。如果編程的時(shí)候不注意，引起了硬件的大量cache同步行為，則程序的效率可能會(huì)急劇下降。

為了讓大家直觀感受到這個(gè)cache同步的開(kāi)銷(xiāo)，下面我們寫(xiě)一個(gè)程序，這個(gè)程序有2個(gè)線程，一個(gè)寫(xiě)變量，一個(gè)讀變量：

這個(gè)程序里，x和y都是cacheline對(duì)齊的，這個(gè)程序的thread1的寫(xiě)，會(huì)不停地與thread2的讀，進(jìn)行cache同步。

它的執(zhí)行時(shí)間為：

$ time 。/a.out real 0m3.614suser 0m7.021ssys 0m0.004s

它在2個(gè)CPU上的userspace共運(yùn)行了7.021秒，累計(jì)這個(gè)程序從開(kāi)始到結(jié)束的對(duì)應(yīng)真實(shí)世界的時(shí)間是3.614秒（就是從命令開(kāi)始到命令結(jié)束的時(shí)間）。

如果我們把程序改一句話，把thread2里面的c = x改為c = y，這樣2個(gè)線程在2個(gè)CPU運(yùn)行的時(shí)候，讀寫(xiě)的是不同的cacheline，就沒(méi)有這個(gè)硬件的cache同步開(kāi)銷(xiāo)了：

它的運(yùn)行時(shí)間：

$ time 。/b.out real 0m1.820suser 0m3.606ssys 0m0.008s

現(xiàn)在只需要1.8秒，幾乎減小了一半。

感覺(jué)前面那個(gè)a.out，雙核的幫助甚至都不大。如果我們改為單核跑呢？

$ time taskset -c 0 。/a.out real 0m3.299suser 0m3.297ssys 0m0.000s

它單核跑，居然只需要3.299秒跑完，而雙核跑，需要3.614s跑完。單核跑完這個(gè)程序，甚至比雙核還快，有沒(méi)有驚掉下巴？?。?！因?yàn)閱魏死锩鏇](méi)有cache同步的開(kāi)銷(xiāo)。

下一個(gè)cache同步的重大問(wèn)題，就是設(shè)備與CPU之間。如果設(shè)備感知不到CPU的cache的話（下圖中的紅色數(shù)據(jù)流向不經(jīng)過(guò)cache），這樣，做DMA前后，CPU就需要進(jìn)行相關(guān)的cacheclean和invalidate的動(dòng)作，軟件的開(kāi)銷(xiāo)會(huì)比較大。

這些軟件的動(dòng)作，若我們?cè)贚inux編程的時(shí)候，使用的是streaming DMA APIs的話，都會(huì)被類(lèi)似這樣的API自動(dòng)搞定：

dma_map_single（）dma_unmap_single（）dma_sync_single_for_cpu（）dma_sync_single_for_device（）dma_sync_sg_for_cpu（）dma_sync_sg_for_device（）

如果是使用的dma_alloc_coherent（） API呢，則設(shè)備和CPU之間的buffer是cache一致的，不需要每次DMA進(jìn)行同步。對(duì)于不支持硬件cache一致性的設(shè)備而言，很可能dma_alloc_coherent（）會(huì)把CPU對(duì)那段DMA buffer的訪問(wèn)設(shè)置為uncachable的。

這些API把底層的硬件差異封裝掉了，如果硬件不支持CPU和設(shè)備的cache同步的話，延時(shí)還是比較大的。那么，對(duì)于底層硬件而言，更好的實(shí)現(xiàn)方式，應(yīng)該仍然是硬件幫我們來(lái)搞定。比如我們需要修改總線協(xié)議，延伸紅線的觸角：

當(dāng)設(shè)備訪問(wèn)RAM的時(shí)候，可以去snoop CPU的cache：

如果做內(nèi)存到外設(shè)的DMA，則直接從CPU的cache取modified的數(shù)據(jù)；

如果做外設(shè)到內(nèi)存的DMA，則直接把CPU的cache invalidate掉。

這樣，就實(shí)現(xiàn)硬件意義上的cache同步。當(dāng)然，硬件的cache同步，還有一些其他方法，原理上是類(lèi)似的。注意，這種同步仍然不是免費(fèi)的，它仍然會(huì)消耗bus cycles的。實(shí)際上，cache的同步開(kāi)銷(xiāo)還與距離相關(guān)，可以說(shuō)距離越遠(yuǎn)，同步開(kāi)銷(xiāo)越大，比如下圖中A、B的同步開(kāi)銷(xiāo)比A、C小。

對(duì)于一個(gè)NUMA服務(wù)器而言，跨NUMA的cache同步開(kāi)銷(xiāo)顯然是要比NUMA內(nèi)的同步開(kāi)銷(xiāo)大。

意識(shí)到CACHE的編程

通過(guò)上一節(jié)的代碼，讀者應(yīng)該意識(shí)到了cache的問(wèn)題不處理好，程序的運(yùn)行性能會(huì)急劇下降。所以意識(shí)到cache的編程，對(duì)程序員是至關(guān)重要的。

從CPU流水線的角度講，任何的內(nèi)存訪問(wèn)延遲都可以簡(jiǎn)化為如下公式：

Average Access Latency = Hit Time + Miss Rate × Miss Penalty

cache miss會(huì)導(dǎo)致CPU的stall狀態(tài)，從而影響性能。現(xiàn)代CPU的微架構(gòu)分了frontend和backend。frontend負(fù)責(zé)fetch指令給backend執(zhí)行，backend執(zhí)行依賴運(yùn)算能力和Memory子系統(tǒng)（包括cache）延遲。

backend執(zhí)行中訪問(wèn)數(shù)據(jù)導(dǎo)致的cache miss會(huì)導(dǎo)致backend stall，從而降低IPC（instructions per cycle）。減小cache的miss，實(shí)際上是一個(gè)軟硬件協(xié)同設(shè)計(jì)的任務(wù)。比如硬件方面，它支持預(yù)取prefetch，通過(guò)分析cache miss的pattern，硬件可以提前預(yù)取數(shù)據(jù)，在流水線需要某個(gè)數(shù)據(jù)前，提前先取到cache，從而CPU流水線跑到需要它的時(shí)候，不再miss。當(dāng)然，硬件不一定有那么聰明，也許它可以學(xué)會(huì)一些簡(jiǎn)單的pattern。但是，對(duì)于復(fù)雜的無(wú)規(guī)律的數(shù)據(jù)，則可能需要軟件通過(guò)預(yù)取指令，來(lái)暗示CPU進(jìn)行預(yù)取。

cache預(yù)取

比如在ARM處理器上就有一條指令叫pld，prefetch可以用pld指令：

static inline void prefetch（const void *ptr）{ __asm__ __volatile__（ “pld %a0” ：： “p” （ptr））;}

眼見(jiàn)為實(shí)，我們隨便從Linux內(nèi)核里面找一個(gè)commit：

因?yàn)槲覀儚腤iFi收到了一個(gè)skb，我們很快就要訪問(wèn)這個(gè)skb里面的數(shù)據(jù)來(lái)進(jìn)行packet的分類(lèi)以及交給IP stack處理了，不如我們先prefetch一下，這樣后面等需要訪問(wèn)這個(gè)skb-》data的時(shí)候，流水線可以直接命中cache，從而不打斷。

預(yù)取的原理有點(diǎn)類(lèi)似今天星期五，咱們?cè)谏虾ffice，下周一需要北京分公司的人來(lái)上海office開(kāi)會(huì)。于是，我們通知北京office的人周末坐飛機(jī)過(guò)來(lái)，這樣周一開(kāi)會(huì)的時(shí)候就不必等他們了。不預(yù)取的情況下，會(huì)議開(kāi)始后，再等北京的人飛過(guò)來(lái)，會(huì)導(dǎo)致stall狀態(tài)。

任何東西最終還是要落實(shí)到代碼，talk is cheap，show me the code。下面這個(gè)是經(jīng)典的二分查找法代碼，這個(gè)代碼是網(wǎng)上抄的。

特別留意ifdef DO_PREFETCH包著的代碼，它提前預(yù)取了下次的中間值。我們來(lái)對(duì)比下，不預(yù)取和預(yù)取情況下，這個(gè)同樣的代碼執(zhí)行時(shí)間的差異。先把cpufreq的影響盡可能關(guān)閉掉，設(shè)置為performance：

barry@barry-HP-ProBook-450-G7：~$ sudo cpupower frequency-set --governor performanceSetting cpu： 0Setting cpu： 1Setting cpu： 2Setting cpu： 3Setting cpu： 4Setting cpu： 5Setting cpu： 6Setting cpu： 7

然后我們來(lái)對(duì)比差異：

開(kāi)啟prefetch執(zhí)行時(shí)間大約10s， 不prefetch的情況下，11.6s執(zhí)行完成，性能提升大約14%，所以周末坐飛機(jī)太重要了！

現(xiàn)在我們來(lái)通過(guò)基于perf的pmu-tools（下載地址：https://github.com/andikleen/pmu-tools），對(duì)上面的程序進(jìn)行topdown分析，分析的時(shí)候，為了盡可能減小其他因子的影響，我們把程序通過(guò)taskset運(yùn)行到CPU0。

先看不prefetch的情況，很明顯，程序是backend_bound的，其中DRAM_Bound占比大，達(dá)到75.8%。

開(kāi)啟prefetch的情況呢？程序依然是backend_bound的，其中，backend bound的主體依然是DRAM_Bound，但是比例縮小到了60.7%。

DRAM_Bound主要對(duì)應(yīng)cycle_activity.stalls_l3_miss事件，我們通過(guò)perf stat來(lái)分別進(jìn)行搜集：

我們看到，執(zhí)行prefetch情況下，指令的條數(shù)明顯多了，但是它的insn per cycle變大了，所以總的時(shí)間cycles反而減小。其中最主要的原因是cycle_activity.stalls_l3_miss變小了很多次。

這個(gè)時(shí)候，我們可以進(jìn)一步通過(guò)錄制mem_load_retired.l3_miss來(lái)分析究竟代碼哪里出了問(wèn)題，先看noprefetch情況：

焦點(diǎn)在main函數(shù)：

繼續(xù)annotate一下：

明顯問(wèn)題出在array［mid］ 《 key這句話這里。做prefetch的情況下呢？

main的占比明顯變小了（99.93% -》 80.00%）：

繼續(xù)annotate一下：

熱點(diǎn)被分散了，預(yù)取緩解了Memory_Bound的情況。

避免false sharing

前面我們提到過(guò)，數(shù)據(jù)如果在一個(gè)cacheline，被多核訪問(wèn)的時(shí)候，多核間運(yùn)行的cache一致性協(xié)議，會(huì)導(dǎo)致cacheline在多核間的同步。這個(gè)同步會(huì)有很大的延遲，是工程里著名的false sharing問(wèn)題。

比如下面一個(gè)結(jié)構(gòu)體

struct s{ int a; int b;}

如果1個(gè)線程讀寫(xiě)a，另外一個(gè)線程讀寫(xiě)b，那么兩個(gè)線程就有機(jī)會(huì)在不同的核，于是產(chǎn)生cacheline同步行為的來(lái)回顛簸。但是，如果我們把a(bǔ)和b之間padding一些區(qū)域，就可以把這兩個(gè)纏繞在一起的人拉開(kāi)：

struct s{ int a; char padding［cacheline_size - sizeof（int）］; int b;}

因此，在實(shí)際的工程中，我們經(jīng)常看到有人對(duì)數(shù)據(jù)的位置進(jìn)行移位，或者在2個(gè)可能引起false sharing的數(shù)據(jù)間填充數(shù)據(jù)進(jìn)行padding。這樣的代碼在內(nèi)核不甚枚舉，我們隨便找一個(gè)：

它特別提到在tw_count后面60個(gè)字節(jié)（L1_CACHE_BYTES - sizeof（atomic_t））的padding，從而避免false sharing：

下面這個(gè)則是通過(guò)移動(dòng)結(jié)構(gòu)體內(nèi)部成員的位置，相關(guān)數(shù)據(jù)的cacheline分開(kāi)的：

這個(gè)改動(dòng)有明顯的性能提升，最高可達(dá)9.9%。代碼里面也有明顯地注釋?zhuān)瑄sage和parent原先靠地太近，一個(gè)頻繁寫(xiě)，一個(gè)頻繁讀。移開(kāi)了2邊互相不打架了：

把理論和代碼能對(duì)上的感覺(jué)真TNND爽。無(wú)論是996，還是007，都必須留些時(shí)間來(lái)思考，來(lái)讓理論和實(shí)踐結(jié)合，否則，就變成漫無(wú)目的的內(nèi)卷，這樣一定會(huì)卷輸?shù)摹?nèi)卷并不可悲，可悲的是卷不贏別人。

編輯：jq