您的關注、點贊、轉發是對我們最大的支持

原創： kiritomoe

引言

如上述代碼所示，定義了一個二維數組 long[][] arr 并且使用了橫向遍歷和縱向遍歷兩種順序對這個二位數組進行遍歷，遍歷總次數相同，只不過循環的方向不同，代碼中記錄了這兩種遍歷方式的耗時，不妨先賣個關子，他們的耗時會有區別嗎？

這問題問的和中小學試卷中的：“它們之間有區別嗎？如有，請說出區別?！币粯記]有水準，沒區別的話文章到這兒就結束了。事實上，在我的機器上（64 位 mac）多次運行后可以發現：橫向遍歷的耗時大約為 25 ms，縱向遍歷的耗時大約為 60 ms，前者比后者快了 1 倍有余。如果你了解上述現象出現的原因，大概能猜到，今天這篇文章的主角便是他了— CPU Cache&Cache Line。

在學生生涯時，不斷收到這樣建議：《計算機網絡》、《計算機組成原理》、《計算機操作系統》、《數據結構》四門課程是至關重要的，而在我這些年的工作經驗中也不斷地意識到前輩們如此建議的原因。作為一個 Java 程序員，你可以選擇不去理解操作系統，組成原理（相比這二者，網絡和數據結構跟日常工作聯系得相對緊密），這不會降低你的 KPI，但了解他們可以使你寫出更加計算機友好（Mechanical Sympathy）的代碼。

下面的章節將會出現不少操作系統相關的術語，我將逐個介紹他們，并最終將他們與 Java 聯系在一起。

什么是 CPU 高速緩存？

CPU 是計算機的心臟，最終由它來執行所有運算和程序。主內存（RAM）是數據（包括代碼行）存放的地方。這兩者的定義大家應該不會陌生，那 CPU 高速緩存又是什么呢？

在計算機系統中，CPU高速緩存是用于減少處理器訪問內存所需平均時間的部件。在金字塔式存儲體系中它位于自頂向下的第二層，僅次于CPU寄存器。其容量遠小于內存，但速度卻可以接近處理器的頻率。當處理器發出內存訪問請求時，會先查看緩存內是否有請求數據。如果存在（命中），則不經訪問內存直接返回該數據；如果不存在（失效），則要先把內存中的相應數據載入緩存，再將其返回處理器。緩存之所以有效，主要是因為程序運行時對內存的訪問呈現局部性（Locality）特征。這種局部性既包括空間局部性（Spatial Locality），也包括時間局部性（Temporal Locality）。有效利用這種局部性，緩存可以達到極高的命中率。在處理器看來，緩存是一個透明部件。因此，程序員通常無法直接干預對緩存的操作。但是，確實可以根據緩存的特點對程序代碼實施特定優化，從而更好地利用緩存?！?維基百科

CPU 緩存架構

左圖為最簡單的高速緩存的架構，數據的讀取和存儲都經過高速緩存，CPU 核心與高速緩存有一條特殊的快速通道；主存與高速緩存都連在系統總線上（BUS），這條總線還用于其他組件的通信。簡而言之，CPU 高速緩存就是位于 CPU 操作和主內存之間的一層緩存。

為什么需要有 CPU 高速緩存？

隨著工藝的提升，最近幾十年 CPU 的頻率不斷提升，而受制于制造工藝和成本限制，目前計算機的內存在訪問速度上沒有質的突破。因此，CPU 的處理速度和內存的訪問速度差距越來越大，甚至可以達到上萬倍。這種情況下傳統的 CPU 直連內存的方式顯然就會因為內存訪問的等待，導致計算資源大量閑置，降低 CPU 整體吞吐量。同時又由于內存數據訪問的熱點集中性，在 CPU 和內存之間用較為快速而成本較高（相對于內存）的介質做一層緩存，就顯得性價比極高了。

為什么需要有 CPU 多級緩存？

結合 圖片 -- CPU 緩存架構，再來看一組 CPU 各級緩存存取速度的對比

各種寄存器，用來存儲本地變量和函數參數，訪問一次需要1cycle，耗時小于1ns；

L1 Cache，一級緩存，本地 core 的緩存，分成 32K 的數據緩存 L1d 和 32k 指令緩存 L1i，訪問 L1 需要3cycles，耗時大約 1ns；

L2 Cache，二級緩存，本地 core 的緩存，被設計為 L1 緩存與共享的 L3 緩存之間的緩沖，大小為 256K，訪問 L2 需要 12cycles，耗時大約 3ns；

L3 Cache，三級緩存，在同插槽的所有 core 共享 L3 緩存，分為多個 2M 的段，訪問 L3 需要 38cycles，耗時大約 12ns；

大致可以得出結論，緩存層級越接近于 CPU core，容量越小，速度越快，同時，沒有披露的一點是其造價也更貴。所以為了支撐更多的熱點數據，同時追求最高的性價比，多級緩存架構應運而生。

什么是緩存行(Cache Line)？

上面我們介紹了 CPU 多級緩存的概念，而之后的章節我們將嘗試忽略“多級”這個特性，將之合并為 CPU 緩存，這對于我們理解 CPU 緩存的工作原理并無大礙。

緩存行 (Cache Line) 便是 CPU Cache 中的最小單位，CPU Cache 由若干緩存行組成，一個緩存行的大小通常是 64 字節（這取決于 CPU），并且它有效地引用主內存中的一塊地址。一個 Java 的 long 類型是 8 字節，因此在一個緩存行中可以存 8 個 long 類型的變量。

