認識CPU Cache

CPU Cache概述

隨著CPU的頻率不斷提升，而內存的訪問速度卻沒有質的突破，為了彌補訪問內存的速度慢，充分發揮CPU的計算資源，提高CPU整體吞吐量，在CPU與內存之間引入了一級Cache。隨著熱點數據體積越來越大，一級Cache L1已經不滿足發展的要求，引入了二級Cache L2，三級Cache L3。（注：若無特別說明，本文的Cache指CPU Cache，高速緩存）CPU Cache在存儲器層次結構中的示意如下圖：

計算機早已進入多核時代，軟件也越來越多的支持多核運行。一個處理器對應一個物理插槽，多處理器間通過QPI總線相連。一個處理器包含多個核，一個處理器間的多核共享L3 Cache。一個核包含寄存器、L1 Cache、L2 Cache，下圖是Intel Sandy Bridge CPU架構，一個典型的NUMA多處理器結構：

作為程序員，需要理解計算機存儲器層次結構，它對應用程序的性能有巨大的影響。如果需要的程序是在CPU寄存器中的，指令執行時1個周期內就能訪問到他們。如果在CPU Cache中，需要1~30個周期；如果在主存中，需要50~200個周期；在磁盤上，大概需要幾千萬個周期。充分利用它的結構和機制，可以有效的提高程序的性能。

以我們常見的X86芯片為例，Cache的結構下圖所示：整個Cache被分為S個組，每個組是又由E行個最小的存儲單元——Cache Line所組成，而一個Cache Line中有B（B=64）個字節用來存儲數據，即每個Cache Line能存儲64個字節的數據，每個Cache Line又額外包含一個有效位(valid bit)、t個標記位(tag bit)，其中valid bit用來表示該緩存行是否有效；tag bit用來協助尋址，唯一標識存儲在CacheLine中的塊；而Cache Line里的64個字節其實是對應內存地址中的數據拷貝。根據Cache的結構題，我們可以推算出每一級Cache的大小為B×E×S。

那么如何查看自己電腦CPU的Cache信息呢？

在windows下查看方式有多種方式，其中最直觀的是，通過安裝CPU-Z軟件，直接顯示Cache信息，如下圖：

此外，Windows下還有兩種方法：

①Windows API調用GetLogicalProcessorInfo。
②通過命令行系統內部工具CoreInfo。

如果是Linux系統， 可以使用下面的命令查看Cache信息：

ls /sys/devices/system/cpu/cpu0/cache/index0

還有lscpu等命令也可以查看相關信息,如果是Mac系統，可以用sysctl machdep.cpu 命令查看cpu信息。

如果我們用Java編程，還可以通過CacheSize API方式來獲取Cache信息， CacheSize是一個谷歌的小項目，java語言通過它可以進行訪問本機Cache的信息。示例代碼如下：

public static void main(String[] args) throws CacheNotFoundException {CacheInfo info = CacheInfo.getInstance(); CacheLevelInfo l1Datainf = info.getCacheInformation(CacheLevel.L1, CacheType.DATA_CACHE);System.out.println("第一級數據緩存信息："+l1Datainf.toString());CacheLevelInfo l1Instrinf = info.getCacheInformation(CacheLevel.L1, CacheType.INSTRUCTION_CACHE);System.out.println("第一級指令緩存信息："+l1Instrinf.toString());}

打印輸出結果如下：

第一級數據緩存信息：CacheLevelInfo [cacheLevel=L1, cacheType=DATA_CACHE, cacheSets=64, cacheCoherencyLineSize=64, cachePhysicalLinePartitions=1, cacheWaysOfAssociativity=8, isFullyAssociative=false, isSelfInitializing=true, totalSizeInBytes=32768]第一級指令緩存信息：CacheLevelInfo [cacheLevel=L1, cacheType=INSTRUCTION_CACHE, cacheSets=64, cacheCoherencyLineSize=64, cachePhysicalLinePartitions=1, cacheWaysOfAssociativity=8, isFullyAssociative=false, isSelfInitializing=true, totalSizeInBytes=32768]

還可以查詢L2、L3級緩存的信息，這里不做示例。從打印的信息和CPU-Z顯示的信息可以看出，本機的Cache信息是一致的，L1數據/指令緩存大小都為：C=B×E×S=64×8×64=32768字節=32KB。

Cache Line偽共享及解決方案

Cache Line偽共享分析

