CPU高速緩存集成于CPU的內(nèi)部，其是CPU可以高效運(yùn)行的成分之一，本文圍繞下面三個(gè)話題來(lái)講解CPU緩存的作用：

• 為什么需要高速緩存？

• 高速緩存的內(nèi)部結(jié)構(gòu)是怎樣的？

• 如何利用好cache，優(yōu)化代碼執(zhí)行效率？

為什么需要高速緩存？

在現(xiàn)代計(jì)算機(jī)的體系架構(gòu)中，為了存儲(chǔ)數(shù)據(jù)，引入了下面一些元件

• 1.CPU寄存器

• 2.CPU高速緩存

• 3.內(nèi)存

• 4.硬盤

從1->4,速度越來(lái)越慢，價(jià)格越來(lái)越低，容量越來(lái)越大。這樣的設(shè)計(jì)使得一臺(tái)計(jì)算機(jī)的價(jià)格會(huì)處于一個(gè)合理的區(qū)間，使得計(jì)算機(jī)可以走進(jìn)千家萬(wàn)戶。

由于硬盤的速度比內(nèi)存訪問(wèn)慢，因此我們?cè)陂_發(fā)應(yīng)用軟件時(shí)，經(jīng)常會(huì)使用redis/memcached這樣的組件來(lái)加快速度。

而由于CPU和內(nèi)存速度的不同，于是產(chǎn)生了CPU高速緩存。

下面這張表反應(yīng)了CPU高速緩存和內(nèi)存的速度差距。

通常cpu內(nèi)有3級(jí)緩存，即L1、L2、L3緩存。其中L1緩存分為數(shù)據(jù)緩存和指令緩存，cpu先從L1緩存中獲取指令和數(shù)據(jù)，如果L1緩存中不存在，那就從L2緩存中獲取。每個(gè)cpu核心都擁有屬于自己的L1緩存和L2緩存。如果數(shù)據(jù)不在L2緩存中，那就從L3緩存中獲取。而L3緩存就是所有cpu核心共用的。如果數(shù)據(jù)也不在L3緩存中，那就從內(nèi)存中獲取了。當(dāng)然，如果內(nèi)存中也沒(méi)有那就只能從硬盤中獲取了。

對(duì)這樣的分層概念有了了解之后，就可以進(jìn)一步的了解高速緩存的內(nèi)部細(xì)節(jié)。

高速緩存的內(nèi)部結(jié)構(gòu)

CPU Cache 在讀取內(nèi)存數(shù)據(jù)時(shí)，每次不會(huì)只讀一個(gè)字或一個(gè)字節(jié)，而是一塊塊地讀取，這每一小塊數(shù)據(jù)也叫CPU 緩存行（CPU Cache Line）。這也是對(duì)局部性原理的運(yùn)用，當(dāng)一個(gè)指令或數(shù)據(jù)被拜訪過(guò)之后，與它相鄰地址的數(shù)據(jù)有很大概率也會(huì)被拜訪，將更多或許被拜訪的數(shù)據(jù)存入緩存，可以進(jìn)步緩存命中率。

cache line 又分為多種類型，分別為直接映射緩存，多路組相連緩存，全相連緩存。

下面依次介紹。

直接映射緩存

直接映射緩存會(huì)將一個(gè)內(nèi)存地址固定映射到某一行的cache line。

其思想是將一個(gè)內(nèi)存地址劃分為三塊，分別是Tag, Index，Offset(這里的內(nèi)存地址指的是虛擬內(nèi)存)。將cacheline理解為一個(gè)數(shù)組，那么通過(guò)Index則是數(shù)組的下標(biāo)，通過(guò)Index就可以獲取對(duì)應(yīng)的cache-line。再獲取cache-line的數(shù)據(jù)后，獲取其中的Tag值，將其與地址中的Tag值進(jìn)行對(duì)比，如果相同，則代表該內(nèi)存地址位于該cache line中，即cache命中了。最后根據(jù)Offset的值去data數(shù)組中獲取對(duì)應(yīng)的數(shù)據(jù)。整個(gè)流程大概如下圖所示：

下面是一個(gè)例子，假設(shè)cache中有8個(gè)cache line，

