一、 基礎知識

???首先，大家都知道現在CPU的多核技術，都會有幾級快取，現在的CPU會有三級記憶體（L1，L2， L3），如下圖所示，

其中：

??? L1快取分成兩種，一種是指令快取，一種是資料快取，L2快取和L3快取不分指令和資料，

• L1和L2快取在每一個CPU核中，L3則是所有CPU核心共享的記憶體，

• L1、L2、L3的越離CPU近就越小，速度也就越快，越離CPU遠，速度也越慢，

再往后面就是記憶體，記憶體的后面就是硬碟，我們來看一些他們的速度，

• L1的存取速度：4個CPU時鐘周期
• L2的存取速度：11個CPU時鐘周期
• L3的存取速度：39個CPU時鐘周期
• RAM記憶體的存取速度：107個CPU時鐘周期

???我們可以看到，L1的速度是RAM的27倍，L1和L2的存取大小基本上是KB級的，L3則是MB級別的，例如，Intel Core i7-8700K,是一個6核的CPU，每核上的L1是64KB（資料和指令各32KB）,L2是256K，L3有2MB，
我們的資料從記憶體向上，先到L3，再到L2，再到L1，最后到暫存器進行計算，那么，為什么會設計成三層？這里有以下幾方面的考慮：

• 物理速度，如果要更大的容量就需要更多的晶體管，除了芯片的體積會變大，更重要的是大量的晶體管會導致速度下降，因為訪問速度和要訪問的晶體管所在的位置成反比，也就是當信號路徑變長時，通信速度會變慢，這就是物理問題，

• 另外一個問題是，多核技術中，資料的狀態需要在多個CPU進行同步，我們可以看到，cache和RAM的速度差距太大，所以，多級不同尺寸的快取有利于提高整體的性能，
  ???這個世界永遠是平衡的，一面變得有多光鮮，另一方面也會變得有多黑暗，建立多級的快取，一定就會引入其它的問題，這里有兩個比較重要的問題，

• 一個是比較簡單的快取命中率的問題

• 另一個是比較復雜的快取更新的一致性問題

???尤其是第二個問題，在多核技術下，這就很像分布式系統了，要面對多個地方進行更新，

二、 快取命中

???首先，我們需要了解一個術語Cache Line，快取基本上來說就是把后面的資料加載到離自己最近的地方，對于CPU來說，它是不會一個位元組一個位元組的加載的，因為這非常沒有效率，一般來說都是要一塊一塊的加載的，對于這樣一塊一塊的資料單位，術語叫“Cache Line”，一般來說，一個主流的CPU的Cache Line是64 Bytes(也有的CPU用32Bytes和128Bytes),64Bytes也就是16個32位的數字,這就是CPU從記憶體中撈資料上來的最小資料單位，比如：Cache Line是最小單位（64Bytes），所以先把Cache分布多個Cache Line，比如：L1有32KB，那么 32KB/64B = 512個Cache Line，
???快取需要把記憶體里的資料放進來，英文叫CPU Associativity，Cache的資料放置策略決定了記憶體中的資料會拷貝到CPU Cache中的哪個位置上，因為Cache的大小遠遠小于記憶體，所以，需要有一種地址關聯演算法，能夠讓記憶體中的資料被映射到Cache中，這個就有點像記憶體地址從邏輯地址到物理地址的映射方法，但是不完全一樣，

基本上會有以下的一些方法

• 任何一個記憶體的資料可以被快取在任何一個Cache Line里，這種方法是最靈活的，但是，如果我們要知道一個記憶體是否存在于Cache中，我們就需要進行O(n)復雜度的Cache遍歷，這是沒有效率的，
• 另一種方法，為了降低快取搜索演算法的時間復雜度，我們要使用像hash table這樣的資料結構，最簡單的hash table就是“求模運算”，比如，我們的L1 Cache有512個Cache Line,那么公式就是(記憶體地址 mod 512) *64就可以直接找到所在的Cache地址的偏移了，但是，這樣的方式需要程式對記憶體地址的訪問非常的平均，不然會造成嚴重地沖突，所以，這成了一個非常理想的情況了，
• 為了避免上述的兩種方案的問題，于是就要容忍一定的hash沖突，也就出現了N-Way關聯，也就是把連續的N個Cache Line綁成一組，然后，先找到相關的組，然后再在組內找到相關的Cache Line，這叫Set Associativity，如下圖所示
  
  ???對于 N-Way 組關聯，可能有點不好理解，這里舉個例子，并多說一些細節（不然后面的代碼你會不能理解），Intel 大多數處理器的L1 Cache都是32KB，8-Way 組相聯，Cache Line 是64 Bytes，這意味著
