從 Linux Kernel 觀察現代處理器特性 — 分支篇
前陣子在研究 IP Virtual Switch 時偶然看到了一個 Linux Kernel 的 Patch：[PATCH 00/79] netfilter: netfilter update
Patch 中出現了大量的 likely 與 unlikely macro，雖然我平常在公司並沒有參與 Linux Kernel 相關的專案開發，但出於好奇心，我還是在下班時間研究了一下這兩個 macro 的用途 XD
首先，上面問題的答案是：likely 與 unlikely 是 gcc 提供針對 CPU 分支的最佳化巨集：
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)兩者皆是利用 __builtin_expect(!!(x), n) 巨集實作，研究其原始碼我們得知該巨集會告知此條件（這裡指 x 變數）為 n 的機率較高，compiler 知道這件事情後，在編譯時就會將該條件後面的程式碼區段緊接在該條件之後：
int main(char *argv[], int argc)
{
if (likely (argc == 1))
foo();
else
bar();
}以上方的程式碼範例來說，我們告知 compiler：argc 的數值極有可能為 1，因此 compiler 會將 foo() 的程式碼區段（組合語言）緊接在該條件後方（同樣為組合語言，一般為 bne 這類的分支指令）。
相反的，如果將程式碼中的 likely 替換為 unlikely：
int main(char *argv[], int argc)
{
if (unlikely (argc == 1))
foo();
else
bar();
}經過 compiler 編譯後，bar 的程式碼區段將緊接在 if (argc == 1) 代表的區段後方。
補充：
或許有讀者會好奇：
__builtin_expect(!!(x), 1)中的!!(x)有什麼用途，這麼做的原因是 x 本身的數值不一定為 1 或 0，使用兩次 NOT 操作可以保證結果一定為 1 或 0，該手法常出現於 Linux Kernel 的原始碼。
看到這裡，你可能會好奇使用 likely 與 unlikely 這類的巨集對於現代處理器的執行有什麼影響？
筆者引用 How branches influence the performance of your code and what can you do about it? 一文中的測試結果，該測試會嘗試進行 1000 次的陣列搜尋，且該陣列有 100 萬個元件：
結果很遺憾，它對於現代處理器的執行效率上幾乎沒有幫助，原因是現代處理器基本上都帶有分支預測（Branch Prediction）的功能，處理器如果遇到分支相關的指令時，本身就有能力透過先前的結果預先載入需要執行的指令，這也類似於 likely 與 unlikely 巨集想要為我們做到的效果（使處理器載入較有可能被執行到的指令）。
補充：分支對於處理器的影響
現代處理器多半採用流水線的設計：
這樣的作法使處理器的每一個 stage 都能並行的處理，大量提高處理器消耗指令的效率。
那麼，Branch（分支）是什麼呢？
我們在程式碼中的條件操作經過 compiler 編譯為組合語言後，會變成各種的分支指令，這也代表處理器並不能保證它所載入的指令一定會被執行到（比如處理器載入了 x == 1 條件成立時會被執行的程式，但這次的結果 x 卻不為 1）。
基本上，處理器在執行到分支指令時，可能會採用以下列出的方式來應對：
- 暫停後續流水線的工作，直到分支的結果確定後載入對應的指令來執行。
- 處理器不會暫停流水線的工作，而是總是載入緊接在分支指令後的程式碼區段。
- 處理器會詢問分支預測器，根據判斷載入對應的程式碼區段。
在現代處理器中，第一種應對方式是完全不被採納的，為了等待一個指令的結果而造成整條流水線的停擺是最沒有效率的做法。然而，如果不暫停流水線就直接載入後續指令，仍有高機率載入到錯誤的指令，導致處理器必須要清空流水線。
而第二點僅會出現在一些低功耗的處理器（不配有分支預測功能）上，在這個情況下，文章前面的 likely 以及 unlikely 巨集就能提升處理器的執行效率。
最後的第三點是現代處理器普遍採納的設計，分支預測器會紀錄每一個程式碼區段的分支結果作為日後的預測依據，它分別解決了：
- 第一點造成的流水線停擺問題
- 降低第二種方式遇到載入錯誤指令的機率
如果讀者對分支預測感興趣，還可參考筆者於 IT 幫鐵人賽的一系列文章：
總結
Linux Kernel 的原始碼規模已達到非常人可及的高度，即便如此，我們仍可透過閱讀其子系統的部分程式碼學習到各式各樣的知識。以這篇文章探討的巨集來看，短短的兩行程式碼背後藏著現代處理器的設計問題，理解這些考量能夠幫助我們開發出更高效的程式。
之後筆者也會更新這類的入門文章，如果讀者有什麼問題與想法都歡迎留言跟我交流～！