對(duì)于直接映射緩存而言，其內(nèi)存和緩存的映射關(guān)系如下所示：

從圖中我們可以看出，0x00,0x40,0x80這三個(gè)地址，其地址中的index成分的值是相同的，因此將會(huì)被加載進(jìn)同一個(gè)cache line。

試想一下如果我們依次訪問(wèn)了0x00，0x40，0x00會(huì)發(fā)生什么？

當(dāng)我們?cè)L問(wèn)0x00時(shí)，cache miss，于是從內(nèi)存中加載到第0行cache line中。當(dāng)訪問(wèn)0x40時(shí)，第0行cache line中的tag與地址中的tag成分不一致，因此又需要再次從內(nèi)存中加載數(shù)據(jù)到第0行cache line中。最后再次訪問(wèn)0x00時(shí)，由于cache line中存放的是0x40地址的數(shù)據(jù)，因此cache再次miss?？梢钥闯鲈谶@個(gè)過(guò)程中，cache并沒(méi)有起什么作用，訪問(wèn)了相同的內(nèi)存地址時(shí)，cache line并沒(méi)有對(duì)應(yīng)的內(nèi)容，而都是從內(nèi)存中進(jìn)行加載。

這種現(xiàn)象叫做cache顛簸（cache thrashing）。針對(duì)這個(gè)問(wèn)題，引入多路組相連緩存。下面一節(jié)將講解多路組相連緩存的工作原理。

多路組相連緩存

多路組相連緩存的原理相比于直接映射緩存復(fù)雜一些，這里將以兩路組相連這種場(chǎng)景來(lái)進(jìn)行講解。

所謂多路就是指原來(lái)根據(jù)虛擬的地址中的index可以唯一確定一個(gè)cache line，而現(xiàn)在根據(jù)index可以找到多行cache line。而兩路的意思就是指通過(guò)index可以找到2個(gè)cache line。在找到這個(gè)兩個(gè)cache line后，遍歷這兩個(gè)cache line，比較其中的tag值，如果相等則代表命中了。

下面還是以8個(gè)cache line的兩路緩存為例，假設(shè)現(xiàn)在有一個(gè)虛擬地址是0000001100101100,其tag值為0x19，其index為1，offset為4。那么根據(jù)index為1可以找到兩個(gè)cache line，由于第一個(gè)cache line的tag為0x10,因此沒(méi)有命中，而第二個(gè)cache line的tag為0x19，值相等，于是cache命中。

對(duì)于多路組相連緩存而言，其內(nèi)存和緩存的映射關(guān)系如下所示：

由于多路組相連的緩存需要進(jìn)行多次tag的比較，對(duì)于比直接映射緩存,其硬件成本更高，因?yàn)闉榱颂岣咝?，可能?huì)需要進(jìn)行并行比較，這就需要更復(fù)雜的硬件設(shè)計(jì)。

另外，如何cache沒(méi)有命中，那么該如何處理呢？

以兩路為例，通過(guò)index可以找到兩個(gè)cache line，如果此時(shí)這兩個(gè)cache line都是處于空閑狀態(tài)，那么cache miss時(shí)可以選擇其中一個(gè)cache line加載數(shù)據(jù)。如果兩個(gè)cache line有一個(gè)處于空閑狀態(tài)，可以選擇空閑狀態(tài)的cache line 加載數(shù)據(jù)。如果兩個(gè)cache line都是有效的，那么則需要一定的淘汰算法，例如PLRU/NRU/fifo/round-robin等等。

這個(gè)時(shí)候如果我們依次訪問(wèn)了0x00，0x40，0x00會(huì)發(fā)生什么？

當(dāng)我們?cè)L問(wèn)0x00時(shí)，cache miss，于是從內(nèi)存中加載到第0路的第0行cache line中。當(dāng)訪問(wèn)0x40時(shí)，第0路第0行cache line中的tag與地址中的tag成分不一致，于是從內(nèi)存中加載數(shù)據(jù)到第1路第0行cache line中。最后再次訪問(wèn)0x00時(shí)，此時(shí)會(huì)訪問(wèn)到第0路第0行的cache line中，因此cache就生效了。由此可以看出，由于多路組相連的緩存可以改善cache顛簸的問(wèn)題。

全相連緩存

