兩個簡單的測試程序

定義一個同樣大小的二維數(shù)組，然后循環(huán)遍歷，對數(shù)組元素賦值。

• array1.c 對數(shù)組按行進行訪問

• array2.c 對數(shù)組按列進行訪問

編譯運行，并用time命令統(tǒng)計一下運行時間：

array1用時0.528秒，array2用時10.310秒。array2耗時居然是array1的將近20倍！

有沒有被這個結(jié)果震驚到？為什么會有如此之大的性能差異呢？

重要說明

要想真正理解這個問題，必須要先補充一些關(guān)于現(xiàn)代計算機存儲系統(tǒng)相關(guān)的背景知識，這也是理解這個問題的關(guān)鍵所在。為方便大家理解，我會盡量以白話的形式進行講解，盡可能避免枯燥無味的純理論描述。

存儲金字塔

相信不少人都聽過“存儲金字塔”這個詞，或者至少見過類似下面這張圖：

這張圖很直觀地描述了現(xiàn)代計算機系統(tǒng)的分級存儲模型。

可以認為CPU就位于金字塔的頂點上，越靠近塔頂，離CPU越近，訪問速度越快，但生產(chǎn)成本越高，相應(yīng)的容量也就越小。在所有存儲器中，寄存器直接內(nèi)嵌在CPU中，訪問速度最快，容量也最小，一般CPU上也就最多幾十個通用寄存器供應(yīng)用程序使用。

反之，越往下靠近塔底，訪問速度越慢，生產(chǎn)成本越低，相應(yīng)的容量也就越大。比如圖中最底部的網(wǎng)絡(luò)存儲設(shè)備，相對其他存儲設(shè)備而言是訪問速度最慢的，但其容量卻幾乎可以認為是無限制的。

那么，這種金字塔式結(jié)構(gòu)中，不同層級的存儲設(shè)備之間究竟是如何協(xié)調(diào)工作的呢？

用一句話概括：高一級的存儲設(shè)備，往往是作為低一級存儲設(shè)備的緩存來使用的。

簡單來說，系統(tǒng)運行時，為了提升數(shù)據(jù)訪問效率，把程序中最近最經(jīng)常訪問的數(shù)據(jù)，盡可能放到訪問速度更快的高一級存儲器中。這樣一來，每次訪問數(shù)據(jù)時，從金字塔的頂端開始，都先嘗試在高一級存儲器中查找，如果被訪問的數(shù)據(jù)存在且有效，則直接訪問，否則，就逐級到更低級的存儲器中去查找。

這種金字塔式的分級存儲模型之所以能夠以近乎完美的方式運行，實際上都是建立在現(xiàn)代計算機科學中的一個非常重要的理論基礎(chǔ)之上：程序的局部性原理。

局部性原理

一個程序的局部性，包含兩個維度：時間局部性和空間局部性。

• 時間局部性。如果一個數(shù)據(jù)在某個時間點被CPU訪問了，那么在接下來很短的一段時間內(nèi)，這個數(shù)據(jù)很有可能會再次被CPU訪問到。
• 空間局部性。如果一個數(shù)據(jù)在某個時間點被CPU訪問了，那么與這個數(shù)據(jù)臨近的其他數(shù)據(jù)，很有可能也會很快被CPU訪問到。

高速緩存 - Cache

根據(jù)常識，我們知道，程序要想被CPU正常執(zhí)行，必須要先被加載到內(nèi)存中。（當然也有例外，有童鞋知道哪些程序不是在內(nèi)存中運行的嗎？歡迎添加作者微信CreCoding討論?。?/p>

但是，內(nèi)存的訪問速度與CPU運行速度相比，要慢好幾個數(shù)量級，可以想象一下，如果CPU每次都直接從內(nèi)存中存取數(shù)據(jù)，會造成大量的計算資源浪費，程序性能嚴重受損，假如真是這樣的話，你還能像現(xiàn)在這樣愉快的吃雞嗎？

為了解決CPU和內(nèi)存之間速度嚴重不匹配的問題，在CPU和內(nèi)存之間設(shè)計了高速緩存，即Cache。

目前，主流CPU一般都有三級（或更多級）的Cache，依次是L1 Cache、L2 Cache、L3 Cache。其中L1 Cache速度最快，幾乎可以和內(nèi)嵌在CPU中的寄存器媲美，容量也最小，而L3 Cache速度最慢（但仍然比內(nèi)存快很多），但容量最大。

CPU讀取數(shù)據(jù)時，會在L1、L2、L3Cache中逐級查找，如果找到，就從Cache直接讀取，找不到再從內(nèi)存讀取，并且把數(shù)據(jù)存放到Cache中，以便提高下次訪問的效率。

在這個過程中，如果在Cache中找到所需數(shù)據(jù)，稱為Cache命中(Cache Hit), 找不到稱為Cache未命中(Cache Miss)。

不難看出，L1 Cache命中的時候，讀取數(shù)據(jù)最快，性能最好，而當L1、L2、L3 Cache全部未命中時，就必須要直接從內(nèi)存中讀取數(shù)據(jù)，性能最差！

Cache Line

Cache Line 是 Cache和內(nèi)存之間進行數(shù)據(jù)傳輸?shù)淖钚挝弧?/strong>

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

我們通過下面一個簡單的例子，加深一下理解。
Cache Line 實例講解
在一個Cache Line大小為64字節(jié)的機器上，定義個數(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對齊的，可以簡單理解為a的地址能被64整除。假設(shè)，數(shù)組a還從來沒有被訪問過，如果此時需要訪問a中的一個元素a[5]，如：

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

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

int y = a[10];
此時，整個數(shù)組都在Cache中，所以CPU在訪問時，觸發(fā)Cache Hit，直接從Cache讀取數(shù)據(jù)即可，不需要再從內(nèi)存中讀取。

了解了Cache的背景知識，現(xiàn)在來分析下array1.c和array2.c為什么會存在這么巨大的性能差異。
按行、列訪問的真正差異 - Cache
首先，必須要知道一點：C語言的數(shù)組，所有元素是存放在地址連續(xù)的內(nèi)存中的，此外，C語言的多維數(shù)組，是按行進行存儲的。

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

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

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

下面我們用perf來對比下這兩個程序的性能指標。
用perf觀測性能指標
perf是Linux提供的一個功能強大的實用性能調(diào)優(yōu)工具，它可以用來觀測幾乎所有CPU相關(guān)的性能指標，但perf工具本身，不是本文重點，以后會有專門文章詳細介紹perf的使用。

先獲取array1.c的性能指標：

再看下array2.c的性能指標：

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

對比一下，array1.c的L1-dcache-load-misses率只有3.10%，而按列訪問的array2.c，則達到了驚人的93.03%！這就是兩者性能差異如此巨大的真相！
小結(jié)
Cache是CPU內(nèi)部最為重要的部件之一，也是影響程序性能的最重要因素之一，但由于各種原因，經(jīng)常被程序員忽視。在進行性能調(diào)優(yōu)時，除了系統(tǒng)架構(gòu)、算法等方面的考量之外，不妨也從CPU的角度去思考一下，比如Cache，有時會對程序性能產(chǎn)生決定性影響。

該文章在 2023/10/30 9:23:16 編輯過