引言

軟件開發人員往往期望計算機硬件擁有無限容量、零訪問延遲、無限帶寬以及便宜的內存，但是現實卻是內存容量越大，相應的訪問時間越長；內存訪問速度越快，價格也更貴；帶寬越大，價格越貴。為了解決大容量、高速度、低成本之間的矛盾，基于程序訪問的局部性原理，將更常用數據放在小容量的高速存儲器中，多種速度不同的存儲器分層級聯，協調工作。

圖1 memory hierarchy for sever[1]

現代計算機的存儲層次可以分幾層。如圖1所示，位于處理器內部的是寄存器；稍遠一點的是一級Cache，一級Cache一般能夠保存64k字節，訪問它大約需要1ns，同時一級Cache通常劃分為指令Cache（處理器從指令Cache中取要執行的指令）和數據Cache（處理器從數據Cache中存/取指令的操作數）；然后是二級Cache，通常既保存指令又保存數據，容量大約256k，訪問它大約需要3-10ns；然后是三級Cache，容量大約16-64MB，訪問它大約需要10-20ns；再接著是主存、硬盤等。注意，CPU和Cache是以word傳輸的，Cache到主存以塊（一般64byte）傳輸的。

前文提到了程序的局部性原理，一般指的是時間局部性（在一定時間內，程序可能會多次訪問同一內存空間）和空間局部性（在一定時間內，程序可能會訪問附近的內存空間），高速緩存（Cache）的效率取決于程序的空間和時間的局部性性質。比如一個程序重復地執行一個循環，在理想情況下，循環的第一個迭代將代碼取至高速緩存中，后續的迭代直接從高速緩存中取數據，而不需要重新從主存裝載。因此，為了使程序獲得更好的性能，應盡可能讓數據訪問發生在高速緩存中。但是如果數據訪問在高速緩存時發生了沖突，也可能會導致性能下降。

篇幅原因，本文重點討論編譯器在Cache優化中可以做哪些工作，如果讀者對其他內存層次優化感興趣，歡迎留言。下面將介紹幾種通過優化Cache使用提高程序性能的方法。

對齊和布局

現代編譯器可以通過調整代碼和數據的布局方式，提高Cache命中率，進而提升程序性能。本節主要討論數據和指令的對齊、代碼布局對程序性能的影響，大部分處理器中Cache到主存是以Cache line（一般為64Byte，也有地方稱Cache塊，本文統一使用Cache line）傳輸的，CPU從內存加載數據是一次一個Cache line，CPU往內存寫數據也是一次一個Cache line。假設處理器首次訪問數據對象A，其大小剛好為64Byte，如果數據對象A首地址并沒有進行對齊，即數據對象A占用兩個不同Cache line的一部分，此時處理器訪問該數據對象時需要兩次內存訪問，效率低。但是如果數據對象A進行了內存對齊，即剛好在一個Cache line中，那么處理器訪問該數據時只需要一次內存訪問，效率會高很多。編譯器可以通過合理安排數據對象，避免不必要地將它們跨越在多個Cache line中，盡量使得同一對象集中在一個Cache中，進而有效地使用Cache來提高程序的性能。通過順序分配對象，即如果下一個對象不能放入當前Cache line的剩余部分，則跳過這些剩余的部分，從下一個Cache line的開始處分配對象，或者將大小（size）相同的對象分配在同一個存儲區，所有對象都對齊在size的倍數邊界上等方式達到上述目的。

Cache line對齊可能會導致存儲資源的浪費，如圖2所示，但是執行速度可能會因此得到改善。對齊不僅僅可以作用于全局靜態數據，也可以作用于堆上分配的數據。對于全局數據，編譯器可以通過匯編語言的對齊指令命令來通知鏈接器。對于堆上分配的數據，將對象放置在Cache line的邊界或者最小化對象跨Cache line的次數的工作不是由編譯器來完成的，而是由runtime中的存儲分配器來完成的^[2]^。

圖2 因塊對齊可能會浪費存儲空間

