天天看點
傳回

關于CPU Cache——程式猿需要知道的那些事

　先來看一張本文所有概念的一個思維導圖

關于CPU Cache——程式猿需要知道的那些事

　　為什麼要有CPU Cache

　　随着工藝的提升最近幾十年CPU的頻率不斷提升，而受制于制造技術和成本限制，目前計算機的記憶體主要是DRAM并且在通路速度上沒有質的突破。是以，CPU的處理速度和記憶體的通路速度差距越來越大，甚至可以達到上萬倍。這種情況下傳統的CPU通過FSB直連記憶體的方式顯然就會因為記憶體通路的等待，導緻計算資源大量閑置，降低CPU整體吞吐量。同時又由于記憶體資料通路的熱點集中性，在CPU和記憶體之間用較為快速而成本較高的SDRAM做一層緩存，就顯得成本效益極高了。

　　為什麼要有多級CPU Cache

　　随着科技發展，熱點資料的體積越來越大，單純的增加一級緩存大小的成本效益已經很低了。是以，就慢慢出現了在一級緩存(L1 Cache)和記憶體之間又增加一層通路速度和成本都介于兩者之間的二級緩存(L2 Cache)。下面是一段從What Every Programmer Should Know About Memory中摘錄的解釋：

Soon after the introduction of the cache the system got more complicated. The speed difference between the cache and the main memory increased again, to a point that another level of cache was added, bigger and slower than the first-level cache. Only increasing the size of the first-level cache was not an option for economical rea- sons.

　　此外，又由于程式指令和程式資料的行為和熱點分布差異很大，是以L1 Cache也被劃分成L1i (i for instruction)和L1d (d for data)兩種專門用途的緩存。

　　什麼是Cache Line

　　Cache Line可以簡單的了解為CPU Cache中的最小緩存機關。目前主流的CPU Cache的Cache Line大小都是64Bytes。假設我們有一個512位元組的一級緩存，那麼按照64B的緩存機關大小來算，這個一級緩存所能存放的緩存個數就是

512/64 = 8

個。具體參見下圖：

關于CPU Cache——程式猿需要知道的那些事

　　為了更好的了解Cache Line，我們還可以在自己的電腦上做下面這個有趣的實驗。

　　下面這段C代碼，會從指令行接收一個參數作為數組的大小建立一個數量為N的int數組。并依次循環的從這個數組中進行數組内容通路，循環10億次。最終輸出數組總大小和對應總執行時間。

#include "stdio.h"
#include <stdlib.h>
#include <sys/time.h>

long timediff(clock_t t1, clock_t t2) {
    long elapsed;
    elapsed = ((double)t2 - t1) / CLOCKS_PER_SEC * 1000;
    return elapsed;
}

int main(int argc, char *argv[])
#*******
{

    int array_size=atoi(argv[1]);
    int repeat_times = 1000000000;
    long array[array_size];
    for(int i=0; i<array_size; i++){
        array[i] = 0;
    }
    int j=0;
    int k=0;
    int c=0;
    clock_t start=clock();
    while(j++<repeat_times){
        if(k==array_size){
            k=0;
        }
        c = array[k++];
    }
    clock_t end =clock();
    printf("%lu\n", timediff(start,end));
    return 0;
}

　　如果我們把這些資料做成折線圖後就會發現：總執行時間在數組大小超過64Bytes時有較為明顯的拐點（當然，由于部落客是在自己的Mac筆記本上測試的，會受到很多其他程式的幹擾，是以會有波動）。原因是當數組小于64Bytes時數組極有可能落在一條Cache Line内，而一個元素的通路就會使得整條Cache Line被填充，因而值得後面的若幹個元素受益于緩存帶來的加速。而當數組大于64Bytes時，必然至少需要兩條Cache Line，繼而在循環通路時會出現兩次Cache Line的填充，由于緩存填充的時間遠高于資料通路的響應時間，是以多一次緩存填充對于總執行的影響會被放大，最終得到下圖的結果：

關于CPU Cache——程式猿需要知道的那些事

　　如果讀者有興趣的話也可以在自己的linux或者MAC上通過

gcc cache_line_size.c -o cache_line_size

編譯，并通過

./cache_line_size

執行。

　　了解Cache Line的概念對我們程式猿有什麼幫助？

