根據(jù)上文講解的程序的局部性原理，如果一個(gè)數(shù)據(jù)被CPU訪問(wèn)了，那么這個(gè)數(shù)據(jù)相鄰的其他數(shù)據(jù)也很快會(huì)被訪問(wèn)到。因此，為了提高內(nèi)存數(shù)據(jù)的讀取效率，并且最大化利用CPU資源，數(shù)據(jù)在Cache和內(nèi)存之間傳輸時(shí)，不是一個(gè)字節(jié)一個(gè)字節(jié)進(jìn)行傳輸?shù)?，而是以緩存?Cache Line)為單位進(jìn)行傳輸?shù)摹?/p>

不同CPU的Cache line大小可能不同，典型的CPU Cache line大小是64個(gè)字節(jié)。

我們通過(guò)下面一個(gè)簡(jiǎn)單的例子，加深一下理解。

Cache Line 實(shí)例講解

在一個(gè)Cache Line大小為64字節(jié)的機(jī)器上，定義個(gè)數(shù)組：

int a[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};

我們假設(shè)數(shù)組a的起始地址是Cache Line對(duì)齊的，可以簡(jiǎn)單理解為a的地址能被64整除。假設(shè)，數(shù)組a還從來(lái)沒(méi)有被訪問(wèn)過(guò)，如果此時(shí)需要訪問(wèn)a中的一個(gè)元素a[5]，如：

int x = a[5];

由于在此之前數(shù)組a沒(méi)有被訪問(wèn)過(guò)，所以理論上講，數(shù)組a應(yīng)該只存在于內(nèi)存中，并未被加載到Cache中。因此，此時(shí)CPU在Cache中找不到a[5]，觸發(fā)Cache Miss，然后需要從內(nèi)存中讀取數(shù)據(jù)，并更加載到Cache中。前面提到，Cache和內(nèi)存之間是以Cache Line為單位進(jìn)行數(shù)據(jù)傳輸?shù)?，因此，這里會(huì)把一個(gè)Cache line大小（64字節(jié)）的數(shù)據(jù)從內(nèi)存讀取出來(lái)加載到Cache中。由于a的起始地址恰巧是Cache line對(duì)齊的，所以CPU會(huì)把整個(gè)數(shù)組（64個(gè)字節(jié)，剛好一個(gè)Cache Line）都加載到Cache中。

緊接著，如果再訪問(wèn)數(shù)組a的元素，如：

int y = a[10];

此時(shí)，整個(gè)數(shù)組都在Cache中，所以CPU在訪問(wèn)時(shí)，觸發(fā)Cache Hit，直接從Cache讀取數(shù)據(jù)即可，不需要再?gòu)膬?nèi)存中讀取。

了解了Cache的背景知識(shí)，現(xiàn)在來(lái)分析下array1.c和array2.c為什么會(huì)存在這么巨大的性能差異。

按行、列訪問(wèn)的真正差異 - Cache

首先，必須要知道一點(diǎn)：C語(yǔ)言的數(shù)組，所有元素是存放在地址連續(xù)的內(nèi)存中的，此外，C語(yǔ)言的多維數(shù)組，是按行進(jìn)行存儲(chǔ)的。

array1.c按行對(duì)數(shù)組進(jìn)行訪問(wèn)，也就是從數(shù)組起始地址開(kāi)始，一直連續(xù)訪問(wèn)到數(shù)組的最后一個(gè)元素的地址處。第一次訪問(wèn)一個(gè)Cache Line的首個(gè)元素時(shí)，觸發(fā)Cache Miss，與該元素臨近的幾個(gè)元素會(huì)組成一個(gè)Cache Line，被一起加載到Cache中。如此，在訪問(wèn)下一個(gè)元素的時(shí)候，就會(huì)Cache Hit，直接從Cache讀取數(shù)據(jù)即可。

而array2.c按列對(duì)數(shù)組進(jìn)行訪問(wèn)，因此并不是按照連續(xù)地址進(jìn)行訪問(wèn)的，而是每次間隔10240 * 4個(gè)字節(jié)進(jìn)行訪問(wèn)。第一次訪問(wèn)一個(gè)Cache Line的首個(gè)元素時(shí)，假設(shè)地址為x，盡管該元素臨近的一個(gè)Cache Line大小的元素也會(huì)被一起加載進(jìn)Cache中，但是程序接下來(lái)訪問(wèn)的并不是臨近的元素，而是地址為x + 10240 * 4處的元素，因此會(huì)再次觸發(fā)Cache Miss。而當(dāng)程序回過(guò)頭來(lái)訪問(wèn)x + 4地址處的元素時(shí)，這個(gè)Cache Line可能已經(jīng)被其他數(shù)據(jù)沖刷掉了。因?yàn)?，盡管Cache會(huì)盡量緩存最近訪問(wèn)過(guò)的數(shù)據(jù)，但畢竟大小有限，當(dāng)Cache被占滿時(shí)，一些舊的數(shù)據(jù)就會(huì)被沖刷替換掉。

可以看出，無(wú)論是時(shí)間局部性還是空間局部性，array1.c都要比array2.c好很多！相比array1.c，array2.c會(huì)觸發(fā)大量的Cache Miss，這也是為什么array2的性能會(huì)如此之差！

下面我們用perf來(lái)對(duì)比下這兩個(gè)程序的性能指標(biāo)。

用perf觀測(cè)性能指標(biāo)

perf是Linux提供的一個(gè)功能強(qiáng)大的實(shí)用性能調(diào)優(yōu)工具，它可以用來(lái)觀測(cè)幾乎所有CPU相關(guān)的性能指標(biāo)，但perf工具本身，不是本文重點(diǎn)，以后會(huì)有專(zhuān)門(mén)文章詳細(xì)介紹perf的使用。

先獲取array1.c的性能指標(biāo)：

再看下array2.c的性能指標(biāo)：

這里，我們只關(guān)注一個(gè)最重要的性能指標(biāo)：L1 Data Cache的Miss率。

對(duì)比一下，array1.c的L1-dcache-load-misses率只有3.10%， 而按列訪問(wèn)的array2.c，則達(dá)到了驚人的93.03%！這就是兩者性能差異如此巨大的真相！

小結(jié)

Cache是CPU內(nèi)部最為重要的部件之一，也是影響程序性能的最重要因素之一，但由于各種原因，經(jīng)常被程序員忽視。在進(jìn)行性能調(diào)優(yōu)時(shí)，除了系統(tǒng)架構(gòu)、算法等方面的考量之外，不妨也從CPU的角度去思考一下，比如Cache，有時(shí)會(huì)對(duì)程序性能產(chǎn)生決定性影響。