您的關注、點贊、轉發是對我們最大的支持
引言
如上述代碼所示，定義了一個二維數組 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 的自動優化，需要使用繼承的方式來填充。
如果你對這個現象感興趣，測試代碼如下：
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 之後想想可不可以有一些特殊的回答技巧呢？
閱讀更多 Java技術架構 的文章