• 32KB的可以分成，32KB / 64 = 512 條 Cache Line；
• 因為有8 Way，于是會每一Way 有 512 / 8 = 64 條 Cache Line；
• 于是每一路就有 64 x 64 = 4096 Byts 的記憶體，

為了方便索引記憶體地址

• Tag：每條 Cache Line 前都會有一個獨立分配的 24 bits來存的 tag，其就是記憶體地址的前24bits；
• Index：記憶體地址后續的6個bits則是在這一Way的是Cache Line 索引，2^6 = 64 剛好可以索引64條Cache Line；
• Offset：再往后的6bits用于表示在Cache Line 里的偏移量

索引程序如下圖所示：

• 當拿到一個記憶體地址的時候，先拿出中間的 6bits 來，找到是哪組；
  

• 然后在這一個8組的cache line中，再進行O(n) ，n=8 的遍歷，主是要匹配前24bits的tag，如果匹配中了，就算命中，如果沒有匹配到，那就是cache miss，如果是讀操作，就需要進向后面的快取進行訪問了，L2和L3同樣是這樣的演算法，而淘汰演算法有兩種，一種是隨機，另一種是LRU，
  

這也意味著：

• L1 Cache 可映射 36bits 的記憶體地址，一共 2^36 = 64GB的記憶體
• 當CPU要訪問一個記憶體的時候，通過這個記憶體中間的6bits 定位是哪個set，通過前 24bits 定位相應的Cache Line，
• 就像一個hash Table的資料結構一樣，先是O(1)的索引，然后進入沖突搜索， 因為中間的 6bits決定了一個同一個set，所以，對于一段連續的記憶體來說，每隔4096的記憶體會被放在同一個組內，導致快取沖突，

???此外，當有資料沒有命中快取的時候，CPU就會以最小為Cache Line的單元向記憶體更新資料，當然，CPU并不一定只是更新64Bytes，因為訪問主存實在是太慢了，所以，一般都會多更新一些，好的CPU會有一些預測的技術，如果找到一種pattern的話，就會預先加載更多的記憶體，包括指令也可以預加載，這叫 Prefetching 技術，比如，你在for-loop訪問一個連續的陣列，你的步長是一個固定的數，記憶體就可以做到prefetching，

了解這些細節，會有利于我們知道在什么情況下有可以導致快取的失效，

三、快取一致

???對于主流的CPU來說，快取的寫操作基本上是兩種策略

• Write Back：寫操作只在Cache上，然后再flush到記憶體上
• Write Through：寫操作同時寫到cache和記憶體上，

???為了提高寫的性能，一般來說，主流的CPU（如：Intel Core i7/i9）采用的是Write Back的策略，因為直接寫記憶體實在是太慢了，

???好了，現在問題來了，如果有一個資料 x 在 CPU 第0核的快取上被更新了，那么其它CPU核上對于這個資料 x 的值也要被更新，這就是快取一致性的問題，

???一般來說，在CPU硬體上，會有兩種方法來解決這個問題，

1. Directory 協議，這種方法的典型實作是要設計一個集中式控制器，它是主存盤器控制器的一部分，其中有一個目錄存盤在主存盤器中，其中包含有關各種本地快取內容的全域狀態資訊，當單個CPU Cache 發出讀寫請求時，這個集中式控制器會檢查并發出必要的命令，以在主存和CPU Cache之間或在CPU Cache自身之間進行資料同步和傳輸，
2. Snoopy 協議，這種協議更像是一種資料通知的總線型的技術，CPU Cache通過這個協議可以識別其它Cache上的資料狀態，如果有資料共享的話，可以通過廣播機制將共享資料的狀態通知給其它CPU Cache，這個協議要求每個CPU Cache 都可以“窺探”資料事件的通知并做出相應的反應，如下圖所示，有一個Snoopy Bus的總線，

???因為Directory協議是一個中心式的，會有性能瓶頸，而且會增加整體設計的復雜度，而Snoopy協議更像是微服務+訊息通訊，所以，現在基本都是使用Snoopy的總線的設計，

