Java 理解CPU緩存(CPU Cache)

從Java視角理解系統結構連載, 關注我的微博(鏈接)了解最新動態?

眾所周知, CPU是計算機的大腦, 它負責執行程序的指令; 內存負責存數據, 包括程序自身數據. 同樣大家都知道, 內存比CPU慢很多. 其實在30年前, CPU的頻率和內存總線的頻率在同一個級別, 訪問內存只比訪問CPU寄存器慢一點兒. 由于內存的發展都到技術及成本的限制, 現在獲取內存中的一條數據大概需要200多個CPU周期(CPU cycles), 而CPU寄存器一般情況下1個CPU周期就夠了.?

CPU緩存?
網頁瀏覽器為了加快速度,會在本機存緩存以前瀏覽過的數據; 傳統數據庫或NoSQL數據庫為了加速查詢, 常在內存設置一個緩存, 減少對磁盤(慢)的IO. 同樣內存與CPU的速度相差太遠, 于是CPU設計者們就給CPU加上了緩存(CPU Cache). 如果你需要對同一批數據操作很多次, 那么把數據放至離CPU更近的緩存, 會給程序帶來很大的速度提升. 例如, 做一個循環計數, 把計數變量放到緩存里,就不用每次循環都往內存存取數據了. 下面是CPU Cache的簡單示意圖.??
?
隨著多核的發展, CPU Cache分成了三個級別: L1, L2, L3. 級別越小越接近CPU, 所以速度也更快, 同時也代表著容量越小. L1是最接近CPU的, 它容量最小, 例如32K, 速度最快,每個核上都有一個L1 Cache(準確地說每個核上有兩個L1 Cache, 一個存數據 L1d Cache, 一個存指令 L1i Cache). L2 Cache 更大一些,例如256K, 速度要慢一些, 一般情況下每個核上都有一個獨立的L2 Cache; L3 Cache是三級緩存中最大的一級,例如12MB,同時也是最慢的一級, 在同一個CPU插槽之間的核共享一個L3 Cache.?

從CPU到	大約需要的CPU周期	大約需要的時間(單位ns)
寄存器	1 cycle	?
L1 Cache	~3-4 cycles	~0.5-1 ns
L2 Cache	~10-20 cycles	~3-7 ns
L3 Cache	~40-45 cycles	~15 ns
跨槽傳輸	?	~20 ns
內存	~120-240 cycles	~60-120ns

感興趣的同學可以在Linux下面用cat /proc/cpuinfo, 或Ubuntu下lscpu看看自己機器的緩存情況, 更細的可以通過以下命令看看:?

 $?cat?/sys/devices/system/cpu/cpu0/cache/index0/size??
 32K??
 $?cat?/sys/devices/system/cpu/cpu0/cache/index0/type??
 Data??
 $?cat?/sys/devices/system/cpu/cpu0/cache/index0/level???
 1??
 $?cat?/sys/devices/system/cpu/cpu3/cache/index3/level?????
 3??

就像數據庫cache一樣, 獲取數據時首先會在最快的cache中找數據, 如果沒有命中(Cache miss) 則往下一級找, 直到三層Cache都找不到,那只要向內存要數據了. 一次次地未命中,代表取數據消耗的時間越長.?

緩存行(Cache line)?
為了高效地存取緩存, 不是簡單隨意地將單條數據寫入緩存的.? 緩存是由緩存行組成的, 典型的一行是64字節. 讀者可以通過下面的shell命令,查看cherency_line_size就知道知道機器的緩存行是多大.?

 $?cat?/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size???
 64??

CPU存取緩存都是按行為最小單位操作的. 在這兒我將不提及緩存的associativity問題, 將問題簡化一些. 一個Java long型占8字節, 所以從一條緩存行上你可以獲取到8個long型變量. 所以如果你訪問一個long型數組, 當有一個long被加載到cache中, 你將無消耗地加載了另外7個. 所以你可以非常快地遍歷數組.?

