面試官：如何寫出讓 CPU 跑得更快的程式碼？

2020 年 10 月 18 日
筆記
圖解作業系統

前言

程式碼都是由 CPU 跑起來的，我們程式碼寫的好與壞就決定了 CPU 的執行效率，特別是在編寫計算密集型的程式，更要注重 CPU 的執行效率，否則將會大大影響系統性能。

CPU 內部嵌入了 CPU Cache（高速快取），它的存儲容量很小，但是離 CPU 核心很近，所以快取的讀寫速度是極快的，那麼如果 CPU 運算時，直接從 CPU Cache 讀取數據，而不是從記憶體的話，運算速度就會很快。

但是，大多數人不知道 CPU Cache 的運行機制，以至於不知道如何才能夠寫出能夠配合 CPU Cache 工作機制的程式碼，一旦你掌握了它，你寫程式碼的時候，就有新的優化思路了。

那麼，接下來我們就來看看，CPU Cache 到底是什麼樣的，是如何工作的呢，又該寫出讓 CPU 執行更快的程式碼呢？

正文

CPU Cache 有多快？

你可能會好奇為什麼有了記憶體，還需要 CPU Cache？根據摩爾定律，CPU 的訪問速度每 18 個月就會翻倍，相當於每年增長 60% 左右，記憶體的速度當然也會不斷增長，但是增長的速度遠小於 CPU，平均每年只增長 7% 左右。於是，CPU 與記憶體的訪問性能的差距不斷拉大。

到現在，一次記憶體訪問所需時間是 200~300 多個時鐘周期，這意味著 CPU 和記憶體的訪問速度已經相差 200~300 多倍了。

為了彌補 CPU 與記憶體兩者之間的性能差異，就在 CPU 內部引入了 CPU Cache，也稱高速快取。

CPU Cache 通常分為大小不等的三級快取，分別是 L1 Cache、L2 Cache 和 L3 Cache。

由於 CPU Cache 所使用的材料是 SRAM，價格比記憶體使用的 DRAM 高出很多，在當今每生產 1 MB 大小的 CPU Cache 需要 7 美金的成本，而記憶體只需要 0.015 美金的成本，成本方面相差了 466 倍，所以 CPU Cache 不像記憶體那樣動輒以 GB 計算，它的大小是以 KB 或 MB 來計算的。

在 Linux 系統中，我們可以使用下圖的方式來查看各級 CPU Cache 的大小，比如我這手上這台伺服器，離 CPU 核心最近的 L1 Cache 是 32KB，其次是 L2 Cache 是 256KB，最大的 L3 Cache 則是 3MB。

其中，L1 Cache 通常會分為「數據快取」和「指令快取」，這意味著數據和指令在 L1 Cache 這一層是分開快取的，上圖中的 index0 也就是數據快取，而 index1 則是指令快取，它兩的大小通常是一樣的。

另外，你也會注意到，L3 Cache 比 L1 Cache 和 L2 Cache 大很多，這是因為 L1 Cache 和 L2 Cache 都是每個 CPU 核心獨有的，而 L3 Cache 是多個 CPU 核心共享的。

程式執行時，會先將記憶體中的數據載入到共享的 L3 Cache 中，再載入到每個核心獨有的 L2 Cache，最後進入到最快的 L1 Cache，之後才會被 CPU 讀取。它們之間的層級關係，如下圖：

越靠近 CPU 核心的快取其訪問速度越快，CPU 訪問 L1 Cache 只需要 2~4 個時鐘周期，訪問 L2 Cache 大約 10~20 個時鐘周期，訪問 L3 Cache 大約 20~60 個時鐘周期，而訪問記憶體速度大概在 200~300 個時鐘周期之間。如下表格：

所以，CPU 從 L1 Cache 讀取數據的速度，相比從記憶體讀取的速度，會快 100 多倍。

CPU Cache 的數據結構和讀取過程是什麼樣的？

CPU Cache 的數據是從記憶體中讀取過來的，它是以一小塊一小塊讀取數據的，而不是按照單個數組元素來讀取數據的，在 CPU Cache 中的，這樣一小塊一小塊的數據，稱為 Cache Line（快取塊）。

你可以在你的 Linux 系統，用下面這種方式來查看 CPU 的 Cache Line，你可以看我伺服器的 L1 Cache Line 大小是 64 位元組，也就意味著 L1 Cache 一次載入數據的大小是 64 位元組。

比如，有一個 int array[100] 的數組，當載入 array[0] 時，由於這個數組元素的大小在記憶體只佔 4 位元組，不足 64 位元組，CPU 就會順序載入數組元素到 array[15]，意味著 array[0]~array[15] 數組元素都會被快取在 CPU Cache 中了，因此當下次訪問這些數組元素時，會直接從 CPU Cache 讀取，而不用再從記憶體中讀取，大大提高了 CPU 讀取數據的性能。

