轉(zhuǎn)自：小林coding

前言

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

CPU 內(nèi)部嵌入了 CPU Cache（高速緩存），它的存儲容量很小，但是離 CPU 核心很近，所以緩存的讀寫速度是極快的，那么如果 CPU 運(yùn)算時，直接從 CPU Cache 讀取數(shù)據(jù)，而不是從內(nèi)存的話，運(yùn)算速度就會很快。

但是，大多數(shù)人不知道 CPU Cache 的運(yùn)行機(jī)制，以至于不知道如何才能夠?qū)懗瞿軌蚺浜?CPU Cache 工作機(jī)制的代碼，一旦你掌握了它，你寫代碼的時候，就有新的優(yōu)化思路了。

那么，接下來我們就來看看，CPU Cache 到底是什么樣的，是如何工作的呢，又該寫出讓 CPU 執(zhí)行更快的代碼呢？

正文

CPU Cache 有多快？

你可能會好奇為什么有了內(nèi)存，還需要 CPU Cache？根據(jù)摩爾定律，CPU 的訪問速度每 18 個月就會翻倍，相當(dāng)于每年增長 60% 左右，內(nèi)存的速度當(dāng)然也會不斷增長，但是增長的速度遠(yuǎn)小于 CPU，平均每年只增長 7% 左右。于是，CPU 與內(nèi)存的訪問性能的差距不斷拉大。

到現(xiàn)在，一次內(nèi)存訪問所需時間是200~300多個時鐘周期，這意味著 CPU 和內(nèi)存的訪問速度已經(jīng)相差200~300多倍了。

為了彌補(bǔ) CPU 與內(nèi)存兩者之間的性能差異，就在 CPU 內(nèi)部引入了 CPU Cache，也稱高速緩存。

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

由于 CPU Cache 所使用的材料是 SRAM，價格比內(nèi)存使用的 DRAM 高出很多，在當(dāng)今每生產(chǎn) 1 MB 大小的 CPU Cache 需要 7 美金的成本，而內(nèi)存只需要 0.015 美金的成本，成本方面相差了 466 倍，所以 CPU Cache 不像內(nèi)存那樣動輒以 GB 計算，它的大小是以 KB 或 MB 來計算的。

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

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

另外，你也會注意到，L3 Cache 比 L1 Cache 和 L2 Cache 大很多，這是因?yàn)?strong>L1 Cache 和 L2 Cache 都是每個 CPU 核心獨(dú)有的，而 L3 Cache 是多個 CPU 核心共享的。

程序執(zhí)行時，會先將內(nèi)存中的數(shù)據(jù)加載到共享的 L3 Cache 中，再加載到每個核心獨(dú)有的 L2 Cache，最后進(jìn)入到最快的 L1 Cache，之后才會被 CPU 讀取。它們之間的層級關(guān)系，如下圖：

越靠近 CPU 核心的緩存其訪問速度越快，CPU 訪問 L1 Cache 只需要2~4個時鐘周期，訪問 L2 Cache 大約10~20個時鐘周期，訪問 L3 Cache 大約20~60個時鐘周期，而訪問內(nèi)存速度大概在200~300個 時鐘周期之間。如下表格：

所以，CPU 從 L1 Cache 讀取數(shù)據(jù)的速度，相比從內(nèi)存讀取的速度，會快100多倍。

CPU Cache 的數(shù)據(jù)結(jié)構(gòu)和讀取過程是什么樣的？

CPU Cache 的數(shù)據(jù)是從內(nèi)存中讀取過來的，它是以一小塊一小塊讀取數(shù)據(jù)的，而不是按照單個數(shù)組元素來讀取數(shù)據(jù)的，在 CPU Cache 中的，這樣一小塊一小塊的數(shù)據(jù)，稱為Cache Line（緩存塊）。

你可以在你的 Linux 系統(tǒng)，用下面這種方式來查看 CPU 的 Cache Line，你可以看我服務(wù)器的 L1 Cache Line 大小是 64 字節(jié)，也就意味著L1 Cache 一次載入數(shù)據(jù)的大小是 64 字節(jié)。