實驗及分析?
我們在Java編程時, 如果不注意CPU Cache, 那么將導致程序效率低下. 例如以下程序, 有一個二維long型數組, 在我的32位筆記本上運行時的內存分布如圖:?
?
32位機器中的java的數組對象頭共占16字節(詳情見?鏈接), 加上62個long型一行long數據一共占512字節. 所以這個二維數據是順序排列的.?

 public?class?L1CacheMiss?{??
 ????private?static?final?int?RUNS?=?10;??
 ????private?static?final?int?DIMENSION_1?=?1024?*?1024;??
 ????private?static?final?int?DIMENSION_2?=?62;??
 ??
 ????private?static?long[][]?longs;??
 ??
 ????public?static?void?main(String[]?args)?throws?Exception?{??
 ????????Thread.sleep(10000);??
 ????????longs?=?new?long[DIMENSION_1][];??
 ????????for?(int?i?=?0;?i?<?DIMENSION_1;?i++)?{??
 ????????????longs[i]?=?new?long[DIMENSION_2];??
 ????????????for?(int?j?=?0;?j?<?DIMENSION_2;?j++)?{??
 ????????????????longs[i][j]?=?0L;??
 ????????????}??
 ????????}??
 ????????System.out.println("starting....");??
 ??
 ????????final?long?start?=?System.nanoTime();??
 ????????long?sum?=?0L;??
 ????????for?(int?r?=?0;?r?<?RUNS;?r++)?{??
 //??????????for?(int?j?=?0;?j?<?DIMENSION_2;?j++)?{??
 //??????????????for?(int?i?=?0;?i?<?DIMENSION_1;?i++)?{??
 //??????????????????sum?+=?longs[i][j];??
 //??????????????}??
 //??????????}??
 ??
 ????????????for?(int?i?=?0;?i?<?DIMENSION_1;?i++)?{??
 ????????????????for?(int?j?=?0;?j?<?DIMENSION_2;?j++)?{??
 ????????????????????sum?+=?longs[i][j];??
 ????????????????}??
 ????????????}??
 ????????}??
 ????????System.out.println("duration?=?"?+?(System.nanoTime()?-?start));??
 ????}??
 }??

編譯后運行,結果如下?

 $?java?L1CacheMiss???
 starting....??
 duration?=?1460583903??

然后我們將22-26行的注釋取消, 將28-32行注釋, 編譯后再次運行,結果是不是比我們預想得還糟??

 $?java?L1CacheMiss???
 starting....??
 duration?=?22332686898??

前面只花了1.4秒的程序, 只做一行的對調要運行22秒. 從上節我們可以知道在加載longs[i][j]時, longs[i][j+1]很可能也會被加載至cache中, 所以立即訪問longs[i][j+1]將會命中L1 Cache, 而如果你訪問longs[i+1][j]情況就不一樣了, 這時候很可能會產生 cache miss導致效率低下.?
下面我們用perf來驗證一下,先將快的程序跑一下.?

 $?perf?stat?-e?L1-dcache-load-misses?java?L1CacheMiss???
 starting....??
 duration?=?1463011588??
 ??
 ?Performance?counter?stats?for?'java?L1CacheMiss':??
 ??
 ???????164,625,965?L1-dcache-load-misses?????????????????????????????????????????
 ??
 ??????13.273572184?seconds?time?elapsed??

一共164,625,965次L1 cache miss, 再看看慢的程序?

 $?perf?stat?-e?L1-dcache-load-misses?java?L1CacheMiss???
 starting....??
 duration?=?21095062165??
 ??
 ?Performance?counter?stats?for?'java?L1CacheMiss':??
 ??
 ?????1,421,402,322?L1-dcache-load-misses?????????????????????????????????????????
 ??
 ??????32.894789436?seconds?time?elapsed??

這回產生了1,421,402,322次 L1-dcache-load-misses, 所以慢多了.?

以上我只是示例了在L1 Cache滿了之后才會發生的cache miss. 其實cache miss的原因有下面三種:?
1. 第一次訪問數據, 在cache中根本不存在這條數據, 所以cache miss, 可以通過prefetch解決.?
2. cache沖突, 需要通過補齊來解決.?
3. 就是我示例的這種, cache滿, 一般情況下我們需要減少操作的數據大小, 盡量按數據的物理順序訪問數據.?
具體的信息可以參考這篇論文.?