事實上，CPU 讀取數據的時候，無論數據是否存放到 Cache 中，CPU 都是先訪問 Cache，只有當 Cache 中找不到數據時，才會去訪問記憶體，並把記憶體中的數據讀入到 Cache 中，CPU 再從 CPU Cache 讀取數據。

這樣的訪問機制，跟我們使用「記憶體作為硬碟的快取」的邏輯是一樣的，如果記憶體有快取的數據，則直接返回，否則要訪問龜速一般的硬碟。

那 CPU 怎麼知道要訪問的記憶體數據，是否在 Cache 里？如果在的話，如何找到 Cache 對應的數據呢？我們從最簡單、基礎的直接映射 Cache（Direct Mapped Cache） 說起，來看看整個 CPU Cache 的數據結構和訪問邏輯。

前面，我們提到 CPU 訪問記憶體數據時，是一小塊一小塊數據讀取的，具體這一小塊數據的大小，取決於 coherency_line_size 的值，一般 64 位元組。在記憶體中，這一塊的數據我們稱為記憶體塊（Block），讀取的時候我們要拿到數據所在記憶體塊的地址。

對於直接映射 Cache 採用的策略，就是把記憶體塊的地址始終「映射」在一個 CPU Line（快取塊）的地址，至於映射關係實現方式，則是使用「取模運算」，取模運算的結果就是記憶體塊地址對應的 CPU Line（快取塊）的地址。

舉個例子，記憶體共被劃分為 32 個記憶體塊，CPU Cache 共有 8 個 CPU Line，假設 CPU 想要訪問第 15 號記憶體塊，如果 15 號記憶體塊中的數據已經快取在 CPU Line 中的話，則是一定映射在 7 號 CPU Line 中，因為 15 % 8 的值是 7。

機智的你肯定發現了，使用取模方式映射的話，就會出現多個記憶體塊對應同一個 CPU Line，比如上面的例子，除了 15 號記憶體塊是映射在 7 號 CPU Line 中，還有 7 號、23 號、31 號記憶體塊都是映射到 7 號 CPU Line 中。

因此，為了區別不同的記憶體塊，在對應的 CPU Line 中我們還會存儲一個組標記（Tag）。這個組標記會記錄當前 CPU Line 中存儲的數據對應的記憶體塊，我們可以用這個組標記來區分不同的記憶體塊。

除了組標記資訊外，CPU Line 還有兩個資訊：

一個是，從記憶體載入過來的實際存放數據（Data）。
另一個是，有效位（Valid bit），它是用來標記對應的 CPU Line 中的數據是否是有效的，如果有效位是 0，無論 CPU Line 中是否有數據，CPU 都會直接訪問記憶體，重新載入數據。

CPU 在從 CPU Cache 讀取數據的時候，並不是讀取 CPU Line 中的整個數據塊，而是讀取 CPU 所需要的一個數據片段，這樣的數據統稱為一個字（Word）。那怎麼在對應的 CPU Line 中數據塊中找到所需的字呢？答案是，需要一個偏移量（Offset）。

因此，一個記憶體的訪問地址，包括組標記、CPU Line 索引、偏移量這三種資訊，於是 CPU 就能通過這些資訊，在 CPU Cache 中找到快取的數據。而對於 CPU Cache 里的數據結構，則是由索引 + 有效位 + 組標記 + 數據塊組成。

如果記憶體中的數據已經在 CPU Cahe 中了，那 CPU 訪問一個記憶體地址的時候，會經歷這 4 個步驟：

根據記憶體地址中索引資訊，計算在 CPU Cahe 中的索引，也就是找出對應的 CPU Line 的地址；
找到對應 CPU Line 後，判斷 CPU Line 中的有效位，確認 CPU Line 中數據是否是有效的，如果是無效的，CPU 就會直接訪問記憶體，並重新載入數據，如果數據有效，則往下執行；
對比記憶體地址中組標記和 CPU Line 中的組標記，確認 CPU Line 中的數據是我們要訪問的記憶體數據，如果不是的話，CPU 就會直接訪問記憶體，並重新載入數據，如果是的話，則往下執行；
根據記憶體地址中偏移量資訊，從 CPU Line 的數據塊中，讀取對應的字。

到這裡，相信你對直接映射 Cache 有了一定認識，但其實除了直接映射 Cache 之外，還有其他通過記憶體地址找到 CPU Cache 中的數據的策略，比如全相連 Cache （Fully Associative Cache）、組相連 Cache （Set Associative Cache）等，這幾種策策略的數據結構都比較相似，我們理解了直接映射 Cache 的工作方式，其他的策略如果你有興趣去看，相信很快就能理解的了。

