likely and unlikely in linux

Linux kernel source code 裡面常看到在 if 的條件裡加上 likely / unlikely 來暗示電腦 true or false 發生, 到底它是怎樣讓效率比較好的? 如果有人說這個是在"暗示處理器的 branch prediction", 這是錯的, 因為處理器的 branch predictor 是硬體機制, 我不確定有沒有辦法去修改, 但至少 likely / unlikely 完全不是這麼回事.

追了一下 kernel 的 source code 看到它是由 macro 定義的: 

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0) 

透過反組譯就可以查出 __builtin_expect 到底在做什麼 (*), 簡單說就是把

• 被暗示較有可能會執行到的 code 放在下面靠近的幾行 (pipeline 後續會抓進來)
• 被暗示較不會被行到的 code 放遠一點, 不幸發生再 jump 過去"

這麼做的好處是可以保持 pipeline 是滿的, 因為 jump 到遠一點的地方後, 該處的"後續指令"要重新抓, 那就得把目前 pipeline 裡的東西 flush 掉重抓, 自然效率是前者比較好了.

所以總結, 這只是 compiler 幫你排一下 (暗示 compiler 可能還貼切點), 看哪一個排法比較不會影響 pipeline 的效率, 和影響 branch predictor 是二回事.

* http://my.oschina.net/moooofly/blog/175019 (注意 code 當中 je 和 jne 跳到哪裡去了)
** http://stackoverflow.com/questions/248693/double-negation-in-c-code/249305#249305 ( __built_expect 二個驚嘆號算是一個小 trick, 叫做 double negation, 目的是快速的把 x 變 boolean 值)

/* Update: 插入人類語言解釋

"某甲和某乙二個人在講話, 某甲會把正在聊的話題, 後面幾句都先想好放在腦中, 如果不幸對方轉了話題, 甲只好拿出筆記本看看新話題的資料, 剛先想好的都白想了, 但大多數話題不轉的情況下, 聊天非常的 smooth"

反之,"某乙只想要聊李倩蓉案,就把李倩蓉案放在腦中, 其它的話題就放到筆記本裡去"...

*/

/*
Update 2 (2015/4/16)
有位學長和我討論, 他討為廣義上這還是一種 branch prediction, 所以後面增加了一些補述, 一併附上供參考
*/

Assumption:

1. Predict vs guess? 預測與猜測定義是否相同? 我們這裡先定義預測是有根據歷史記錄, 猜測是沒有根據的.
2. 從 Turing machine 構架來看, 程式是單純的 input, 只是一個 tape, 而設計出來的杜靈機本身有沒有對應"猜測往左或往右"的機制?

回頭看這個 gcc 編出來的程式, 以及它假設對應的硬體, 硬體裡完全沒有用到任何一個 bit 來紀錄過往 branch or not, 它永遠是抓下幾條指令進 pipeline, 即使遇到 je or jne 它也是一樣這樣抓, 這部份是一個 stateless design, 所以這裡我稱它在"猜測"而不是"預測", 或說"它永遠猜不會 branch, 不管怎樣".

而這個程式, 在假設硬體這部份完全沒有 stateful 設計下, 把"自己這個帶子 (tape) 排成有利於這機器", 你這樣看還會覺得它有在"預測"嗎?

在這樣的用詞下, 還有硬體就的確有個東西叫 branch predictor, 所以我覺得把它解釋成"寫程式的人根據自己的經驗法則, 排了這個帶子給一個無分支預測記憶的杜圖機"比較貼切.

終究要回歸到定義問題呀, 在人腦裡做了 prediction 做出了這個帶子, 但帶子本身和杜圖機本身是沒有在做 prediction 的.