先來(lái)看一張本文所有概念的一個(gè)思維導(dǎo)圖

為什么要有CPU Cache

隨著工藝的提升最近幾十年CPU的頻率不斷提升，而受制于制造工藝和成本限制，目前計(jì)算機(jī)的內(nèi)存主要是DRAM并且在訪問(wèn)速度上沒(méi)有質(zhì)的突破。因此，CPU的處理速度和內(nèi)存的訪問(wèn)速度差距越來(lái)越大，甚至可以達(dá)到上萬(wàn)倍。這種情況下傳統(tǒng)的CPU通過(guò)FSB直連內(nèi)存的方式顯然就會(huì)因?yàn)閮?nèi)存訪問(wèn)的等待，導(dǎo)致計(jì)算資源大量閑置，降低CPU整體吞吐量。同時(shí)又由于內(nèi)存數(shù)據(jù)訪問(wèn)的熱點(diǎn)集中性，在CPU和內(nèi)存之間用較為快速而成本較高的SDRAM做一層緩存，就顯得性價(jià)比極高了。

為什么要有多級(jí)CPU Cache

隨著科技發(fā)展，熱點(diǎn)數(shù)據(jù)的體積越來(lái)越大，單純的增加一級(jí)緩存大小的性價(jià)比已經(jīng)很低了。因此，就慢慢出現(xiàn)了在一級(jí)緩存(L1 Cache)和內(nèi)存之間又增加一層訪問(wèn)速度和成本都介于兩者之間的二級(jí)緩存(L2 Cache)。下面是一段從What Every Programmer Should Know About Memory中摘錄的解釋?zhuān)?/p>

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.

此外，又由于程序指令和程序數(shù)據(jù)的行為和熱點(diǎn)分布差異很大，因此L1 Cache也被劃分成L1i (i for instruction)和L1d (d for data)兩種專(zhuān)門(mén)用途的緩存。 下面一張圖可以看出各級(jí)緩存之間的響應(yīng)時(shí)間差距，以及內(nèi)存到底有多慢！

什么是Cache Line

Cache Line可以簡(jiǎn)單的理解為CPU Cache中的最小緩存單位。目前主流的CPU Cache的Cache Line大小都是64Bytes。假設(shè)我們有一個(gè)512字節(jié)的一級(jí)緩存，那么按照64B的緩存單位大小來(lái)算，這個(gè)一級(jí)緩存所能存放的緩存?zhèn)€數(shù)就是512/64 = 8個(gè)。具體參見(jiàn)下圖：

為了更好的了解Cache Line，我們還可以在自己的電腦上做下面這個(gè)有趣的實(shí)驗(yàn)。

下面這段C代碼，會(huì)從命令行接收一個(gè)參數(shù)作為數(shù)組的大小創(chuàng)建一個(gè)數(shù)量為N的int數(shù)組。并依次循環(huán)的從這個(gè)數(shù)組中進(jìn)行數(shù)組內(nèi)容訪問(wèn)，循環(huán)10億次。最終輸出數(shù)組總大小和對(duì)應(yīng)總執(zhí)行時(shí)間。

#include "stdio.h" #include #include 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

如果我們把這些數(shù)據(jù)做成折線圖后就會(huì)發(fā)現(xiàn)：總執(zhí)行時(shí)間在數(shù)組大小超過(guò)64Bytes時(shí)有較為明顯的拐點(diǎn)（當(dāng)然，由于博主是在自己的Mac筆記本上測(cè)試的，會(huì)受到很多其他程序的干擾，因此會(huì)有波動(dòng)）。原因是當(dāng)數(shù)組小于64Bytes時(shí)數(shù)組極有可能落在一條Cache Line內(nèi)，而一個(gè)元素的訪問(wèn)就會(huì)使得整條Cache Line被填充，因而值得后面的若干個(gè)元素受益于緩存帶來(lái)的加速。而當(dāng)數(shù)組大于64Bytes時(shí)，必然至少需要兩條Cache Line，繼而在循環(huán)訪問(wèn)時(shí)會(huì)出現(xiàn)兩次Cache Line的填充，由于緩存填充的時(shí)間遠(yuǎn)高于數(shù)據(jù)訪問(wèn)的響應(yīng)時(shí)間，因此多一次緩存填充對(duì)于總執(zhí)行的影響會(huì)被放大，最終得到下圖的結(jié)果：

gcc cache_line_size.c -o cache_line_size編譯，并通過(guò)./cache_line_size執(zhí)行。

了解Cache Line的概念對(duì)我們程序猿有什么幫助？我們來(lái)看下面這個(gè)C語(yǔ)言中常用的循環(huán)優(yōu)化例子下面兩段代碼中，第一段代碼在C語(yǔ)言中總是比第二段代碼的執(zhí)行速度要快。具體的原因相信你仔細(xì)閱讀了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 是如何存放數(shù)據(jù)的

你會(huì)怎么設(shè)計(jì)Cache的存放規(guī)則

我們先來(lái)嘗試回答一下那么這個(gè)問(wèn)題：