如何寫出讓 CPU 跑得更快的程式碼？

我們知道 CPU 訪問記憶體的速度，比訪問 CPU Cache 的速度慢了 100 多倍，所以如果 CPU 所要操作的數據在 CPU Cache 中的話，這樣將會帶來很大的性能提升。訪問的數據在 CPU Cache 中的話，意味著快取命中，快取命中率越高的話，程式碼的性能就會越好，CPU 也就跑的越快。

於是，「如何寫出讓 CPU 跑得更快的程式碼？」這個問題，可以改成「如何寫出 CPU 快取命中率高的程式碼？」。

在前面我也提到， L1 Cache 通常分為「數據快取」和「指令快取」，這是因為 CPU 會別處理數據和指令，比如 1+1=2 這個運算，+ 就是指令，會被放在「指令快取」中，而輸入數字 1 則會被放在「數據快取」里。

因此，我們要分開來看「數據快取」和「指令快取」的快取命中率。

如何提升數據快取的命中率？

假設要遍歷二維數組，有以下兩種形式，雖然程式碼執行結果是一樣，但你覺得哪種形式效率最高呢？為什麼高呢？

經過測試，形式一 array[i][j] 執行時間比形式二 array[j][i] 快好幾倍。

之所以有這麼大的差距，是因為二維數組 array 所佔用的記憶體是連續的，比如長度 N 的指是 2 的話，那麼記憶體中的數組元素的布局順序是這樣的：

形式一用 array[i][j] 訪問數組元素的順序，正是和記憶體中數組元素存放的順序一致。當 CPU 訪問 array[0][0] 時，由於該數據不在 Cache 中，於是會「順序」把跟隨其後的 3 個元素從記憶體中載入到 CPU Cache，這樣當 CPU 訪問後面的 3 個數組元素時，就能在 CPU Cache 中成功地找到數據，這意味著快取命中率很高，快取命中的數據不需要訪問記憶體，這便大大提高了程式碼的性能。

而如果用形式二的 array[j][i] 來訪問，則訪問的順序就是：

你可以看到，訪問的方式跳躍式的，而不是順序的，那麼如果 N 的數值很大，那麼操作 array[j][i] 時，是沒辦法把 array[j+1][i] 也讀入到 CPU Cache 中的，既然 array[j+1][i] 沒有讀取到 CPU Cache，那麼就需要從記憶體讀取該數據元素了。很明顯，這種不連續性、跳躍式訪問數據元素的方式，可能不能充分利用到了 CPU Cache 的特性，從而程式碼的性能不高。

那訪問 array[0][0] 元素時，CPU 具體會一次從記憶體中載入多少元素到 CPU Cache 呢？這個問題，在前面我們也提到過，這跟 CPU Cache Line 有關，它表示 CPU Cache 一次性能載入數據的大小，可以在 Linux 里通過 coherency_line_size 配置查看它的大小，通常是 64 個位元組。

也就是說，當 CPU 訪問記憶體數據時，如果數據不在 CPU Cache 中，則會一次性會連續載入 64 位元組大小的數據到 CPU Cache，那麼當訪問 array[0][0] 時，由於該元素不足 64 位元組，於是就會往後順序讀取 array[0][0]~array[0][15] 到 CPU Cache 中。順序訪問的 array[i][j] 因為利用了這一特點，所以就會比跳躍式訪問的 array[j][i] 要快。

因此，遇到這種遍曆數組的情況時，按照記憶體布局順序訪問，將可以有效的利用 CPU Cache 帶來的好處，這樣我們程式碼的性能就會得到很大的提升，

如何提升指令快取的命中率？

提升數據的快取命中率的方式，是按照記憶體布局順序訪問，那針對指令的快取該如何提升呢？

我們以一個例子來看看，有一個元素為 0 到 100 之間隨機數字組成的一維數組：

接下來，對這個數組做兩個操作：

第一個操作，循環遍曆數組，把小於 50 的數組元素置為 0；
第二個操作，將數組排序；

那麼問題來了，你覺得先遍歷再排序速度快，還是先排序再遍歷速度快呢？

在回答這個問題之前，我們先了解 CPU 的分支預測器。對於 if 條件語句，意味著此時至少可以選擇跳轉到兩段不同的指令執行，也就是 if 還是 else 中的指令。那麼，如果分支預測可以預測到接下來要執行 if 里的指令，還是 else 指令的話，就可以「提前」把這些指令放在指令快取中，這樣 CPU 可以直接從 Cache 讀取到指令，於是執行速度就會很快。