說偽共享前，先看看Cache Line 在java編程中使用的場景。如果CPU訪問的內存數據不在Cache中（一級、二級、三級），這就產生了Cache Line miss問題，此時CPU不得不發出新的加載指令，從內存中獲取數據。通過前面對Cache存儲層次的理解，我們知道一旦CPU要從內存中訪問數據就會產生一個較大的時延，程序性能顯著降低，所謂遠水救不了近火。為此我們不得不提高Cache命中率，也就是充分發揮局部性原理。

局部性包括時間局部性、空間局部性。時間局部性：對于同一數據可能被多次使用，自第一次加載到Cache Line后，后面的訪問就可以多次從Cache Line中命中，從而提高讀取速度（而不是從下層緩存讀取）。空間局部性：一個Cache Line有64字節塊，我們可以充分利用一次加載64字節的空間，把程序后續會訪問的數據，一次性全部加載進來，從而提高Cache Line命中率（而不是重新去尋址讀取）。

看個例子：內存地址是連續的數組（利用空間局部性），能一次被L1緩存加載完成。

如下代碼，長度為16的row和column數組，在Cache Line 64字節數據塊上內存地址是連續的，能被一次加載到Cache Line中，所以在訪問數組時，Cache Line命中率高，性能發揮到極致。

public int run(int[] row, int[] column) {int sum = 0;for(int i = 0; i < 16; i++ ) {sum += row[i] * column[i];}return sum; }

而上面例子中變量i則體現了時間局部性，i作為計數器被頻繁操作，一直存放在寄存器中，每次從寄存器訪問，而不是從主存甚至磁盤訪問。雖然連續緊湊的內存分配帶來高性能，但并不代表它一直都能帶來高性能。如果把它放在多線程中將會發生什么呢？如圖：

數據X、Y、Z被加載到同一Cache Line中，線程A在Core1修改X，線程B在Core2上修改Y。根據MESI大法，假設是Core1是第一個發起操作的CPU核，Core1上的L1 Cache Line由S（共享）狀態變成M（修改，臟數據）狀態，然后告知其他的CPU核，圖例則是Core2，引用同一地址的Cache Line已經無效了；當Core2發起寫操作時，首先導致Core1將X寫回主存，Cache Line狀態由M變為I（無效），而后才是Core2從主存重新讀取該地址內容，Cache Line狀態由I變成E（獨占），最后進行修改Y操作， Cache Line從E變成M。可見多個線程操作在同一Cache Line上的不同數據，相互競爭同一Cache Line，導致線程彼此牽制影響，變成了串行程序，降低了并發性。此時我們則需要將共享在多線程間的數據進行隔離，使他們不在同一個Cache Line上，從而提升多線程的性能。

Cache Line偽共享處理方案

處理偽共享的兩種方式：

增大數組元素的間隔使得不同線程存取的元素位于不同的cache line上。典型的空間換時間。（Linux cache機制與之相關）

在每個線程中創建全局數組各個元素的本地拷貝，然后結束后再寫回全局數組。

在Java類中，最優化的設計是考慮清楚哪些變量是不變的，哪些是經常變化的，哪些變化是完全相互獨立的，哪些屬性一起變化。舉個例子：

public class Data{long modifyTime;boolean flag;long createTime;char key;int value; }

假如業務場景中，上述的類滿足以下幾個特點：

當value變量改變時，modifyTime肯定會改變

createTime變量和key變量在創建后，就不會再變化。

flag也經常會變化，不過與modifyTime和value變量毫無關聯。

當上面的對象需要由多個線程同時的訪問時，從Cache角度來說，就會有一些有趣的問題。當我們沒有加任何措施時，Data對象所有的變量極有可能被加載在L1緩存的一行Cache Line中。在高并發訪問下，會出現這種問題：

如上圖所示，每次value變更時，根據MESI協議，對象其他CPU上相關的Cache Line全部被設置為失效。其他的處理器想要訪問未變化的數據(key 和 createTime)時，必須從內存中重新拉取數據，增大了數據訪問的開銷。

Padding 方式

正確的方式應該將該對象屬性分組，將一起變化的放在一組，與其他屬性無關的屬性放到一組，將不變的屬性放到一組。這樣當每次對象變化時，不會帶動所有的屬性重新加載緩存，提升了讀取效率。在JDK1.8以前，我們一般是在屬性間增加長整型變量來分隔每一組屬性。被操作的每一組屬性占的字節數加上前后填充屬性所占的字節數，不小于一個cache line的字節數就可以達到要求：

