深入理解 cache 對寫好程式碼至關重要

CACHE 基礎

對cache的掌握，對於Linux工程師（其他的非Linux工程師也一樣）寫出高效能程式碼，以及優化Linux系統的效能是至關重要的。簡單來說，cache快，記憶體慢，硬碟更慢。在一個典型的現代CPU中比較接近改進的哈佛結構，cache的排布大概是這樣的：

L1速度> L2速度> L3速度> RAM

L1容量< L2容量< L3容量< RAM

現代CPU，通常L1 cache的指令和資料是分離的。這樣可以實現2條高速公路並行訪問，CPU可以同時load指令和資料。當然，cache也不一定是一個core獨享，現代很多CPU的典型分佈是這樣的，比如多個core共享一個L3。比如這臺的Linux裡面運行lstopo命令：

人們也常常稱呼L2cache為MLC（MiddleLevel Cache）,L3cache為LLC（Last LevelCache）。這些Cache究竟有多塊呢？我們來看看Intel的資料，具體配置：Intel i7-4770 (Haswell), 3.4 GHz (Turbo Boostoff), 22 nm. RAM: 32 GB (PC3-12800 cl11 cr2)

訪問延遲：

資料來源：https://www.7-cpu.com/cpu/Haswell.html

由此我們可以知道，我們應該儘可能追求cache的命中率高，以避免延遲，最好是低階cache的命中率越高越好。

CACHE 的組織

現代的cache基本按照這個模式來組織：SET、WAY、TAG、INDEX，這幾個概念是理解Cache的關鍵。隨便開啟一個數據手冊，就可以看到這樣的字眼：

翻譯成中文就是4路（way）組（set）相聯，VIPT表現為(behave as)PIPT --這尼瑪什麼鬼？，cacheline的長度是64位元組。

下面我們來想象一個16KB大小的cache，假設是4路組相聯，cacheline的長度是64位元組。Cacheline的概念比較簡單，cache的整個替換是以行為單位的，一行64個位元組裡面讀了任何一個位元組，其實整個64位元組就進入了cache。

比如下面兩段程式，前者的計算量是後者的8倍：

但是它的執行時間，則遠遠不到後者的8倍：

16KB的cache是4way的話，每個set包括4*64B，則整個cache分為16KB/64B/4 = 64set，也即2的6次方。當CPU從cache裡面讀資料的時候，它會用地址位的BIT6-BIT11來定址set，BIT0-BIT5是cacheline內的offset。

比如CPU訪問地址

或者

或者

由於它們紅色的6位都相同，所以他們全部都會找到第0個set的cacheline。第0個set裡面有4個way，之後硬體會用地址的高位如0,1，YYYY作為tag，去檢索這4個way的tag是否與地址的高位相同，而且cacheline是否有效，如果tag匹配且cacheline有效，則cache命中。

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

中間紅色的位就是INDEX，前面YYYY這些位就是TAG。具體的實現可以是用虛擬地址或者實體地址的相應位做TAG或者INDEX。如果用虛擬地址做TAG，我們叫VT；如果用實體地址做TAG，我們叫PT；如果用虛擬地址做INDEX，我們叫VI；如果用實體地址做TAG，我們叫PT。工程中碰到的cache可能有這麼些組合：

VIVT、VIPT、PIPT。

VIVT的硬體實現開銷最低，但是軟體維護成本高；PIPT的硬體實現開銷最高，但是軟體維護成本最低；VIPT介於二者之間，但是有些硬體是VIPT，但是behave as PIPT，這樣對軟體而言，維護成本與PIPT一樣。

在VIVT的情況下，CPU發出的虛擬地址，不需要經過MMU的轉化，直接就可以去查cache。

而在VIPT和PIPT的場景下，都涉及到虛擬地址轉換為實體地址後，再去比對cache的過程。VIPT如下：

PIPT如下：

從圖上看起來，VIVT的硬體實現效率很高，不需要經過MMU就可以去查cache了。不過，對軟體來說，這是個災難。因為VIVT有嚴重的歧義和別名問題。

歧義：一個虛擬地址先後指向兩個（或者多個）實體地址