當數組中的元素是隨機的，分支預測就無法有效工作，而當數組元素都是是順序的，分支預測器會動態地根據歷史命中數據對未來進行預測，這樣命中率就會很高。

因此，先排序再遍歷速度會更快，這是因為排序之後，數字是從小到大的，那麼前幾次循環命中 if < 50 的次數會比較多，於是分支預測就會快取 if 里的 array[i] = 0 指令到 Cache 中，後續 CPU 執行該指令就只需要從 Cache 讀取就好了。

如果你肯定程式碼中的 if 中的表達式判斷為 true 的概率比較高，我們可以使用顯示分支預測工具，比如在 C/C++ 語言中編譯器提供了 likely 和 unlikely 這兩種宏，如果 if 條件為 ture 的概率大，則可以用 likely 宏把 if 里的表達式包裹起來，反之用 unlikely 宏。

實際上，CPU 自身的動態分支預測已經是比較準的了，所以只有當非常確信 CPU 預測的不準，且能夠知道實際的概率情況時，才建議使用這兩種宏。

如果提升多核 CPU 的快取命中率？

在單核 CPU，雖然只能執行一個進程，但是作業系統給每個進程分配了一個時間片，時間片用完了，就調度下一個進程，於是各個進程就按時間片交替地佔用 CPU，從宏觀上看起來各個進程同時在執行。

而現代 CPU 都是多核心的，進程可能在不同 CPU 核心來回切換執行，這對 CPU Cache 不是有利的，雖然 L3 Cache 是多核心之間共享的，但是 L1 和 L2 Cache 都是每個核心獨有的，如果一個進程在不同核心來回切換，各個核心的快取命中率就會受到影響，相反如果進程都在同一個核心上執行，那麼其數據的 L1 和 L2 Cache 的快取命中率可以得到有效提高，快取命中率高就意味著 CPU 可以減少訪問記憶體的頻率。

當有多個同時執行「計算密集型」的執行緒，為了防止因為切換到不同的核心，而導致快取命中率下降的問題，我們可以把執行緒綁定在某一個 CPU 核心上，這樣性能可以得到非常可觀的提升。

在 Linux 上提供了 sched_setaffinity 方法，來實現將執行緒綁定到某個 CPU 核心這一功能。

總結

由於隨著電腦技術的發展，CPU 與記憶體的訪問速度相差越來越多，如今差距已經高達好幾百倍了，所以 CPU 內部嵌入了 CPU Cache 組件，作為記憶體與 CPU 之間的快取層，CPU Cache 由於離 CPU 核心很近，所以訪問速度也是非常快的，但由於所需材料成本比較高，它不像記憶體動輒幾個 GB 大小，而是僅有幾十 KB 到 MB 大小。

當 CPU 訪問數據的時候，先是訪問 CPU Cache，如果快取命中的話，則直接返回數據，就不用每次都從記憶體讀取速度了。因此，快取命中率越高，程式碼的性能越好。

但需要注意的是，當 CPU 訪問數據時，如果 CPU Cache 沒有快取該數據，則會從記憶體讀取數據，但是並不是只讀一個數據，而是一次性讀取一塊一塊的數據存放到 CPU Cache 中，之後才會被 CPU 讀取。

記憶體地址映射到 CPU Cache 地址里的策略有很多種，其中比較簡單是直接映射 Cache，它巧妙的把記憶體地址拆分成「索引 + 組標記 + 偏移量」的方式，使得我們可以將很大的記憶體地址，映射到很小的 CPU Cache 地址里。

要想寫出讓 CPU 跑得更快的程式碼，就需要寫出快取命中率高的程式碼，CPU L1 Cache 分為數據快取和指令快取，因而需要分別提高它們的快取命中率：

對於數據快取，我們在遍曆數據的時候，應該按照記憶體布局的順序操作，這是因為 CPU Cache 是根據 CPU Cache Line 批量操作數據的，所以順序地操作連續記憶體數據時，性能能得到有效的提升；
對於指令快取，有規律的條件分支語句能夠讓 CPU 的分支預測器發揮作用，進一步提高執行的效率；

另外，對於多核 CPU 系統，執行緒可能在不同 CPU 核心來回切換，這樣各個核心的快取命中率就會受到影響，於是要想提高進程的快取命中率，可以考慮把執行緒綁定 CPU 到某一個 CPU 核心。

絮叨

哈嘍，我是小林，就愛圖解電腦基礎，如果覺得文章對你有幫助，歡迎分享給你的朋友，也給小林點個「贊」，這對小林非常重要，謝謝你們，給各位小姐姐小哥哥們抱拳了，我們下次見！

面試官：如何寫出讓 CPU 跑得更快的程式碼？

前言