兩個簡單的測試程序

定義一個同樣大小的二維數組，然后循環遍歷，對數組元素賦值。

• • array1.c 對數組按行進行訪問

• • array2.c 對數組按列進行訪問

編譯運行，并用time命令統計一下運行時間：

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

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

重要說明

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

存儲金字塔

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

這張圖很直觀地描述了現代計算機系統的分級存儲模型。

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

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

那么，這種金字塔式結構中，不同層級的存儲設備之間究竟是如何協調工作的呢？

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

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

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

局部性原理

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

• • 時間局部性。如果一個數據在某個時間點被CPU訪問了，那么在接下來很短的一段時間內，這個數據很有可能會再次被CPU訪問到。

• • 空間局部性。如果一個數據在某個時間點被CPU訪問了，那么與這個數據臨近的其他數據，很有可能也會很快被CPU訪問到。

高速緩存 - Cache

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

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

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

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

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

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

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

Cache Line

Cache Line 是 Cache和內存之間進行數據傳輸的最小單位。

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

不同CPU的Cache line大小可能不同，典型的CPU Cache line大小是64個字節。

我們通過下面一個簡單的例子，加深一下理解。

Cache Line 實例講解

在一個Cache Line大小為64字節的機器上，定義個數組：

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

我們假設數組a的起始地址是Cache Line對齊的，可以簡單理解為a的地址能被64整除。假設，數組a還從來沒有被訪問過，如果此時需要訪問a中的一個元素a[5]，如：

int x = a[5];

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

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

int y = a[10];

此時，整個數組都在Cache中，所以CPU在訪問時，觸發Cache Hit，直接從Cache讀取數據即可，不需要再從內存中讀取。

了解了Cache的背景知識，現在來分析下array1.c和array2.c為什么會存在這么巨大的性能差異。

按行、列訪問的真正差異 - Cache

首先，必須要知道一點：C語言的數組，所有元素是存放在地址連續的內存中的，此外，C語言的多維數組，是按行進行存儲的。

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

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

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

下面我們用perf來對比下這兩個程序的性能指標。

用perf觀測性能指標

perf是Linux提供的一個功能強大的實用性能調優工具，它可以用來觀測幾乎所有CPU相關的性能指標，但perf工具本身，不是本文重點，以后會有專門文章詳細介紹perf的使用。

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

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

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

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

小結

Cache是CPU內部最為重要的部件之一，也是影響程序性能的最重要因素之一，但由于各種原因，經常被程序員忽視。在進行性能調優時，除了系統架構、算法等方面的考量之外，不妨也從CPU的角度去思考一下，比如Cache，有時會對程序性能產生決定性影響。