摘要：本文重點介紹幾種通過優化Cache使用提高程式性能的方法，
本文分享自華為云社區《編譯器優化那些事兒（7）：Cache優化》，作者：畢昇小助手，
引言
軟體開發人員往往期望計算機硬體擁有無限容量、零訪問延遲、無限帶寬以及便宜的記憶體，但是現實卻是記憶體容量越大，相應的訪問時間越長；記憶體訪問速度越快，價格也更貴；帶寬越大，價格越貴，為了解決大容量、高速度、低成本之間的矛盾，基于程式訪問的區域性原理，將更常用資料放在小容量的高速存盤器中，多種速度不同的存盤器分層級聯，協調作業，
圖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在小用例上如何提升程式性能，總之針對不同的回圈場景，選擇合適的回圈交換方法，既能保證程式語意正確， 又能獲得改善程式性能的機會，
小結
汝之蜜糖，彼之砒霜，針對不同的硬體，我們需要結合具體的硬體架構，利用性能分析工具，通過分析報告和程式，從系統層次和演算法層次思考問題，往往會有意想不到的識訓，本文簡單地介紹了記憶體層次優化相關的幾種方法，結合一些小例子深入淺出地講解了一些記憶體層次優化相關的知識，紙上得來終覺淺，絕知此事要躬行，更多性能優化相關的知識需要我們從實踐中慢慢摸索，
參考
-
John L. Hennessy, David A. Patterson. 計算機體系結構：量化研究方法（第6版）. 賈洪峰,譯
-
Andrew W.Apple, with Jens Palsberg. Modern Compiler Implenentation in C
-
http://www.cs.cmu.edu/afs/cs/academic/class/15745-s19/www/lectures/L20-Global-Scheduling.pdf
-
https://zhuanlan.zhihu.com/p/292539074
點擊關注，第一時間了解華為云新鮮技術~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539033.html
標籤：其他