「每日分享」CPU Cache 与缓存行
您的關注、點贊、轉發是對我們最大的支持
原創: 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 各級緩存存取速度的對比
大致可以得出結論,緩存層級越接近于 CPU core,容量越小,速度越快,同時,沒有披露的一點是其造價也更貴。所以為了支撐更多的熱點數據,同時追求最高的性價比,多級緩存架構應運而生。
什么是緩存行(Cache Line)?
上面我們介紹了 CPU 多級緩存的概念,而之后的章節我們將嘗試忽略“多級”這個特性,將之合并為 CPU 緩存,這對于我們理解 CPU 緩存的工作原理并無大礙。
緩存行 (Cache Line) 便是 CPU Cache 中的最小單位,CPU Cache 由若干緩存行組成,一個緩存行的大小通常是 64 字節(這取決于 CPU),并且它有效地引用主內存中的一塊地址。一個 Java 的 long 類型是 8 字節,因此在一個緩存行中可以存 8 個 long 類型的變量。
多級緩存
試想一下你正在遍歷一個長度為 16 的 long 數組 data[16],原始數據自然存在于主內存中,訪問過程描述如下
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 之后想想可不可以有一些特殊的回答技巧呢?
總結
以上是生活随笔為你收集整理的「每日分享」CPU Cache 与缓存行的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Android Webview H5 秒
- 下一篇: 课堂练习2