public class DataPadding{long a1,a2,a3,a4,a5,a6,a7,a8;//防止與前一個對象產生偽共享int value;long modifyTime;long b1,b2,b3,b4,b5,b6,b7,b8;//防止不相關變量偽共享;boolean flag;long c1,c2,c3,c4,c5,c6,c7,c8;//long createTime;char key;long d1,d2,d3,d4,d5,d6,d7,d8;//防止與下一個對象產生偽共享 }

通過填充變量，使不相關的變量分開

Contended注解方式

在JDK1.8中，新增了一種注解@sun.misc.Contended，來使各個變量在Cache line中分隔開。注意，jvm需要添加參數-XX:-RestrictContended才能開啟此功能
用時，可以在類前或屬性前加上此注釋：

// 類前加上代表整個類的每個變量都會在單獨的cache line中 @sun.misc.Contended @SuppressWarnings("restriction") public class ContendedData {int value;long modifyTime;boolean flag;long createTime;char key; } 或者這種： // 屬性前加上時需要加上組標簽 @SuppressWarnings("restriction") public class ContendedGroupData {@sun.misc.Contended("group1")int value;@sun.misc.Contended("group1")long modifyTime;@sun.misc.Contended("group2")boolean flag;@sun.misc.Contended("group3")long createTime;@sun.misc.Contended("group3")char key; }

采取上述措施圖示：

JDK1.8 ConcurrentHashMap的處理

java.util.concurrent.ConcurrentHashMap在這個如雷貫耳的Map中，有一個很基本的操作問題，在并發條件下進行++操作。因為++這個操作并不是原子的，而且在連續的Atomic中，很容易產生偽共享（false sharing）。所以在其內部有專門的數據結構來保存long型的數據:

（openjdk\jdk\src\share\classes\java\util\concurrent\ConcurrentHashMap.java line:2506）：/* ---------------- Counter support -------------- *//*** A padded cell for distributing counts. Adapted from LongAdder* and Striped64. See their internal docs for explanation.*/@sun.misc.Contended static final class CounterCell {volatile long value;CounterCell(long x) { value = x; }}

我們看到該類中，是通過@sun.misc.Contended達到防止false sharing的目的

JDK1.8 Thread 的處理

java.lang.Thread在java中，生成隨機數是和線程有著關聯。而且在很多情況下，多線程下產生隨機數的操作是很常見的，JDK為了確保產生隨機數的操作不會產生false sharing ,把產生隨機數的三個相關值設為獨占cache line。

（openjdk\jdk\src\share\classes\java\lang\Thread.java line:2023）// The following three initially uninitialized fields are exclusively// managed by class java.util.concurrent.ThreadLocalRandom. These// fields are used to build the high-performance PRNGs in the// concurrent code, and we can not risk accidental false sharing.// Hence, the fields are isolated with @Contended./** The current seed for a ThreadLocalRandom */@sun.misc.Contended("tlr")long threadLocalRandomSeed;/** Probe hash value; nonzero if threadLocalRandomSeed initialized */@sun.misc.Contended("tlr")int threadLocalRandomProbe;/** Secondary seed isolated from public ThreadLocalRandom sequence */@sun.misc.Contended("tlr")int threadLocalRandomSecondarySeed;

Java中對Cache line經典設計

Disruptor框架

認識Disruptor

LMAX是在英國注冊并受到FCA監管的外匯黃金交易所。也是歐洲第一家也是唯一一家采用多邊交易設施Multilateral Trading Facility（MTF）擁有交易所牌照和經紀商牌照的歐洲頂級金融公司。LMAX的零售金融交易平臺，是建立在JVM平臺上，核心是一個業務邏輯處理器，它能夠在一個線程里每秒處理6百萬訂單。業務邏輯處理器的核心就是Disruptor（注，本文Disruptor基于當前最新3.3.6版本），這是一個Java實現的并發組件，能夠在無鎖的情況下實現網絡的Queue并發操作，它確保任何數據只由一個線程擁有以進行寫訪問，從而消除寫爭用的設計， 這種設計被稱作“破壞者”，也是這樣命名這個框架的。

Disruptor是一個線程內通信框架，用于線程里共享數據。與LinkedBlockingQueue類似，提供了一個高速的生產者消費者模型，廣泛用于批量IO讀寫，在硬盤讀寫相關的程序中應用的十分廣泛，Apache旗下的HBase、Hive、Storm等框架都有在使用Disruptor。LMAX 創建Disruptor作為可靠消息架構的一部分，并將它設計成一種在不同組件中共享數據非常快的方法。Disruptor運行大致流程入下圖：

圖中左側（Input Disruptor部分）可以看作多生產者單消費者模式。外部多個線程作為多生產者并發請求業務邏輯處理器（Business Logic Processor），這些請求的信息經過Receiver存放在粉紅色的圓環中，業務處理器則作為消費者從圓環中取得數據進行處理。右側（Output Disruptor部分）則可看作單生產者多消費者模式。業務邏輯處理器作為單生產者，發布數據到粉紅色圓環中，Publisher作為多個消費者接受業務邏輯處理器的結果。這里兩處地方的數據共享都是通過那個粉紅色的圓環，它就是Disruptor的核心設計RingBuffer。

Disruptor特點

無鎖機制。

沒有CAS操作，避免了內存屏障指令的耗時。

避開了Cache line偽共享的問題，也是Disruptor部分主要關注的主題。

Disruptor對偽共享的處理

RingBuffer類

RingBuffer類（即上節中粉紅色的圓環）的類關系圖如下：

通過源碼分析，RingBuffer的父類，RingBufferFields采用數組來實現存放線程間的共享數據。下圖，第57行，entries數組。

前面分析過數組比鏈表、樹更具有緩存友好性，此處不做細表。不使用LinkedBlockingQueue隊列，是基于無鎖機制的考慮。詳細分析可參考，并發編程網的翻譯。這里我們主要分析RingBuffer的繼承關系中的填充，解決緩存偽共享問題。如下圖：

依據JVM對象繼承關系中父類屬性與子類屬性，內存地址連續排列布局，RingBufferPad的protected long p1,p2,p3,p4,p5,p6,p7;作為緩存前置填充，RingBuffer中的protected long p1,p2,p3,p4,p5,p6,p7;作為緩存后置填充。這樣任意線程訪問RingBuffer時，RingBuffer放在父類RingBufferFields的屬性，都是獨占一行Cache line不會產生偽共享問題。如圖，RingBuffer的操作字段在RingBufferFields中，使用rbf標識：

按照一行緩存64字節計算，前后填充56字節（7個long），中間大于等于8字節的內容都能獨占一行Cache line，此處rbf是大于8字節的。

Sequence類

Sequence類用來跟蹤RingBuffer和事件處理器的增長步數，支持多個并發操作包括CAS指令和寫指令。同時使用了Padding方式來實現，如下為其類結構圖及Padding的類。

Sequence里在volatile long value前后放置了7個long padding，來解決偽共享的問題。示意如圖，此處Value等于8字節：

也許讀者應該會認為這里的圖示比上面RingBuffer的圖示更好理解，這里的操作屬性只有一個value，兩個圖相互結合就更能理解了。

Sequencer的實現

在RingBuffer構造函數里面存在一個Sequencer接口，用來遍歷數據，在生產者和消費者之間傳遞數據。Sequencer有兩個實現類，單生產者模式的實現SingleProducerSequencer與多生產者模式的實現MultiProducerSequencer。它們的類結構如圖：

單生產者是在Cache line中使用padding方式實現，源碼如下：

多生產者則是使用 sun.misc.Unsafe來實現的。如下圖：

總結與使用示例

可見padding方式在Disruptor中是處理偽共享常見的方式，JDK1.8的@Contended很好的解決了這個問題，不知道Disruptor后面的版本是否會考慮使用它。

Disruptor使用示例代碼參考地址。

參考資料:

7個示例科普CPU Cache：http://coolshell.cn/articles/10249.html
Linux Cache 機制：http://www.cnblogs.com/liloke/archive/2011/11/20/2255737.html
《深入理解計算機系統》：第六章部分
Disruptor官方文檔：https://github.com/LMAX-Exchange/disruptor/tree/master/docs
Disruptor并發編程網文檔翻譯：http://ifeve.com/disruptor/

作者簡介：

上海-周衛理、北京-楊珍琪、北京-馮英圣、深圳-姜寄羽 傾力合作，另外感謝惠普系統架構師吳治輝策劃支持。

周衛理：本科，從事Java開發7年，熱愛研究術問題，喜歡運動。目前就職于上海一家互聯網公司，擔任Java后端小組組長，負責分布式系統框架搭建。正往Java高性能編程，大數據中間件方向靠攏。

馮英勝：長期從事Java軟件開發工作，善于復雜業務開發，6年工作經驗，對大數據平臺和分布式架構等有濃厚興趣。目前就職于北京當當網。

姜寄羽：四川大學軟件工程學士。目前在深圳亞略特擔任Java工程師一職。負責Java方面的開發和維護以及新技術預研，對軟件工程、分布式系統和高性能編程有著深厚的理論基礎。

楊珍琪：碩士，會計學士，前HP工程師，參與中國移動BOSS系統開發，現為創業公司CTO。

轉載請注明：馮英勝的博客???Java專家系列：CPU Cache與高性能編程

總結

以上是生活随笔為你收集整理的Java专家系列：CPU Cache与高性能编程的全部內容，希望文章能夠幫你解決所遇到的問題。

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