別名：兩個（或者多個）虛擬地址同時指向一個實體地址

這裡我們重點看別名問題。比如2個虛擬地址對應同一個實體地址，基於VIVT的邏輯，無論是INDEX還是TAG，2個虛擬地址都是可能不一樣的(儘管他們的實體地址一樣，但是實體地址在cache比對中完全不摻和)，這樣它們完全可能在2個cacheline同時命中。

由於2個虛擬地址指向1個實體地址，這樣CPU寫過第一個虛擬地址後，寫入cacheline1。CPU讀第2個虛擬地址，讀到的是過時的cacheline2，這樣就出現了不一致。所以，為了避免這種情況，軟體必須寫完虛擬地址1後，對虛擬地址1對應的cache執行clean，對虛擬地址2對應的cache執行invalidate。

而PIPT完全沒有這樣的問題，因為無論多少虛擬地址對應一個實體地址，由於實體地址一樣，我們是基於實體地址去尋找和比對cache的，所以不可能出現這種別名問題。

那麼VIPT有沒有可能出現別名呢？答案是有可能，也有可能不能。如果VI恰好對於PI，就不可能，這個時候，VIPT對軟體而言就是PIPT了：

VI=PI

PT=PT

那麼什麼時候VI會等於PI呢？這個時候我們來回憶下虛擬地址往實體地址的轉換過程，它是以頁為單位的。假設一頁是4K，那麼地址的低12位虛擬地址和實體地址是完全一樣的。回憶我們前面的地址：

YYYYY000000XXXXXX

其中紅色的000000是INDEX。在我們的例子中，紅色的6位和後面的XXXXXX（cache內部偏移）加起來正好12位，所以這個000000經過虛實轉換後，其實還是000000的，這個時候VI=PI，VIPT沒有別名問題。

我們原先假設的cache是：16KB大小的cache，假設是4路組相聯，cacheline的長度是64位元組，這樣我們正好需要紅色的6位來作為INDEX。但是如果我們把cache的大小增加為32KB，這樣我們需要 32KB/4/64B=128=2^7，也即7位來做INDEX。

YYYY0000000XXXXXX

這樣VI就可能不等於PI了，因為紅色的最高位超過了2^12的範圍，完全可能出現如下2個虛擬地址，指向同一個實體地址：

這樣就出現了別名問題，我們在工程裡，可能可以通過一些辦法避免這種別名問題，比如軟體在建立虛實轉換的時候，把虛實轉換往2^13而不是2^12對齊，讓實體地址的低13位而不是低12位與實體地址相同，這樣強行繞開別名問題，下圖中，2個虛擬地址指向了同一個實體地址，但是它們的INDEX是相同的，這樣VI=PI，就繞開了別名問題。這通常是PAGE COLOURING技術中的一種技巧。

如果這種PAGE COLOURING的限制對軟體仍然不可接受，而我們又想享受VIPT的INDEX不需要經過MMU虛實轉換的快捷？有沒有什麼硬體技術來解決VIPT別名問題呢？確實是存在的，現代CPU很多都是把L1 CACHE做成VIPT，但是表現地（behave as）像PIPT。這是怎麼做到的呢？

這要求VIPT的cache，硬體上具備alias detection的能力。比如，硬體知道YYYY0000000XXXXXX既有可能出現在第0000000，又可能出現在1000000這2個set，然後硬體自動去比對這2個set裡面是否出現對映到相同實體地址的cacheline，並從硬體上解決好別名同步，那麼軟體就完全不用操心了。

下面我們記住一個簡單的規則：

對於VIPT，如果cache的size除以WAY數，小於等於1個page的大小，則天然VI=PI，無別名問題；

對於VIPT，如果cache的size除以WAY數，大於1個page的大小，則天然VI≠PI，有別名問題；這個時候又分成2種情況:

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

• 硬體具備alias detection能力，軟體把cache當成PIPT用。

比如cache大小64KB，4WAY，PAGE SIZE是4K，顯然有別名問題；這個時候，如果cache改為16WAY，或者PAGE SIZE改為16K，不再有別名問題。為什麼？感覺小學數學知識也能算得清