從多路組相連，我們了解到其可以降低cache顛簸的問(wèn)題，并且路數(shù)量越多，降低cache顛簸的效果就越好。那么是不是可以這樣設(shè)想，如果路數(shù)無(wú)限大，大到所有的cache line都在一個(gè)組內(nèi)，是不是效果就最好？基于這樣的思想，全相連緩存相應(yīng)而生。

下面還是以8個(gè)cache line的全相連緩存為例，假設(shè)現(xiàn)在有一個(gè)虛擬地址是0000001100101100,其tag值為0x19，offset為4。依次遍歷，直到遍歷到第4行cache line時(shí)，tag匹配上。

全連接緩存中所有的cache line都位于一個(gè)組(set)內(nèi)，因此地址中將不會(huì)劃出一部分作為index。在判斷cache line是否命中時(shí)，需要遍歷所有的cache line，將其與虛擬地址中的tag成分進(jìn)行對(duì)比，如果相等，則意味著匹配上了。因此對(duì)于全連接緩存而言，任意地址的數(shù)據(jù)可以緩存在任意的cache line中，這可以避免緩存的顛簸，但是與此同時(shí)，硬件上的成本也是最高。

如何利用緩存寫出高效率的代碼？

看下面這個(gè)例子，對(duì)一個(gè)二維數(shù)組求和時(shí)，可以進(jìn)行按行遍歷和按列遍歷，那么哪一種速度會(huì)比較快呢？

const int row = 1024;
const int col = 1024;
int matrix[row][col];

//按行遍歷
int sum_row = 0;
for (int r = 0; r < row; r++) {
    for (int c = 0; c < col; c++) {
        sum_row += matrix[r][c];
    }
}

//按列遍歷
int sum_col = 0;
for (int c = 0; c < col; c++) {
    for (int r = 0; r < row; r++) {
        sum_col += matrix[r][c];
    }
}

我們分別編寫下面的測(cè)試代碼，首先是按行遍歷的時(shí)間：

#include 
#include 
const int row = 1024;
const int col = 1024;
int matrix[row][col];

//按行遍歷
int main(){
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            matrix[r][c] = r+c;
        }
    }
    auto start = std::now();
    
    //按行遍歷
    int sum_row = 0;
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            sum_row += matrix[r][c];
        }
    }

    auto finish = std::now();
    auto duration = std::duration_cast<std::milliseconds>(finish - start);
    std::cout << duration.count() << "ms" << std::endl;
}

標(biāo)準(zhǔn)輸出打印了：2ms

接著是按列遍歷的測(cè)試代碼：

#include 
#include 
const int row = 1024;
const int col = 1024;
int matrix[row][col];

//按行遍歷
int main(){
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            matrix[r][c] = r+c;
        }
    }
    auto start = std::now();
    
    //按列遍歷
    int sum_col = 0;
    for (int c = 0; c < col; c++) {
        for (int r = 0; r < row; r++) {
            sum_col += matrix[r][c];
        }
    }

    auto finish = std::now();
    auto duration = std::duration_cast<std::milliseconds>(finish - start);
    std::cout << duration.count() << "ms" << std::endl;
}

標(biāo)準(zhǔn)輸出打印了：8ms

答案很明顯了，按行遍歷速度比按列遍歷快很多。

原因就是按行遍歷時(shí)， 在訪問(wèn)matrix[r][c]時(shí)，會(huì)將后面的一些元素一并加載到cache line中，那么后面訪問(wèn)matrix[r][c+1]和matrix[r][c+2]時(shí)就可以命中緩存，這樣就可以極大的提高緩存訪問(wèn)的速度。

如下圖所示，在訪問(wèn)matrix[0][0]時(shí)，matrix[0][1]，matrix[0][2]，matrix[0][2]也被加載進(jìn)了高速緩存中，因此隨后遍歷時(shí)就可以用到緩存。

而按列遍歷時(shí)，訪問(wèn)完matrix[0][0]之后，下一個(gè)要訪問(wèn)的數(shù)據(jù)是matrix[1][0]，不在高速緩存中，于是需要再次訪問(wèn)內(nèi)存，這就使得程序的訪問(wèn)速度相較于按行緩存會(huì)慢很多。