比如，有一個int array[100]的數(shù)組，當(dāng)載入array[0]時，由于這個數(shù)組元素的大小在內(nèi)存只占 4 字節(jié)，不足 64 字節(jié)，CPU 就會順序加載數(shù)組元素到array[15]，意味著array[0]~array[15]數(shù)組元素都會被緩存在 CPU Cache 中了，因此當(dāng)下次訪問這些數(shù)組元素時，會直接從 CPU Cache 讀取，而不用再從內(nèi)存中讀取，大大提高了 CPU 讀取數(shù)據(jù)的性能。

事實(shí)上，CPU 讀取數(shù)據(jù)的時候，無論數(shù)據(jù)是否存放到 Cache 中，CPU 都是先訪問 Cache，只有當(dāng) Cache 中找不到數(shù)據(jù)時，才會去訪問內(nèi)存，并把內(nèi)存中的數(shù)據(jù)讀入到 Cache 中，CPU 再從 CPU Cache 讀取數(shù)據(jù)。

這樣的訪問機(jī)制，跟我們使用「內(nèi)存作為硬盤的緩存」的邏輯是一樣的，如果內(nèi)存有緩存的數(shù)據(jù)，則直接返回，否則要訪問龜速一般的硬盤。

那 CPU 怎么知道要訪問的內(nèi)存數(shù)據(jù)，是否在 Cache 里？如果在的話，如何找到 Cache 對應(yīng)的數(shù)據(jù)呢？我們從最簡單、基礎(chǔ)的直接映射 Cache（Direct Mapped Cache）說起，來看看整個 CPU Cache 的數(shù)據(jù)結(jié)構(gòu)和訪問邏輯。

前面，我們提到 CPU 訪問內(nèi)存數(shù)據(jù)時，是一小塊一小塊數(shù)據(jù)讀取的，具體這一小塊數(shù)據(jù)的大小，取決于coherency_line_size的值，一般 64 字節(jié)。在內(nèi)存中，這一塊的數(shù)據(jù)我們稱為內(nèi)存塊（Bock），讀取的時候我們要拿到數(shù)據(jù)所在內(nèi)存塊的地址。

對于直接映射 Cache 采用的策略，就是把內(nèi)存塊的地址始終「映射」在一個 CPU Line（緩存塊） 的地址，至于映射關(guān)系實(shí)現(xiàn)方式，則是使用「取模運(yùn)算」，取模運(yùn)算的結(jié)果就是內(nèi)存塊地址對應(yīng)的 CPU Line（緩存塊） 的地址。

舉個例子，內(nèi)存共被劃分為 32 個內(nèi)存塊，CPU Cache 共有 8 個 CPU Line，假設(shè) CPU 想要訪問第 15 號內(nèi)存塊，如果 15 號內(nèi)存塊中的數(shù)據(jù)已經(jīng)緩存在 CPU Line 中的話，則是一定映射在 7 號 CPU Line 中，因?yàn)?5 % 8的值是 7。

機(jī)智的你肯定發(fā)現(xiàn)了，使用取模方式映射的話，就會出現(xiàn)多個內(nèi)存塊對應(yīng)同一個 CPU Line，比如上面的例子，除了 15 號內(nèi)存塊是映射在 7 號 CPU Line 中，還有 7 號、23 號、31 號內(nèi)存塊都是映射到 7 號 CPU Line 中。

因此，為了區(qū)別不同的內(nèi)存塊，在對應(yīng)的 CPU Line 中我們還會存儲一個組標(biāo)記（Tag）。這個組標(biāo)記會記錄當(dāng)前 CPU Line 中存儲的數(shù)據(jù)對應(yīng)的內(nèi)存塊，我們可以用這個組標(biāo)記來區(qū)分不同的內(nèi)存塊。

除了組標(biāo)記信息外，CPU Line 還有兩個信息：

一個是，從內(nèi)存加載過來的實(shí)際存放數(shù)據(jù)（Data）。