　　我們來看下面這個C語言中常用的循環優化例子

　　下面兩段代碼中，第一段代碼在C語言中總是比第二段代碼的執行速度要快。具體的原因相信你仔細閱讀了Cache Line的介紹後就很容易了解了。

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        int num;    
        //code
        arr[i][j] = num;
    }
}      
for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
        int num;    
        //code
        arr[j][i] = num;
    }
}

　　CPU Cache 是如何存放資料的

　　你會怎麼設計Cache的存放規則

　　我們先來嘗試回答一下那麼這個問題：

假設我們有一塊4MB的區域用于緩存，每個緩存對象的唯一辨別是它所在的實體記憶體位址。每個緩存對象大小是64Bytes，所有可以被緩存對象的大小總和（即實體記憶體總大小）為4GB。那麼我們該如何設計這個緩存？

　　如果你和部落客一樣是一個大學沒有好好學習基礎/數字電路的人的話，會覺得最靠譜的的一種方式就是：Hash表。把Cache設計成一個Hash數組。記憶體位址的Hash值作為數組的Index，緩存對象的值作為數組的Value。每次存取時，都把位址做一次Hash然後找到Cache中對應的位置操作即可。

　　這樣的設計方式在高等語言中很常見，也顯然很高效。因為Hash值得計算雖然耗時(10000個CPU Cycle左右)，但是相比程式中其他操作（上百萬的CPU Cycle）來說可以忽略不計。而對于CPU Cache來說，本來其設計目标就是在幾十CPU Cycle内擷取到資料。如果通路效率是百萬Cycle這個等級的話，還不如到Memory直接擷取資料。當然，更重要的原因是在硬體上要實作Memory Address Hash的功能在成本上是非常高的。

　　為什麼Cache不能做成Fully Associative

　　Fully Associative 字面意思是全關聯。在CPU Cache中的含義是：如果在一個Cache集内，任何一個記憶體位址的資料可以被緩存在任何一個Cache Line裡，那麼我們成這個cache是Fully Associative。從定義中我們可以得出這樣的結論：給到一個記憶體位址，要知道他是否存在于Cache中，需要周遊所有Cache Line并比較緩存内容的記憶體位址。而Cache的本意就是為了在盡可能少得CPU Cycle内取到資料。那麼想要設計一個快速的Fully Associative的Cache幾乎是不可能的。

　　為什麼Cache不能做成Direct Mapped

　　和Fully Associative完全相反，使用Direct Mapped模式的Cache給定一個記憶體位址，就唯一确定了一條Cache Line。設計複雜度低且速度快。那麼為什麼Cache不使用這種模式呢？讓我們來想象這麼一種情況：一個擁有1M L2 Cache的32位CPU，每條Cache Line的大小為64Bytes。那麼整個L2Cache被劃為了

1M/64=16384

條Cache Line。我們為每條Cache Line從0開始編上号。同時64位CPU所能管理的記憶體位址範圍是

2^32=4G

，那麼Direct Mapped模式下，記憶體也被劃為

4G/16384=256K

的小份。也就是說每256K的記憶體位址共享一條Cache Line。但是，這種模式下每條Cache Line的使用率如果要做到接近100%，就需要作業系統對于記憶體的配置設定和通路在位址上也是近乎平均的。而與我們的意願相反，為了減少記憶體碎片和實作便捷，作業系統更多的是連續集中的使用記憶體。這樣會出現的情況就是0-1000号這樣的低編号Cache Line由于記憶體經常被配置設定并使用，而16000号以上的Cache Line由于記憶體鮮有程序通路，幾乎一直處于空閑狀态。這種情況下，本來就寶貴的1M二級CPU緩存，使用率也許50%都無法達到。

　　什麼是N-Way Set Associative

　　為了避免以上兩種設計模式的缺陷，N-Way Set Associative緩存就出現了。他的原理是把一個緩存按照N個Cache Line作為一組（set），緩存按組劃為等分。這樣一個64位系統的記憶體位址在4MB二級緩存中就劃成了三個部分（見下圖），低位6個bit表示在Cache Line中的偏移量，中間12bit表示Cache組号（set index），剩餘的高位46bit就是記憶體位址的唯一id。這樣的設計相較前兩種設計有以下兩點好處：

  • 給定一個記憶體位址可以唯一對應一個set，對于set中隻需周遊16個元素就可以确定對象是否在緩存中（Full Associative中比較次數随記憶體大小線性增加）
  • 每

    2^18(512K)*64

     =

    32M

     的連續熱點資料才會導緻一個set内的conflict（Direct Mapped中512K的連續熱點資料就會出現conflict）
