衆所周知, 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位筆記本上運作時的記憶體分布如圖:
加上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行注釋, 編譯後再次運作,結果是不是比我們預想得還糟?
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
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, 再看看慢的程式
duration = 21095062165
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滿, 一般情況下我們需要減少操作的資料大小, 盡量按資料的實體順序通路資料.