另一個是，有效位（Valid bit），它是用來標(biāo)記對應(yīng)的 CPU Line 中的數(shù)據(jù)是否是有效的，如果有效位是 0，無論 CPU Line 中是否有數(shù)據(jù)，CPU 都會直接訪問內(nèi)存，重新加載數(shù)據(jù)。

CPU 在從 CPU Cache 讀取數(shù)據(jù)的時候，并不是讀取 CPU Line 中的整個數(shù)據(jù)塊，而是讀取 CPU 所需要的一個數(shù)據(jù)片段，這樣的數(shù)據(jù)統(tǒng)稱為一個字（Word）。那怎么在對應(yīng)的 CPU Line 中數(shù)據(jù)塊中找到所需的字呢？答案是，需要一個偏移量（Offset）。

因此，一個內(nèi)存的訪問地址，包括組標(biāo)記、CPU Line 索引、偏移量這三種信息，于是 CPU 就能通過這些信息，在 CPU Cache 中找到緩存的數(shù)據(jù)。而對于 CPU Cache 里的數(shù)據(jù)結(jié)構(gòu)，則是由索引 + 有效位 + 組標(biāo)記 + 數(shù)據(jù)塊組成。

如果內(nèi)存中的數(shù)據(jù)已經(jīng)在 CPU Cahe 中了，那 CPU 訪問一個內(nèi)存地址的時候，會經(jīng)歷這 4 個步驟：

根據(jù)內(nèi)存地址中索引信息，計算在 CPU Cahe 中的索引，也就是找出對應(yīng)的 CPU Line 的地址；

找到對應(yīng) CPU Line 后，判斷 CPU Line 中的有效位，確認(rèn) CPU Line 中數(shù)據(jù)是否是有效的，如果是無效的，CPU 就會直接訪問內(nèi)存，并重新加載數(shù)據(jù)，如果數(shù)據(jù)有效，則往下執(zhí)行；

對比內(nèi)存地址中組標(biāo)記和 CPU Line 中的組標(biāo)記，確認(rèn) CPU Line 中的數(shù)據(jù)是我們要訪問的內(nèi)存數(shù)據(jù)，如果不是的話，CPU 就會直接訪問內(nèi)存，并重新加載數(shù)據(jù)，如果是的話，則往下執(zhí)行；

根據(jù)內(nèi)存地址中偏移量信息，從 CPU Line 的數(shù)據(jù)塊中，讀取對應(yīng)的字。

到這里，相信你對直接映射 Cache 有了一定認(rèn)識，但其實(shí)除了直接映射 Cache 之外，還有其他通過內(nèi)存地址找到 CPU Cache 中的數(shù)據(jù)的策略，比如全相連 Cache （Fully Associative Cache）、組相連 Cache （Set Associative Cache）等，這幾種策策略的數(shù)據(jù)結(jié)構(gòu)都比較相似，我們理解流直接映射 Cache 的工作方式，其他的策略如果你有興趣去看，相信很快就能理解的了。

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

我們知道 CPU 訪問內(nèi)存的速度，比訪問 CPU Cache 的速度慢了 100 多倍，所以如果 CPU 所要操作的數(shù)據(jù)在 CPU Cache 中的話，這樣將會帶來很大的性能提升。訪問的數(shù)據(jù)在 CPU Cache 中的話，意味著緩存命中，緩存命中率越高的話，代碼的性能就會越好，CPU 也就跑的越快。

于是，「如何寫出讓 CPU 跑得更快的代碼？」這個問題，可以改成「如何寫出 CPU 緩存命中率高的代碼？」。

在前面我也提到， L1 Cache 通常分為「數(shù)據(jù)緩存」和「指令緩存」，這是因?yàn)?CPU 會別處理數(shù)據(jù)和指令，比如1+1=2這個運(yùn)算，+就是指令，會被放在「指令緩存」中，而輸入數(shù)字1則會被放在「數(shù)據(jù)緩存」里。

因此，我們要分開來看「數(shù)據(jù)緩存」和「指令緩存」的緩存命中率。

如何提升數(shù)據(jù)緩存的命中率？

假設(shè)要遍歷二維數(shù)組，有以下兩種形式，雖然代碼執(zhí)行結(jié)果是一樣，但你覺得哪種形式效率最高呢？為什么高呢？

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