CACHE 的一致性

Cache的一致性有這麼幾個層面

1. 一個CPU的icache和dcache的同步問題

2. 多個CPU各自的cache同步問題

3. CPU與裝置（其實也可能是個異構處理器，不過在Linux運行的CPU眼裡，都是裝置，都是DMA）的cache同步問題

先看一下ICACHE和DCACHE同步問題。由於程式的運行而言，指令流的都流過icache，而指令中涉及到的資料流經過dcache。所以對於自修改的程式碼（Self-Modifying Code）而言，比如我們修改了記憶體p這個位置的程式碼（典型多見於JIT compiler），這個時候我們是通過store的方式去寫的p，所以新的指令會進入dcache。但是我們接下來去執行p位置的指令的時候，icache裡面可能命中的是修改之前的指令。

所以這個時候軟體需要把dcache的東西clean出去，然後讓icache invalidate，這個開銷顯然還是比較大的。

但是，比如ARM64的N1處理器，它支援硬體的icache同步，詳見文件：The Arm Neoverse N1 Platform: Building Blocks for the Next-Gen Cloud-to-Edge Infrastructure SoC

特別注意畫紅色的幾行。軟體維護的成本實際很高，還涉及到icache的invalidation向所有核廣播的動作。

接下來的一個問題就是多個核之間的cache同步。下面是一個簡化版的處理器，CPU_A和B共享了一個L3，CPU_C和CPU_D共享了一個L3。實際的硬體架構由於涉及到NUMA，會比這個更加複雜，但是這個圖反映層級關係是足夠了。

比如CPU_A讀了一個地址p的變數？CPU_B、C、D又讀，難道B,C,D又必須從RAM裡面經過L3,L2,L1再讀一遍嗎？這個顯然是沒有必要的，在硬體上，cache的snooping控制單元，可以協助直接把CPU_A的p地址cache拷貝到CPU_B、C和D的cache。

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

假設CPU B這個時候，把棕色小球寫成紅色，而其他CPU裡面還是棕色，這樣就會不一致了：

這個時候怎麼辦？這裡面顯然需要一個協議，典型的多核cache同步協議有MESI和MOESI。MOESI相對MESI有些細微的差異，不影響對全局的理解。下面我們重點看MESI協議。

MESI協議定義了4種狀態：

M（Modified）: 當前cache的內容有效，資料已被修改而且與記憶體中的資料不一致，資料只在當前cache裡存在；類似RAM裡面是棕色球，B裡面是紅色球（CACHE與RAM不一致），A、C、D都沒有球。

E（Exclusive）：當前cache的內容有效，資料與記憶體中的資料一致，資料只在當前cache裡存在；類似RAM裡面是棕色球，B裡面是棕色球（RAM和CACHE一致），A、C、D都沒有球。

S（Shared）：當前cache的內容有效，資料與記憶體中的資料一致，資料在多個cache裡存在。類似如下圖，在CPU A-B-C裡面cache的棕色球都與RAM一致。

I（Invalid）： 當前cache無效。前面三幅圖裡面cache沒有球的那些都是屬於這個情況。

然後它有個狀態機

這個狀態機比較難記，死記硬背是記不住的，也沒必要記，它講的cache原先的狀態，經過一個硬體在本cache或者其他cache的讀寫操作後，各個cache的狀態會如何變遷。所以，硬體上不僅僅是監控本CPU的cache讀寫行為，還會監控其他CPU的。只需要記住一點：這個狀態機是為了保證多核之間cache的一致性，比如一個乾淨的資料，可以在多個CPU的cache share，這個沒有一致性問題；但是，假設其中一個CPU寫過了，比如A-B-C本來是這樣：

然後B被寫過了：

這樣A、C的cache實際是過時的資料，這是不允許的。這個時候，硬體會自動把A、C的cache invalidate掉，不需要軟體的干預，A、C其實變地相當於不命中這個球了：