假設(shè)我們有一塊4MB的區(qū)域用于緩存，每個(gè)緩存對(duì)象的唯一標(biāo)識(shí)是它所在的物理內(nèi)存地址。每個(gè)緩存對(duì)象大小是64Bytes，所有可以被緩存對(duì)象的大小總和（即物理內(nèi)存總大?。?a href="http://www.www27dydycom.cn/v/tag/9979/" target="_blank">4GB。那么我們?cè)撊绾卧O(shè)計(jì)這個(gè)緩存？

如果你和博主一樣是一個(gè)大學(xué)沒(méi)有好好學(xué)習(xí)基礎(chǔ)/數(shù)字電路的人的話，會(huì)覺(jué)得最靠譜的的一種方式就是：Hash表。把Cache設(shè)計(jì)成一個(gè)Hash數(shù)組。內(nèi)存地址的Hash值作為數(shù)組的Index，緩存對(duì)象的值作為數(shù)組的Value。每次存取時(shí)，都把地址做一次Hash然后找到Cache中對(duì)應(yīng)的位置操作即可。 這樣的設(shè)計(jì)方式在高等語(yǔ)言中很常見(jiàn)，也顯然很高效。因?yàn)镠ash值得計(jì)算雖然耗時(shí)(10000個(gè)CPU Cycle左右)，但是相比程序中其他操作（上百萬(wàn)的CPU Cycle）來(lái)說(shuō)可以忽略不計(jì)。而對(duì)于CPU Cache來(lái)說(shuō)，本來(lái)其設(shè)計(jì)目標(biāo)就是在幾十CPU Cycle內(nèi)獲取到數(shù)據(jù)。如果訪問(wèn)效率是百萬(wàn)Cycle這個(gè)等級(jí)的話，還不如到Memory直接獲取數(shù)據(jù)。當(dāng)然，更重要的原因是在硬件上要實(shí)現(xiàn)Memory Address Hash的功能在成本上是非常高的。

為什么Cache不能做成Fully Associative

Fully Associative 字面意思是全關(guān)聯(lián)。在CPU Cache中的含義是：如果在一個(gè)Cache集內(nèi)，任何一個(gè)內(nèi)存地址的數(shù)據(jù)可以被緩存在任何一個(gè)Cache Line里，那么我們成這個(gè)cache是Fully Associative。從定義中我們可以得出這樣的結(jié)論：給到一個(gè)內(nèi)存地址，要知道他是否存在于Cache中，需要遍歷所有Cache Line并比較緩存內(nèi)容的內(nèi)存地址。而Cache的本意就是為了在盡可能少得CPU Cycle內(nèi)取到數(shù)據(jù)。那么想要設(shè)計(jì)一個(gè)快速的Fully Associative的Cache幾乎是不可能的。

為什么Cache不能做成Direct Mapped

和Fully Associative完全相反，使用Direct Mapped模式的Cache給定一個(gè)內(nèi)存地址，就唯一確定了一條Cache Line。設(shè)計(jì)復(fù)雜度低且速度快。那么為什么Cache不使用這種模式呢？讓我們來(lái)想象這么一種情況：一個(gè)擁有1M L2 Cache的32位CPU，每條Cache Line的大小為64Bytes。那么整個(gè)L2Cache被劃為了1M/64=16384條Cache Line。我們?yōu)槊織lCache Line從0開(kāi)始編上號(hào)。同時(shí)32位CPU所能管理的內(nèi)存地址范圍是2^32=4G，那么Direct Mapped模式下，內(nèi)存也被劃為4G/16384=256K的小份。也就是說(shuō)每256K的內(nèi)存地址共享一條Cache Line。但是，這種模式下每條Cache Line的使用率如果要做到接近100%，就需要操作系統(tǒng)對(duì)于內(nèi)存的分配和訪問(wèn)在地址上也是近乎平均的。而與我們的意愿相反，為了減少內(nèi)存碎片和實(shí)現(xiàn)便捷，操作系統(tǒng)更多的是連續(xù)集中的使用內(nèi)存。這樣會(huì)出現(xiàn)的情況就是0-1000號(hào)這樣的低編號(hào)Cache Line由于內(nèi)存經(jīng)常被分配并使用，而16000號(hào)以上的Cache Line由于內(nèi)存鮮有進(jìn)程訪問(wèn)，幾乎一直處于空閑狀態(tài)。這種情況下，本來(lái)就寶貴的1M二級(jí)CPU緩存，使用率也許50%都無(wú)法達(dá)到。

什么是N-Way Set Associative

為了避免以上兩種設(shè)計(jì)模式的缺陷，N-Way Set Associative緩存就出現(xiàn)了。他的原理是把一個(gè)緩存按照N個(gè)Cache Line作為一組（set），緩存按組劃為等分。這樣一個(gè)64位系統(tǒng)的內(nèi)存地址在4MB二級(jí)緩存中就劃成了三個(gè)部分（見(jiàn)下圖），低位6個(gè)bit表示在Cache Line中的偏移量，中間12bit表示Cache組號(hào)（set index），剩余的高位46bit就是內(nèi)存地址的唯一id。這樣的設(shè)計(jì)相較前兩種設(shè)計(jì)有以下兩點(diǎn)好處：