前文提到了數據對象對齊，可以提高程序性能。指令Cache的對齊，也可以提高程序性能。同時，代碼布局也會影響程序的性能，將頻繁執行的基本塊的首地址對齊在Cache line的大小倍數邊界上能增加在指令Cache中同時容納的基本塊數目，將不頻繁執行的指令和頻繁指令的指令放到不同的Cache line中，通過優化代碼布局來提升程序性能。

利用硬件輔助

Cache預取是將內存中的指令和數據提前存放至Cache中，達到加快處理器執行速度的目的。Cache預取可以通過硬件或者軟件實現，硬件預取是通過處理器中專門的硬件單元實現的，該單元通過跟蹤內存訪問指令數據地址的變化規律來預測將會被訪問到的內存地址，并提前從主存中讀取這些數據到Cache；軟件預取是在程序中顯示地插入預取指令，以非阻塞的方式讓處理器從內存中讀取指定地址數據至Cache。由于硬件預取器通常無法正常動態關閉，因此大部分情況下軟件預取和硬件預取是并存的，軟件預取必須盡力配合硬件預取以取得更優的效果。本文假設硬件預取器被關閉后，討論如何利用軟件預取達到性能提升的效果。

預取指令prefech(x)只是一種提示，告知硬件開始將地址x中的數據從主存中讀取到Cache中。它并不會引起處理停頓，但若硬件發現會產生異常，則會忽略這個預取操作。如果prefech(x)成功，則意味著下一次取x將命中Cache；不成功的預取操作可能會導致下次讀取時發生Cache miss，但不會影響程序的正確性^[2]^。

數據預取是如何改成程序性能的呢？如下一段程序：

double a[n];
for (int i = 0; i < 100; i++)
 a[i] = 0;

假設一個Cache line可以存放兩個double元素，當第一次訪問a[0]時，由于a[0]不在Cache中，會發生一次Cache miss，需要從主存中將其加載至Cache中，由于一個Cache line可以存放兩個double元素，當訪問a[1]時則不會發生Cache miss。依次類推，訪問a[2]時會發生Cache miss，訪問a[3]時不會發生Cache miss，我們很容易得到程序總共發生了50次Cache miss。

我們可以通過軟件預取等相關優化，降低Cache miss次數，提高程序性能。首先介紹一個公式^[3]^：

上述公式中L是memory latency，S是執行一次循環迭代最短的時間。iterationAhead表示的是循環需要經過執行幾次迭代，預取的數據才會到達Cache。假設我們的硬件架構計算出來的iterationAhead=6，那么原程序可以優化成如下程序：

double a[n];
for (int i = 0; i < 12; i+=2)   //prologue 
 prefetch(&a[i]);
for (int i = 0; i < 88; i+=2) { // steady state
 prefetch(&a[i+12]);
 a[i] = 0;
 a[i+1] = 0;
}
for (int i = 88; i < 100; i++) //epilogue
 a[i] = 0;

由于我們的硬件架構需要循環執行6次后，預取的數據才會到達Cache。一個Cache line可以存放兩個double元素，為了避免浪費prefetch指令，所以prologue和steady state循環都展開了，即執行prefetch(&a[0])后會將a[0]、a[1]從主存加載至Cache中，下次執行預取時就無需再次將a[1]從主存加載至Cache了。prologue循環先執行數組a的前12個元素的預取指令，等到執行steady state循環時，當i = 0時，a[0]和a[1]已經被加載至Cache中，就不會發生Cache miss了。依次類推，經過上述優化后，在不改變語義的基礎上，通過使用預取指令，程序的Cache miss次數從50下降至0，程序的性能將會得到很大提升。

注意，預取并不能減少從主存儲器取數據到高速緩存的延遲，只是通過預取與計算重疊而隱藏這種延遲。總之，當處理器有預取指令或者有能夠用作預取的非阻塞的讀取指令時，對于處理器不能動態重排指令或者動態重排緩沖區小于我們希望隱藏的具體Cache延遲，并且所考慮的數據大于Cache或者是不能夠判斷數據是否已在Cache中，預取是適用的。預取也不是萬能，不當的預取可能會導致高速緩存沖突，程序性能降低。我們應該首先利用數據重用來減少延遲，然后才考慮預取。