這個時候，你可能會繼續問，如果C要讀這個球呢？它目前的狀態在B裡面是modified的，而且與RAM不一致，這個時候，硬體會把紅球clean，然後B、C、RAM變地一致，B、C的狀態都變化為S（Shared）：

這一系列的動作雖然由硬體完成，但是對軟體而言不是免費的，因為它耗費了時間。如果程式設計的時候不注意，引起了硬體的大量cache同步行為，則程式的效率可能會急劇下降。

為了讓大家直觀感受到這個cache同步的開銷，下面我們寫一個程式，這個程式有2個執行緒，一個寫變數，一個讀變數：

這個程式裡，x和y都是cacheline對齊的，這個程式的thread1的寫，會不停地與thread2的讀，進行cache同步。

它的執行時間為：

它在2個CPU上的userspace共運行了7.021秒，累計這個程式從開始到結束的對應真實世界的時間是3.614秒（就是從命令開始到命令結束的時間）。

如果我們把程式改一句話，把thread2裡面的c = x改為c = y，這樣2個執行緒在2個CPU運行的時候，讀寫的是不同的cacheline，就沒有這個硬體的cache同步開銷了：

它的運行時間：

現在只需要1.8秒，幾乎減小了一半。

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

它單核跑，居然只需要3.299秒跑完，而雙核跑，需要3.614s跑完。單核跑完這個程式，甚至比雙核還快，有沒有驚掉下巴？！！！因為單核裡面沒有cache同步的開銷。

下一個cache同步的重大問題，就是裝置與CPU之間。如果裝置感知不到CPU的cache的話（下圖中的紅色資料流向不經過cache），這樣，做DMA前後，CPU就需要進行相關的cacheclean和invalidate的動作，軟體的開銷會比較大。

這些軟體的動作，若我們在Linux程式設計的時候，使用的是streaming DMA APIs的話，都會被類似這樣的API自動搞定：

如果是使用的dma_alloc_coherent() API呢，則裝置和CPU之間的buffer是cache一致的，不需要每次DMA進行同步。對於不支援硬體cache一致性的裝置而言，很可能dma_alloc_coherent()會把CPU對那段DMA buffer的訪問設定為uncachable的。

這些API把底層的硬體差異封裝掉了，如果硬體不支援CPU和裝置的cache同步的話，延時還是比較大的。那麼，對於底層硬體而言，更好的實現方式，應該仍然是硬體幫我們來搞定。比如我們需要修改匯流排協議，延伸紅線的觸角：

當裝置訪問RAM的時候，可以去snoop CPU的cache：

• 如果做記憶體到外設的DMA，則直接從CPU的cache取modified的資料；

• 如果做外設到記憶體的DMA，則直接把CPU的cache invalidate掉。

這樣，就實現硬體意義上的cache同步。當然，硬體的cache同步，還有一些其他方法，原理上是類似的。注意，這種同步仍然不是免費的，它仍然會消耗bus cycles的。實際上，cache的同步開銷還與距離相關，可以說距離越遠，同步開銷越大，比如下圖中A、B的同步開銷比A、C小。

對於一個NUMA伺服器而言，跨NUMA的cache同步開銷顯然是要比NUMA內的同步開銷大。

意識到 CACHE 的程式設計

通過上一節的程式碼，讀者應該意識到了cache的問題不處理好，程式的運行效能會急劇下降。所以意識到cache的程式設計，對程式設計師是至關重要的。

從CPU流水線的角度講，任何的記憶體訪問延遲都可以簡化為如下公式：

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

cache miss會導致CPU的stall狀態，從而影響效能。現代CPU的微架構分了frontend和backend。frontend負責fetch指令給backend執行，backend執行依賴運算能力和Memory子系統（包括cache）延遲。

backend執行中訪問資料導致的cache miss會導致backend stall，從而降低IPC（instructions per cycle）。減小cache的miss，實際上是一個軟硬體協同設計的任務。比如硬體方面，它支援預取prefetch，通過分析cache miss的pattern，硬體可以提前預取資料，在流水線需要某個資料前，提前先取到cache，從而CPU流水線跑到需要它的時候，不再miss。當然，硬體不一定有那麼聰明，也許它可以學會一些簡單的pattern。但是，對於複雜的無規律的資料，則可能需要軟體通過預取指令，來暗示CPU進行預取。