關于CPU Cache——程式猿需要知道的那些事

　　為什麼N-Way Set Associative的Set段是從低位而不是高位開始的

　　下面是一段從How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses摘錄的解釋：

The vast majority of accesses are close together, so moving the set index bits upwards would cause more conflict misses. You might be able to get away with a hash function that isn’t simply the least significant bits, but most proposed schemes hurt about as much as they help while adding extra complexity.

　　由于記憶體的通路通常是大片連續的，或者是因為在同一程式中而導緻位址接近的（即這些記憶體位址的高位都是一樣的）。是以如果把記憶體位址的高位作為set index的話，那麼短時間的大量記憶體通路都會因為set index相同而落在同一個set index中，進而導緻cache conflicts使得L2, L3 Cache的命中率低下，影響程式的整體執行效率。

　　了解N-Way Set Associative的存儲模式對我們有什麼幫助

　　了解N-Way Set的概念後，我們不難得出以下結論：

2^(6Bits <Cache Line Offset> + 12Bits <Set Index>)

 = 

2^18

 = 

512K

。即在連續的記憶體位址中每512K都會出現一個處于同一個Cache Set中的緩存對象。也就是說這些對象都會争搶一個僅有16個空位的緩存池（16-Way Set）。而如果我們在程式中又使用了所謂優化神器的“記憶體對齊”的時候，這種争搶就會越發增多。效率上的損失也會變得非常明顯。具體的實際測試我們可以參考： How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses 一文。

　　這裡我們引用一張Gallery of Processor Cache Effects 中的測試結果圖，來解釋下記憶體對齊在極端情況下帶來的性能損失。

關于CPU Cache——程式猿需要知道的那些事

　　該圖實際上是我們上文中第一個測試的一個變種。縱軸表示了測試對象數組的大小。橫軸表示了每次數組元素通路之間的index間隔。而圖中的顔色表示了響應時間的長短，藍色越明顯的部分表示響應時間越長。從這個圖我們可以得到很多結論。當然這裡我們隻對記憶體帶來的性能損失感興趣。有興趣的讀者也可以閱讀原文分析了解其他從圖中可以得到的結論。

　　從圖中我們不難看出圖中每1024個步進，即每

1024*4

即4096Bytes，都有一條特别明顯的藍色豎線。也就是說，隻要我們按照4K的步進去通路記憶體(記憶體根據4K對齊），無論熱點資料多大它的實際效率都是非常低的！按照我們上文的分析，如果4KB的記憶體對齊，那麼一個80MB的數組就含有20480個可以被通路到的數組元素；而對于一個每512K就會有set沖突的16Way二級緩存，總共有

512K/20480

=

25

個元素要去争搶16個空位。那麼緩存命中率隻有64%，自然效率也就低了。

　　想要知道更多關于記憶體位址對齊在目前的這種CPU-Cache的架構下會出現的問題可以詳細閱讀以下兩篇文章：

  • How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses
  • Gallery of Processor Cache Effects

　　Cache淘汰政策

　　在文章的最後我們順帶提一下CPU Cache的淘汰政策。常見的淘汰政策主要有

LRU

和

Random

兩種。通常意義下LRU對于Cache的命中率會比Random更好，是以CPU Cache的淘汰政策選擇的是

LRU

。當然也有些實驗顯示在Cache Size較大的時候Random政策會有更高的命中率

　　總結

　　CPU Cache對于程式猿是透明的，所有的操作和政策都在CPU内部完成。但是，了解和了解CPU Cache的設計、工作原理有利于我們更好的利用CPU Cache，寫出更多對CPU Cache友好的程式

　　參考

  1. Gallery of Processor Cache Effects
  2. How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses
  3. Introduction to Caches
計算機底層 C++性能優化 cache
上一篇: 電腦C槽滿了？整理一份超全清理方法大全給你。做完幹幹淨淨
下一篇: 億級别記錄的mongodb批量導入Es的java代碼完整實作

繼續閱讀