? 在分布式系統中我們一般用Paxos/Raft這樣的分布式一致性的演算法，而在CPU的微觀世界里，則不必使用這樣的演算法，因為CPU的多個核的硬體不必考慮網路會斷會延遲的問題，所以，CPU的多核心快取間的同步的核心就是要管理好資料的狀態就好了，
???這里介紹幾個狀態協議，先從最簡單的開始，MESI協議，這個協議跟那個著名的足球運動員梅西沒什么關系，其主要表示快取資料有四個狀態：Modified（已修改）, Exclusive（獨占的）,Shared（共享的），Invalid（無效的），
??? MESI 這種協議在資料更新后，會標記其它共享的CPU快取的資料拷貝為Invalid狀態，然后當其它CPU再次read的時候，就會出現 cache miss 的問題，此時再從記憶體中更新資料，從記憶體中更新資料意味著20倍速度的降低，我們能不能直接從我隔壁的CPU快取中更新？是的，這就可以增加很多速度了，但是狀態控制也就變麻煩了，還需要多來一個狀態：Owner(宿主)，用于標記，我是更新資料的源，于是，出現了 MOESI 協議，
??? MOESI協議允許 CPU Cache 間同步資料，于是也降低了對記憶體的操作，性能是非常大的提升，但是控制邏輯也非常復雜，
??? 順便說一下，與 MOESI 協議類似的一個協議是 MESIF，其中的 F 是 Forward，同樣是把更新過的資料轉發給別的 CPU Cache 但是，MOESI 中的 Owner 狀態 和MESIF 中的 Forward 狀態有一個非常大的不一樣—— Owner狀態下的資料是dirty的，還沒有寫回記憶體，Forward狀態下的資料是clean的，可以丟棄而不用另行通知，
??? 需要說明的是，AMD用MOESI，Intel用MESIF，所以，F 狀態主要是針對 CPU L3 Cache 設計的（前面我們說過，L3是所有CPU核心共享的），

四、程式性能

??? 了解了我們上面的這些東西后，我們來看一下對于程式的影響，

示例一

???首先，假設我們有一個64M長的陣列，設想一下下面的兩個回圈：

       const int LEN = 64*1024*1024;
       int *arr = new int[LEN];

          for (int i = 0; i < LEN; i += 2) arr[i] *= i;

          for (int i = 0; i < LEN; i += 8) arr[i] *= i; 

??? 按我們的想法，第二個回圈要比第一個回圈少4倍的計算量，其應該要快4倍的，但實際跑下來并不是，在我的機器上，第一個回圈需要128毫秒，第二個回圈則需要122毫秒，相差無幾，這里最主要的原因就是 Cache Line，因為CPU會以一個Cache Line 64Bytes最小時單位加載，也就是16個32bits的整型，所以，無論你步長是2還是8，都差不多，而后面的乘法其實是不耗CPU時間的，

示例二

???接下來，我們再來看個示例，下面是一個二維陣列的兩種遍歷方式，一個逐行遍歷，一個是逐列遍歷，這兩種方式在理論上來說，尋址和計算量都是一樣的，執行時間應該也是一樣的，

const int row = 1024;
const int col = 512
int matrix[row][col];
//逐行遍歷
int sum_row=0;
for(int _r=0; _r<row; _r++) {
    for(int _c=0; _c<col; _c++){
        sum_row += matrix[_r][_c];
    }
}
//逐列遍歷
int sum_col=0;
for(int _c=0; _c<col; _c++) {
    for(int _r=0; _r<row; _r++){
        sum_col += matrix[_r][_c];
    }
}

???然而，并不是，在我的機器上，得到下面的結果，

???逐行遍歷：0.083ms
???逐列遍歷：1.072ms

???執行時間有十幾倍的差距，其中的原因，就是逐列遍歷對于CPU Cache 的運作方式并不友好，所以，付出巨大的代價，

示例三

???接下來，我們來看一下多核下的性能問題，參看如下的代碼，兩個執行緒在操作一個陣列的兩個不同的元素（無需加鎖），執行緒回圈1000萬次，做加法操作，在下面的代碼中，我高亮了一行，就是p2指標，要么是p[1]，或是 p[30]，理論上來說，無論訪問哪兩個陣列元素，都應該是一樣的執行時間，

 void fn (int* data) {
    for(int i = 0; i < 10*1024*1024; ++i)
        *data += rand();
}
int p[32];
int *p1 = &p[0];
int *p2 = &p[1]; // int *p2 = &p[30];
thread t1(fn, p1);
thread t2(fn, p2);

???然而，并不是，在我的機器上執行下來的結果是：

???對于 p[0] 和 p[1] ：570ms
???對于 p[0] 和 p[30]：105ms

???這是因為 p[0] 和 p[1] 在同一條 Cache Line 上，而 p[0] 和 p[30] 則不可能在同一條Cache Line 上 ，CPU的快取最小的更新單位是Cache Line，所以，這導致雖然兩個執行緒在寫不同的資料，但是因為這兩個資料在同一條Cache Line上，就會導致快取需要不斷進在兩個CPU的L1/L2中進行同步，從而導致了5倍的時間差異，