緩存命中

緩存命中

來自專欄 遊戲研發的點滴

遊戲開發者可分為兩類：在他們的遊戲引擎中使用STL模板庫之類的。以及不使用的。一些開發者認為STL內存分配模式(memory allocation pattern)不高效，也導致內存碎片問題，使STL不能在遊戲中使用。一些開發者認為STL的強大和方便超過它的問題，而且大部分的問題還是可以變通解決，筆者個人認為STL在PC上可以無障礙使用。因為PC上可以無障礙使用虛擬內存（virtual memory）系統,謹慎的分配內存變得不那麼緊要(雖然遊戲開發者仍要非常謹慎)。在遊戲主機上，只有有限（甚至沒有）虛擬內存功能，而且內存命中失敗（cache miss)的代價極高，遊戲開發者最好編寫自定義的數據結構，保證是可預期或者有限的內存分配模式。（在PC上做同樣的事情，肯定也不也錯不了。)【以上內容來自《遊戲引擎架構》第29頁】

什麼是Cache?

Cache Memory也被稱為Cache，是存儲器子系統的組成部分，存放著程序經常使用的指令和數據，這就是Cache的傳統定義。從廣義的角度上看，Cache是快設備為了緩解訪問慢設備延時的預留的Buffer，從而可以在掩蓋訪問延時的同時，儘可能地提高數據傳輸率。 快和慢是一個相對概念，與微架構(Microarchitecture)中的 L1/L2/L3 Cache相比， DDR內存是一個慢速設備；在磁碟 I/O 系統中，DDR卻是快速設備，在磁碟 I/O 系統中，仍在使用DDR內存作為磁介質的Cache。在一個微架構中，除了有L1/L2/L3 Cache之外，用於虛實地址轉換的各級TLB， MOB( Memory Ordering Buffers)、在指令流水線中的ROB，Register File和BTB等等也是一種Cache。我們這裡的Cache，是狹義 Cache，是CPU流水線和主存儲器的 L1/L2/L3 Cache。

好處是什麼

提高計算機的運行速度。只要能存儲數據的器件都可以稱之為存儲器，它的含義覆蓋了寄存器，緩存，內存，硬碟。cpu訪問快慢的速度依次為寄存器-> 緩存->內存->硬碟。

寄存器是中央處理器的組成部分，是一種直接整合到cpu中的有限的高速訪問速度的存儲器，它是有一些與非門組合組成的，分為通用寄存器和特殊寄存器。cpu訪問寄存器的速度是最快的。那為什麼我們不把數據都存儲到寄存器中呢，因為寄存器是一種容量有限的存儲器，並且非常小。因此只把一些計算機的指令等一些計算機頻繁用到的數據存儲在其中，來提高計算機的運行速度。

緩存其實是內存中高速緩存（cache）,它之所以存在，是因為當cpu要頻繁訪問內存中的一些數據時，如果每次都從內存中去讀，花費的時間會更多，因此在寄存器和內存之間有了緩存，把cpu要頻繁訪問的一些數據存儲在緩衝中，這樣效率就會更高，但需要注意的是，緩衝的大小也是很小的，不能存放大量的數據，並且緩存中存放的數據會因為cpu的訪問而被替代，必須某個數據開始被cpu頻繁訪問，但後來不再頻繁，那這個數據的空間會被其他訪問頻繁的數據所佔據（那些數據會被暫時存儲在緩存中是演算法問題）。緩存又可以分為一級和二級緩存，一級的速度大一二級的速度。因此cpu在訪問數據時，先到緩存中看有沒有，沒有的話再到內存中讀取。

作為一個程序員，你需要理解存儲器層次結構，因為它對應用程序的性能有著巨大的影響。如果你的程序需要的數據存儲在CPU寄存器中的，那麼在指令的執行期間，在零個周期內就能訪問到它們。如果存儲在高速緩存中，需要1~30個周期。如果存儲在主存中，需要50~200個周期。而如果存儲在磁碟上，需要大約幾千萬個周期。【以上內容來自《深入理解計算機系統(Computer Systems)》第382頁】

如何知道Cache大小

如何知道自己CPU的L2、L3的容量多大呢？當然可以用CPU-z，但其實可以有個更加簡單的辦法，在命令行輸入：

wmic cpu get L2CacheSize,L3CacheSize

我的筆記本得到這個結果：

怎麼去寫出緩存友好的代碼

• 如上一篇文章中struct 結構體類型的大小計算

1. struct stu3
2. {
3. char c1;// 偏移量為0符合要求，首位本身不需要偏移。
4. int i; // 偏移量為4， 結構體變數中成員的偏移量必須是成員大小的整數倍（0被認為是任何數的整數倍），所以1+3
5. char c2;// 偏移量為8（偏移量4+int大小4），符合要求
6. }

總長度不考慮自身對齊的最大的那個值的倍數，所以長度是1+3+4+1 = 9，考慮倍數長度是12

優化後

1. struct stu3
2. {
3. char c1;// 偏移量為0符合要求，首位本身不需要偏移。
4. char c2;// 偏移量為1（偏移量1+char大小1），符合要求
5. int i; // 偏移量為4， 結構體變數中成員的偏移量必須是成員大小的整數倍（0被認為是任何數的整數倍），所以
6. }

優化後大小是1+1+2+4= 8。

• 讓最常見的情況運行得快。大部分時間都花在少量的核心函數上，這些函數常把大部分時間都花在少量循環上。
• 在每個循環內部緩存不命中數量最小。
  舉例數組循環

1. int sumarraycols(int a[M][N])
2. {
3. int i,j,sum =0;
4. for(i=0;i<M;i++)
5. for(j=0;j<N;j++)
6. sum += a[i][j];
7. return sum;
8. }

int sumarraycols(int a[M][N])

{

int i,j,sum =0;

for(j=0;j<N;j++)

for(i=0;i<M;i++)

sum += a[i][j];

return sum;

}

第一個寫法是常見的寫法，緩存比較優好。第二個是修改後的。差異在於第一個是連續的內存塊。第二個是每隔一段取一塊。第二種miss的概率更高。Cache是CacheLine組成的。

——————————

參考

• 淺談CPU三級緩存和緩存命中率
• L1，L2，L3 Cache究竟在哪裡？
• Cache是怎麼組織和工作的？
• Cache為什麼有那麼多級？為什麼一級比一級大？是不是Cache越大越好？
• 對緩存的思考【續】——編寫高速緩存友好代碼

推薦閱讀：