多級緩存

試想一下你正在遍歷一個長度為 16 的 long 數組 data[16]，原始數據自然存在于主內存中，訪問過程描述如下

訪問 data[0]，CPU core 嘗試訪問 CPU Cache，未命中。

嘗試訪問主內存，操作系統一次訪問的單位是一個 Cache Line 的大小 — 64 字節，這意味著：既從主內存中獲取到了 data[0] 的值，同時將 data[0] ~ data[7] 加入到了 CPU Cache 之中，for free~

訪問 data[1]~data[7]，CPU core 嘗試訪問 CPU Cache，命中直接返回。

訪問 data[8]，CPU core 嘗試訪問 CPU Cache，未命中。

嘗試訪問主內存。重復步驟 2

CPU 緩存在順序訪問連續內存數據時揮發出了最大的優勢。試想一下上一篇文章中提到的 PageCache，其實發生在磁盤 IO 和內存之間的緩存，是不是有異曲同工之妙？只不過今天的主角— CPU Cache，相比 PageCache 更加的微觀。

再回到文章的開頭，為何橫向遍歷 arr = new long[1024 * 1024][8] 要比縱向遍歷更快？此處得到了解答，正是更加友好地利用 CPU Cache 帶來的優勢，甚至有一個專門的詞來修飾這種行為 — Mechanical Sympathy。

偽共享

通常提到緩存行，大多數文章都會提到偽共享問題（正如提到 CAS 便會提到 ABA 問題一般）。

偽共享指的是多個線程同時讀寫同一個緩存行的不同變量時導致的 CPU 緩存失效。盡管這些變量之間沒有任何關系，但由于在主內存中鄰近，存在于同一個緩存行之中，它們的相互覆蓋會導致頻繁的緩存未命中，引發性能下降。偽共享問題難以被定位，如果系統設計者不理解 CPU 緩存架構，甚至永遠無法發現 — 原來我的程序還可以更快。

偽共享

正如圖中所述，如果多個線程的變量共享了同一個 CacheLine，任意一方的修改操作都會使得整個 CacheLine 失效（因為 CacheLine 是 CPU 緩存的最小單位），也就意味著，頻繁的多線程操作，CPU 緩存將會徹底失效，降級為 CPU core 和主內存的直接交互。

偽共享問題的解決方法便是字節填充。

偽共享-字節填充

我們只需要保證不同線程的變量存在于不同的 CacheLine 即可，使用多余的字節來填充可以做點這一點，這樣就不會出現偽共享問題。在代碼層面如何實現圖中的字節填充呢？

Java6 中實現字節填充

PaddingObject 類中需要保存一個 long 類型的 value 值，如果多線程操作同一個 CacheLine 中的 PaddingObject 對象，便無法完全發揮出 CPU Cache 的優勢（想象一下你定義了一個 PaddingObject[] 數組，數組元素在內存中連續，卻由于偽共享導致無法使用 CPU Cache 帶來的沮喪）。

不知道你注意到沒有，實際數據 value + 用于填充的 p1~p6 總共只占據了 7 * 8 = 56 個字節，而 Cache Line 的大小應當是 64 字節，這是有意而為之，在 Java 中，對象頭還占據了 8 個字節，所以一個 PaddingObject 對象可以恰好占據一個 Cache Line。

Java7 中實現字節填充

在 Java7 之后，一個 JVM 的優化給字節填充造成了一些影響，上面的代碼片段 public long p1, p2, p3, p4, p5, p6; 會被認為是無效代碼被優化掉，有回歸到了偽共享的窘境之中。

為了避免 JVM 的自動優化，需要使用繼承的方式來填充。

Tips:實際上我在本地 mac 下測試過 jdk1.8 下的字節填充，并不會出現無效代碼的優化，個人猜測和 jdk 版本有關，不過為了保險起見，還是使用相對穩妥的方式去填充較為合適。

如果你對這個現象感興趣，測試代碼如下：

Java8 中實現字節填充

Java8 中終于提供了字節填充的官方實現，這無疑使得 CPU Cache 更加可控了，無需擔心 jdk 的無效字段優化，無需擔心 Cache Line 在不同 CPU 下的大小究竟是不是 64 字節。使用 @Contended 注解可以完美的避免偽共享問題。

一些最佳實踐

可能有讀者會問：作為一個普通開發者，需要關心 CPU Cache 和 Cache Line 這些知識點嗎？這就跟前幾天比較火的話題：「程序員有必要懂 JVM 嗎？」一樣，仁者見仁了。但確實有不少優秀的源碼在關注著這些問題。他們包括：

ConcurrentHashMap

面試中問到要吐的 ConcurrentHashMap 中，使用 @sun.misc.Contended 對靜態內部類 CounterCell 進行修飾。另外還包括并發容器 Exchanger 也有相同的操作。

Thread

Thread 線程類的源碼中，使用 @sun.misc.Contended 對成員變量進行修飾。

RingBuffer

來源于一款優秀的開源框架 Disruptor 中的一個數據結構 RingBuffer ，我后續會專門花一篇文章的篇幅來介紹這個數據結構

使用字節填充和繼承的方式來避免偽共享。

面試題擴展

問：說說數組和鏈表這兩種數據結構有什么區別？

了解了 CPU Cache 和 Cache Line 之后想想可不可以有一些特殊的回答技巧呢？

總結

以上是生活随笔為你收集整理的「每日分享」CPU Cache 与缓存行的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。