之所以有這么大的差距，是因?yàn)槎S數(shù)組array所占用的內(nèi)存是連續(xù)的，比如長度N的指是2的話，那么內(nèi)存中的數(shù)組元素的布局順序是這樣的：

形式一用array[i][j]訪問數(shù)組元素的順序，正是和內(nèi)存中數(shù)組元素存放的順序一致。當(dāng) CPU 訪問array[0][0]時，由于該數(shù)據(jù)不在 Cache 中，于是會「順序」把跟隨其后的 3 個元素從內(nèi)存中加載到 CPU Cache，這樣當(dāng) CPU 訪問后面的 3 個數(shù)組元素時，就能在 CPU Cache 中成功地找到數(shù)據(jù)，這意味著緩存命中率很高，緩存命中的數(shù)據(jù)不需要訪問內(nèi)存，這便大大提高了代碼的性能。

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

你可以看到，訪問的方式跳躍式的，而不是順序的，那么如果 N 的數(shù)值很大，那么操作array[j][i]時，是沒辦法把a(bǔ)rray[j+1][i]也讀入到 CPU Cache 中的，既然array[j+1][i]沒有讀取到 CPU Cache，那么就需要從內(nèi)存讀取該數(shù)據(jù)元素了。很明顯，這種不連續(xù)性、跳躍式訪問數(shù)據(jù)元素的方式，可能不能充分利用到了 CPU Cache 的特性，從而代碼的性能不高。

那訪問array[0][0]元素時，CPU 具體會一次從內(nèi)存中加載多少元素到 CPU Cache 呢？這個問題，在前面我們也提到過，這跟 CPU Cache Line 有關(guān)，它表示CPU Cache 一次性能加載數(shù)據(jù)的大小，可以在 Linux 里通過coherency_line_size配置查看 它的大小，通常是 64 個字節(jié)。

也就是說，當(dāng) CPU 訪問內(nèi)存數(shù)據(jù)時，如果數(shù)據(jù)不在 CPU Cache 中，則會一次性會連續(xù)加載 64 字節(jié)大小的數(shù)據(jù)到 CPU Cache，那么當(dāng)訪問array[0][0]時，由于該元素不足 64 字節(jié)，于是就會往后順序讀取array[0][0]~array[0][15]到 CPU Cache 中。順序訪問的array[i][j]因?yàn)槔昧诉@一特點(diǎn)，所以就會比跳躍式訪問的array[j][i]要快。

因此，遇到這種遍歷數(shù)組的情況時，按照內(nèi)存布局順序訪問，將可以有效的利用 CPU Cache 帶來的好處，這樣我們代碼的性能就會得到很大的提升，

如何提升指令緩存的命中率？

提升數(shù)據(jù)的緩存命中率的方式，是按照內(nèi)存布局順序訪問，那針對指令的緩存該如何提升呢？

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

接下來，對這個數(shù)組做兩個操作：

第一個操作，循環(huán)遍歷數(shù)組，把小于 50 的數(shù)組元素置為 0；

第二個操作，將數(shù)組排序；

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

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

當(dāng)數(shù)組中的元素是隨機(jī)的，分支預(yù)測就無法有效工作，而當(dāng)數(shù)組元素都是順序的，分支預(yù)測器會動態(tài)地根據(jù)歷史命中數(shù)據(jù)對未來進(jìn)行預(yù)測，這樣命中率就會很高。

因此，先排序再遍歷速度會更快，這是因?yàn)榕判蛑螅瑪?shù)字是從小到大的，那么前幾次循環(huán)命中if < 50?的次數(shù)會比較多，于是分支預(yù)測就會緩存?if?里的?array[i] = 0?指令到 Cache 中，后續(xù) CPU 執(zhí)行該指令就只需要從 Cache 讀取就好了。

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

實(shí)際上，CPU 自身的動態(tài)分支預(yù)測已經(jīng)是比較準(zhǔn)的了，所以只有當(dāng)非常確信 CPU 預(yù)測的不準(zhǔn)，且能夠知道實(shí)際的概率情況時，才建議使用這兩種宏。