給定一個(gè)內(nèi)存地址可以唯一對(duì)應(yīng)一個(gè)set，對(duì)于set中只需遍歷16個(gè)元素就可以確定對(duì)象是否在緩存中（Full Associative中比較次數(shù)隨內(nèi)存大小線性增加）

每2^18(256K)*16(way)=4M的連續(xù)熱點(diǎn)數(shù)據(jù)才會(huì)導(dǎo)致一個(gè)set內(nèi)的conflict（Direct Mapped中512K的連續(xù)熱點(diǎn)數(shù)據(jù)就會(huì)出現(xiàn)conflict）

什么N-Way Set Associative的Set段是從低位而不是高位開(kāi)始的

下面是一段從How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses摘錄的解釋?zhuān)?/p>

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.

由于內(nèi)存的訪問(wèn)通常是大片連續(xù)的，或者是因?yàn)樵谕怀绦蛑卸鴮?dǎo)致地址接近的（即這些內(nèi)存地址的高位都是一樣的）。所以如果把內(nèi)存地址的高位作為set index的話，那么短時(shí)間的大量?jī)?nèi)存訪問(wèn)都會(huì)因?yàn)閟et index相同而落在同一個(gè)set index中，從而導(dǎo)致cache conflicts使得L2, L3 Cache的命中率低下，影響程序的整體執(zhí)行效率。

了解N-Way Set Associative的存儲(chǔ)模式對(duì)我們有什么幫助

了解N-Way Set的概念后，我們不難得出以下結(jié)論：2^(6Bits + 12Bits )=2^18=256K。即在連續(xù)的內(nèi)存地址中每256K都會(huì)出現(xiàn)一個(gè)處于同一個(gè)Cache Set中的緩存對(duì)象。也就是說(shuō)這些對(duì)象都會(huì)爭(zhēng)搶一個(gè)僅有16個(gè)空位的緩存池（16-Way Set）。而如果我們?cè)诔绦蛑杏质褂昧怂^優(yōu)化神器的“內(nèi)存對(duì)齊”的時(shí)候，這種爭(zhēng)搶就會(huì)越發(fā)增多。效率上的損失也會(huì)變得非常明顯。具體的實(shí)際測(cè)試我們可以參考：How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses一文。 這里我們引用一張Gallery of Processor Cache Effects中的測(cè)試結(jié)果圖，來(lái)解釋下內(nèi)存對(duì)齊在極端情況下帶來(lái)的性能損失。

該圖實(shí)際上是我們上文中第一個(gè)測(cè)試的一個(gè)變種。縱軸表示了測(cè)試對(duì)象數(shù)組的大小。橫軸表示了每次數(shù)組元素訪問(wèn)之間的index間隔。而圖中的顏色表示了響應(yīng)時(shí)間的長(zhǎng)短，藍(lán)色越明顯的部分表示響應(yīng)時(shí)間越長(zhǎng)。從這個(gè)圖我們可以得到很多結(jié)論。當(dāng)然這里我們只對(duì)內(nèi)存帶來(lái)的性能損失感興趣。有興趣的讀者也可以閱讀原文分析理解其他從圖中可以得到的結(jié)論。

從圖中我們不難看出圖中每1024個(gè)步進(jìn)，即每1024*4即4096Bytes，都有一條特別明顯的藍(lán)色豎線。也就是說(shuō)，只要我們按照4K的步進(jìn)去訪問(wèn)內(nèi)存(內(nèi)存根據(jù)4K對(duì)齊），無(wú)論熱點(diǎn)數(shù)據(jù)多大它的實(shí)際效率都是非常低的！按照我們上文的分析，如果4KB的內(nèi)存對(duì)齊，那么一個(gè)240MB的數(shù)組就含有61440個(gè)可以被訪問(wèn)到的數(shù)組元素；而對(duì)于一個(gè)每256K就會(huì)有set沖突的16Way二級(jí)緩存，總共有256K/4K=64個(gè)元素要去爭(zhēng)搶16個(gè)空位，總共有61440/64=960個(gè)這樣的元素。那么緩存命中率只有1%，自然效率也就低了。

Cache淘汰策略

在文章的最后我們順帶提一下CPU Cache的淘汰策略。常見(jiàn)的淘汰策略主要有LRU和Random兩種。通常意義下LRU對(duì)于Cache的命中率會(huì)比Random更好，所以CPU Cache的淘汰策略選擇的是LRU。當(dāng)然也有些實(shí)驗(yàn)顯示在Cache Size較大的時(shí)候Random策略會(huì)有更高的命中率

總結(jié)

CPU Cache對(duì)于程序猿是透明的，所有的操作和策略都在CPU內(nèi)部完成。但是，了解和理解CPU Cache的設(shè)計(jì)、工作原理有利于我們更好的利用CPU Cache，寫(xiě)出更多對(duì)CPU Cache友好的程序。