除了軟件預取外，ARMv8還提供了Non-temporal的Load/Store指令，可以提高Cache的利用率。對于一些數據，如果只是訪問一次，無需占用Cache，可以使用這個指令進行訪問，從而保護Cache中關鍵數據不被替換，比如memcpy大數據的場景下，使用該指令對于其關鍵業務而言，是有一定的收益的。

循環變換

重用Cache中的數據是最基本的高效使用Cache方法。對于多層嵌套循環，可以通過交換兩個嵌套的循環（loop interchange）、逆轉循環迭代執行的順序（loop reversal）、將兩個循環體合并成一個循環體（loop fusion）、循環拆分（loop distribution）、循環分塊（loop tiling）、loop unroll and jam等循環變換操作。選擇適當的循環變換方式，既能保持程序的語義，又能改善程序性能。我們做這些循環變換的主要目的是為了實現寄存器、數據高速緩存以及其他存儲層次使用方面的優化。

篇幅受限，本節僅討論循環分塊（loop tiling）如何改善程序性能，若對loop interchange感興趣，請點擊查閱。下面這個簡單的循環：

for(int i = 0; i < m; i++) {
 for(int j = 0; j < n; j++) {
  x = x+a[i]+c*b[j];
 }
}

我們假設數組a、b都是超大數組，m、n相等且都很大，程序不會出現數組越界訪問情況發生。那么如果b[j]在j層循環中跨度太大時，那么被下次i層循環重用時數據已經被清出高速緩存。即程序訪問b[n-1]時，b[0]、b[1]已經被清出緩存，此時需要重新從主存中將數據加載至緩存中，程序性能會大幅下降。

我們如何通過降低Cache miss次數提升程序的性能呢？通過對循環做loop tiling可以符合我們的期望，即通過循環重排，使得數據分成一個一個tile，讓每一個tile的數據都可以在Cache中被hint^[4]^。從內層循環開始tiling，假設tile的大小為t，t遠小于m、n，t的取值使得b[t-1]被訪問時b[0]依然在Cache中，將會大幅地減少Cache miss次數。假設n-1恰好被t整除，此時b數組的訪問順序如下所示：

i=1; b[0]、b[1]、b[2]...b[t-1]
i=2; b[0]、b[1]、b[2]...b[t-1]
...
i=n; b[0]、b[1]、b[2]...b[t-1]
...
...
...
i=1; b[n-t]、b[n-t-1]、b[n-t-2]...b[n-1]
i=2; b[n-t]、b[n-t-1]、b[n-t-2]...b[n-1]
...
i=n; b[n-t]、b[n-t-1]、b[n-t-2]...b[n-1]

經過loop tiling后循環變換成：

for(int j = 0; j < n; j+=t) {
 for(int i = 0; i < m; i++) {
  for(int jj = j; jj < min(j+t, n); jj++) {
   x = x+a[i]+c*b[jj];
  }
 }
}

假設每個Cache line能夠容納X個數組元素，loop tiling前a的Cache miss次數為m/X，b的Cache miss次數是m*n/X，總的Cache miss次數為m*(n+1)/x。loop tiling后a的Cache miss次數為(n/t)*(m/X)，b的Cache miss次數為(t/X)*(n/t)=n/X，總的Cache miss次數為n*(m+t)/xt。此時，由于n與m相等，那么loop tiling后Cache miss大約可以降低t倍^[4]^。

前文討論了loop tiling在小用例上如何提升程序性能，總之針對不同的循環場景，選擇合適的循環交換方法，既能保證程序語義正確， 又能獲得改善程序性能的機會。

小結

汝之蜜糖，彼之砒霜。針對不同的硬件，我們需要結合具體的硬件架構，利用性能分析工具，通過分析報告和程序，從系統層次和算法層次思考問題，往往會有意想不到的收獲。本文簡單地介紹了內存層次優化相關的幾種方法，結合一些小例子深入淺出地講解了一些內存層次優化相關的知識。紙上得來終覺淺，絕知此事要躬行，更多性能優化相關的知識需要我們從實踐中慢慢摸索。