如果提升多核 CPU 的緩存命中率？

在單核 CPU，雖然只能執(zhí)行一個進(jìn)程，但是操作系統(tǒng)給每個進(jìn)程分配了一個時間片，時間片用完了，就調(diào)度下一個進(jìn)程，于是各個進(jìn)程就按時間片交替地占用 CPU，從宏觀上看起來各個進(jìn)程同時在執(zhí)行。

而現(xiàn)代 CPU 都是多核心的，進(jìn)程可能在不同 CPU 核心來回切換執(zhí)行，這對 CPU Cache 不是有利的，雖然 L3 Cache 是多核心之間共享的，但是 L1 和 L2 Cache 都是每個核心獨(dú)有的，如果一個進(jìn)程在不同核心來回切換，各個核心的緩存命中率就會受到影響，相反如果進(jìn)程都在同一個核心上執(zhí)行，那么其數(shù)據(jù)的 L1 和 L2 Cache 的緩存命中率可以得到有效提高，緩存命中率高就意味著 CPU 可以減少訪問 內(nèi)存的頻率。

當(dāng)有多個同時執(zhí)行「計算密集型」的線程，為了防止因?yàn)榍袚Q到不同的核心，而導(dǎo)致緩存命中率下降的問題，我們可以把線程綁定在某一個 CPU 核心上，這樣性能可以得到非?？捎^的提升。

在 Linux 上提供了sched_setaffinity方法，來實(shí)現(xiàn)將線程綁定到某個 CPU 核心這一功能。

總結(jié)

由于隨著計算機(jī)技術(shù)的發(fā)展，CPU 與 內(nèi)存的訪問速度相差越來越多，如今差距已經(jīng)高達(dá)好幾百倍了，所以 CPU 內(nèi)部嵌入了 CPU Cache 組件，作為內(nèi)存與 CPU 之間的緩存層，CPU Cache 由于離 CPU 核心很近，所以訪問速度也是非?？斓?，但由于所需材料成本比較高，它不像內(nèi)存動輒幾個 GB 大小，而是僅有幾十 KB 到 MB 大小。

當(dāng) CPU 訪問數(shù)據(jù)的時候，先是訪問 CPU Cache，如果緩存命中的話，則直接返回數(shù)據(jù)，就不用每次都從內(nèi)存讀取速度了。因此，緩存命中率越高，代碼的性能越好。

但需要注意的是，當(dāng) CPU 訪問數(shù)據(jù)時，如果 CPU Cache 沒有緩存該數(shù)據(jù)，則會從內(nèi)存讀取數(shù)據(jù)，但是并不是只讀一個數(shù)據(jù)，而是一次性讀取一塊一塊的數(shù)據(jù)存放到 CPU Cache 中，之后才會被 CPU 讀取。

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

要想寫出讓 CPU 跑得更快的代碼，就需要寫出緩存命中率高的代碼，CPU L1 Cache 分為數(shù)據(jù)緩存和指令緩存，因而需要分別提高它們的緩存命中率：

對于數(shù)據(jù)緩存，我們在遍歷數(shù)據(jù)的時候，應(yīng)該按照內(nèi)存布局的順序操作，這是因?yàn)?CPU Cache 是根據(jù) CPU Cache Line 批量操作數(shù)據(jù)的，所以順序地操作連續(xù)內(nèi)存數(shù)據(jù)時，性能能得到有效的提升；

對于指令緩存，有規(guī)律的條件分支語句能夠讓 CPU 的分支預(yù)測器發(fā)揮作用，進(jìn)一步提高執(zhí)行的效率；

另外，對于多核 CPU 系統(tǒng)，線程可能在不同 CPU 核心來回切換，這樣各個核心的緩存命中率就會受到影響，于是要想提高進(jìn)程的緩存命中率，可以考慮把線程綁定 CPU 到某一個 CPU 核心。

原文標(biāo)題：面試官：如何寫出讓 CPU 跑得更快的代碼？

文章出處：【微信公眾號：Linux愛好者】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq