介紹幾種通過優(yōu)化Cache使用提高程序性能的方法

引言

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

圖1 memory hierarchy for sever[1]

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

前文提到了程序的局部性原理，一般指的是時間局部性（在一定時間內，程序可能會多次訪問同一內存空間）和空間局部性（在一定時間內，程序可能會訪問附近的內存空間），高速緩存（Cache）的效率取決于程序的空間和時間的局部性性質。

比如一個程序重復地執(zhí)行一個循環(huán)，在理想情況下，循環(huán)的第一個迭代將代碼取至高速緩存中，后續(xù)的迭代直接從高速緩存中取數(shù)據，而不需要重新從主存裝載。因此，為了使程序獲得更好的性能，應盡可能讓數(shù)據訪問發(fā)生在高速緩存中。但是如果數(shù)據訪問在高速緩存時發(fā)生了沖突，也可能會導致性能下降。

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

對齊和布局

現(xiàn)代編譯器可以通過調整代碼和數(shù)據的布局方式，提高Cache命中率，進而提升程序性能。本節(jié)主要討論數(shù)據和指令的對齊、代碼布局對程序性能的影響，大部分處理器中Cache到主存是以Cache line（一般為64Byte，也有地方稱Cache塊，本文統(tǒng)一使用Cache line）傳輸?shù)?，CPU從內存加載數(shù)據是一次一個Cache line，CPU往內存寫數(shù)據也是一次一個Cache line。

假設處理器首次訪問數(shù)據對象A，其大小剛好為64Byte，如果數(shù)據對象A首地址并沒有進行對齊，即數(shù)據對象A占用兩個不同Cache line的一部分，此時處理器訪問該數(shù)據對象時需要兩次內存訪問，效率低。

但是如果數(shù)據對象A進行了內存對齊，即剛好在一個Cache line中，那么處理器訪問該數(shù)據時只需要一次內存訪問，效率會高很多。編譯器可以通過合理安排數(shù)據對象，避免不必要地將它們跨越在多個Cache line中，盡量使得同一對象集中在一個Cache中，進而有效地使用Cache來提高程序的性能。

通過順序分配對象，即如果下一個對象不能放入當前Cache line的剩余部分，則跳過這些剩余的部分，從下一個Cache line的開始處分配對象，或者將大小（size）相同的對象分配在同一個存儲區(qū)，所有對象都對齊在size的倍數(shù)邊界上等方式達到上述目的。

Cache line對齊可能會導致存儲資源的浪費，如圖2所示，但是執(zhí)行速度可能會因此得到改善。對齊不僅僅可以作用于全局靜態(tài)數(shù)據，也可以作用于堆上分配的數(shù)據。對于全局數(shù)據，編譯器可以通過匯編語言的對齊指令命令來通知鏈接器。

對于堆上分配的數(shù)據，將對象放置在Cache line的邊界或者最小化對象跨Cache line的次數(shù)的工作不是由編譯器來完成的，而是由runtime中的存儲分配器來完成的[2]。

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

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

利用硬件輔助

Cache預取是將內存中的指令和數(shù)據提前存放至Cache中，達到加快處理器執(zhí)行速度的目的。Cache預取可以通過硬件或者軟件實現(xiàn)，硬件預取是通過處理器中專門的硬件單元實現(xiàn)的，該單元通過跟蹤內存訪問指令數(shù)據地址的變化規(guī)律來預測將會被訪問到的內存地址，并提前從主存中讀取這些數(shù)據到Cache；軟件預取是在程序中顯示地插入預取指令，以非阻塞的方式讓處理器從內存中讀取指定地址數(shù)據至Cache。

由于硬件預取器通常無法正常動態(tài)關閉，因此大部分情況下軟件預取和硬件預取是并存的，軟件預取必須盡力配合硬件預取以取得更優(yōu)的效果。本文假設硬件預取器被關閉后，討論如何利用軟件預取達到性能提升的效果。

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

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

doublea[n];
for(inti=0;i

	

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

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

	

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

	
doublea[n];
for(inti=0;i

	

	由于我們的硬件架構需要循環(huán)執(zhí)行6次后，預取的數(shù)據才會到達Cache。一個Cache line可以存放兩個double元素，為了避免浪費prefetch指令，所以prologue和steady state循環(huán)都展開了，即執(zhí)行prefetch(&a[0])后會將a[0]、a[1]從主存加載至Cache中，下次執(zhí)行預取時就無需再次將a[1]從主存加載至Cache了。


	prologue循環(huán)先執(zhí)行數(shù)組a的前12個元素的預取指令，等到執(zhí)行steady state循環(huán)時，當i = 0時，a[0]和a[1]已經被加載至Cache中，就不會發(fā)生Cache miss了。依次類推，經過上述優(yōu)化后，在不改變語義的基礎上，通過使用預取指令，程序的Cache miss次數(shù)從50下降至0，程序的性能將會得到很大提升。

	注意，預取并不能減少從主存儲器取數(shù)據到高速緩存的延遲，只是通過預取與計算重疊而隱藏這種延遲。總之，當處理器有預取指令或者有能夠用作預取的非阻塞的讀取指令時，對于處理器不能動態(tài)重排指令或者動態(tài)重排緩沖區(qū)小于我們希望隱藏的具體Cache延遲，并且所考慮的數(shù)據大于Cache或者是不能夠判斷數(shù)據是否已在Cache中，預取是適用的。


	預取也不是萬能，不當?shù)念A取可能會導致高速緩存沖突，程序性能降低。我們應該首先利用數(shù)據重用來減少延遲，然后才考慮預取。

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

	循環(huán)變換

	重用Cache中的數(shù)據是最基本的高效使用Cache方法。對于多層嵌套循環(huán)，可以通過交換兩個嵌套的循環(huán)（loop interchange）、逆轉循環(huán)迭代執(zhí)行的順序（loop reversal）、將兩個循環(huán)體合并成一個循環(huán)體（loop fusion）、循環(huán)拆分（loop distribution）、循環(huán)分塊（loop tiling）、loop unroll and jam等循環(huán)變換操作。


	選擇適當?shù)难h(huán)變換方式，既能保持程序的語義，又能改善程序性能。我們做這些循環(huán)變換的主要目的是為了實現(xiàn)寄存器、數(shù)據高速緩存以及其他存儲層次使用方面的優(yōu)化。

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

	
for(inti=0;i

	

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

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

	
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后循環(huán)變換成：

	
for(intj=0;j

	

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

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

	小結

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

	





	審核編輯：劉清