cache預取

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

眼見為實，我們隨便從Linux核心裡面找一個commit：

因為我們從WiFi收到了一個skb，我們很快就要訪問這個skb裡面的資料來進行packet的分類以及交給IP stack處理了，不如我們先prefetch一下，這樣後面等需要訪問這個skb->data的時候，流水線可以直接命中cache，從而不打斷。

預取的原理有點類似今天星期五，咱們在上海office，下週一需要北京分公司的人來上海office開會。於是，我們通知北京office的人週末坐飛機過來，這樣週一開會的時候就不必等他們了。不預取的情況下，會議開始後，再等北京的人飛過來，會導致stall狀態。

任何東西最終還是要落實到程式碼，talk is cheap，show me the code。下面這個是經典的二分查詢法程式碼，這個程式碼是網上抄的。

特別留意ifdef DO_PREFETCH包著的程式碼，它提前預取了下次的中間值。我們來對比下，不預取和預取情況下，這個同樣的程式碼執行時間的差異。先把cpufreq的影響儘可能關閉掉，設定為performance:

然後我們來對比差異：

開啟prefetch執行時間大約10s, 不prefetch的情況下，11.6s執行完成，效能提升大約14%，所以週末坐飛機太重要了！

現在我們來通過基於perf的pmu-tools（下載地址：https://github.com/andikleen/pmu-tools)，對上面的程式進行topdown分析，分析的時候，為了儘可能減小其他因子的影響，我們把程式通過taskset運行到CPU0。

先看不prefetch的情況，很明顯，程式是backend_bound的，其中DRAM_Bound佔比大，達到75.8%。

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

DRAM_Bound主要對應cycle_activity.stalls_l3_miss事件，我們通過perf stat來分別進行蒐集：

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

這個時候，我們可以進一步通過錄制mem_load_retired.l3_miss來分析究竟程式碼哪裡出了問題，先看noprefetch情況：

焦點在main函數：

繼續annotate一下：

明顯問題出在array[mid] < key這句話這裡。做prefetch的情況下呢？

main的佔比明顯變小了（99.93% -> 80.00%）：

繼續annotate一下：

熱點被分散了，預取緩解了Memory_Bound的情況。

避免false sharing

前面我們提到過，資料如果在一個cacheline，被多核訪問的時候，多核間運行的cache一致性協議，會導致cacheline在多核間的同步。這個同步會有很大的延遲，是工程裡著名的false sharing問題。

比如下面一個結構體

如果1個執行緒讀寫a，另外一個執行緒讀寫b，那麼兩個執行緒就有機會在不同的核，於是產生cacheline同步行為的來回顛簸。但是，如果我們把a和b之間padding一些區域，就可以把這兩個纏繞在一起的人拉開：

因此，在實際的工程中，我們經常看到有人對資料的位置進行移位，或者在2個可能引起false sharing的資料間填充資料進行padding。這樣的程式碼在核心不甚列舉，我們隨便找一個：

它特別提到在tw_count後面60個位元組（L1_CACHE_BYTES - sizeof(atomic_t)）的padding，從而避免false sharing：

下面這個則是通過移動結構體內部成員的位置，相關資料的cacheline分開的：

這個改動有明顯的效能提升，最高可達9.9%。程式碼裡面也有明顯地註釋，usage和parent原先靠地太近，一個頻繁寫，一個頻繁讀。移開了2邊互相不打架了：

把理論和程式碼能對上的感覺真爽。無論是996,還是007,都必須留些時間來思考，來讓理論和實踐結合，否則，就變成漫無目的的內卷，這樣一定會卷輸的。內卷並不可悲，可悲的是卷不贏別人。

小米MIX4最新渲染圖曝光；蘋果首款OLED iPad將於2023年問世；格力將引進鴻蒙作業系統|極客頭條
百億美元合同告吹！微軟「到嘴的鴨子」飛了
勒索過蘋果的黑客REvil又來了？這次是7000萬美元贖金！