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 的.




留言

張貼留言

這個網誌中的熱門文章

岩窟中的聖母

-
圖片
在達文西的密碼一書中，中譯第161頁有提到 達文西接受一個教會組織「純淨受孕協會」所委託，該協會位於米蘭的 聖芳濟會教堂中，需要一幅 畫作為祭壇三聯板中間的那一幅。那些修女給了李奧納多精確的尺寸，以及期望的主題 - 聖母瑪莉亞，施洗者聖約翰幼嬰，大天使烏列，以及聖嬰耶穌，一起躲在一個洞窟中。雖然達文西遵照他們的要求畫了，但作品交出後，該協會卻大感驚恐。他在作 品中畫滿了引人爭議且不安的細節。 畫中是一個身穿藍袍坐著的聖母馬利亞，手臂攬著一名應該是耶穌的嬰孩。馬利亞的另一旁是大天使烏列，也 帶著一名應該是施洗者聖約翰的嬰孩。不過奇怪的是，畫面中並非一般情節中耶穌為聖約翰祝聖，而是聖約翰為耶穌祝聖……而耶穌服從於聖約翰的權威! 更令人不安的是，馬利亞一手舉在聖約翰的頭上，做出一個很明確的威脅手勢 - 他的手指看起來像鷹爪，正抓著一個看不見的頭。最後，最明顯也最駭人的畫面是: 就在馬利亞扭曲的手指下方，烏列比畫出一個切割的手勢 - 好像從馬利亞鷹爪般手指所抓著那個無形人頭的頸部劃過。 達文西最後擺平那個協會的方式，就是畫了第二幅給他們，在這幅「摻水版」的＜岩窟中的聖母＞中，每個人物的安排都比較正統。 我覺得滿有趣的，以下是我用google找到的二幅圖，二幅圖的名稱不同，但我用google的搜尋結果，似乎外國人也沒有細分這二張？有時候二個名字混用，名字用錯，或乾脆用括號把另一個名字加在後面。我猜他們可能也不少人根本不知道這回事。 圖：Madonna of the Rocks 圖：Virgin of the Rocks
閱讀完整內容

人生第一次

-
人生第一次的逕行錄取，應該也是唯一一次。其實我大約快一個月前，就已經博士班逕行錄取了，只是因為現在連碩士都不知道畢不畢得了業，就一直很不想提這件事。記得我大四上十二月左右，我正唸書準備考隔年三四月的碩士班筆試，得知一個唸交大應化系的同學已經免口試逕取清大化學所時，心中是多麼的羨慕，不用考試就算了，連口試都免了，他真的是強者，我無話可說~ 其實博士班要上我覺得不難，特別是自己學校想要上更是不難，因為內行的都知道真正難的不是錄取，而是畢業，也不知道為什麼，本校的畢業率比另外二間更低，我常覺得自己可能畢不了業。我一直覺得自己不是個會唸書的人，自從考完大學更是這樣覺得，有時候會覺得連我這種咖洨都可以唸到博士，台灣要沉淪了。。。哈 前幾天做夢夢到高中時的事，以前高中時國文要考一種奇怪的考卷，叫做傳統題，顧名思義就是它很傳統，所有的東西都是死背的，題目都是從課本上的題解與作者，解釋等，直接挖空要你填充，我高中這東西好像沒考過八十分以上，甚至還有考過二十三分，印象深刻，還被老師當著全班的面把考卷亮出來，痛罵我一頓。我夢到老師在我的考卷上寫"在唸什麼!!"，罵我不認真唸書，其實這件事情過去也是真的發生過，所以也不算是憑空夢到的，只能算是夢中回憶到這件事而已。國中時成績還算不差，常態分班的班上3~8名遊走，當時很多長輩，像是爸爸，或是一些老師，都會說"你很聰明，只是不用功"，一直到高中，都還是常會聽到這一句話。聯考考完後，我再也沒聽過這句話了，一來是大學也沒人那麼無聊在比成績，二來聯考都考爛了，也沒人會和你說這種話了。 大學時，我從大二開始變用功，大一下好像還三十幾名左右，大二上開始我就很努力的唸專業科目，馬上就變成了前十名。其實我當時並不是想讓自己的成績變好，根本也沒想過要讓自己成績變好，我只是很希望自己能夠變強一點，因為參與了Java討論區，常感覺到自己的渺小，我曾經因為一個演算法別人想得出來，我想不出來，而在床邊鬱悶了好幾天。我告訴自己，我再也不說"那個又不難，我也可以"這種話，我告訴自己如果我沒有做，我就不能說我也可以，因為我永遠不會去做。於是我當時養成一個習慣，不管是資料結構，或是演算法這種課，只要教了某個東西，我回家就會把它寫出來，寫成真正可以跑的程式，因為我只有這樣才能夠驗證自己是真正懂了這個東西，紙上談兵就如...
閱讀完整內容

小時候(1)

-
第一次接觸電腦，好像是小學四年級，我還記得當時的CPU是486DX-33，DX代表有浮點運算功能，而SX則沒有，當時花了四萬五，硬碟 40MB，記憶體是 4MB，單色螢幕。 當時家裡買電腦，是因為家裡是做生意的，賣家電用品，需要做存貨的管理，所以才買了這台電腦，而當時使用的會計軟體我還記得叫做"高格會計"，現在用Google可以查到一個叫做"高格亞翼"的公司，也是做這樣的會計套裝軟體，不知道是不是同一家。 對於一個小學四年級的小朋友來說，沒有比這個更新鮮的事了，電腦，多麼引人好奇的一個東西，當時的電腦沒有GUI，我使用的作業系統是MS-DOS 5.0，我第一個學會的指令是"dir"，雖然使用"dir"後出來的東西我都看不懂，但是我還是每天都樂於在電腦前面輸入"dir"，看著那畫面出現的英文字。 當時要使用中文，必須使用"倚天中文系統"，只要輸入ET3，就可以進入了，當時的開機自動執行批次檔(autoexec.bat)裡，就已經在最後呼叫了ET3.bat，所以只要開完機後，就會進入中文系統。 我家裡沒有什麼書，只有一本"輕輕鬆鬆學Basic"，那是我姐在高中時，上計算機概論用的課本，裡面有介紹Basic，但我完全不懂那是在幹嘛，但是我還是每天拿著那本書，照著書上的東西打看看，試試這台電腦會給我什麼樣的回應。 當然，多半我得不到回應，因為書上寫的東西都是在Basic下的命令，我在DOS Shell輸入是不會有反應的，多半會得到"Bad command or filename"，但有時候會有一點點不同，比如我輸入了書上的"FOR"，"PRINT"，"IF"，就不會出現"Bad command or filename"，而是出來一些我看不懂的英文，現在當然知道是說我語法錯誤，因為這些在Basic裡的關鍵字，在DOS Shell裡，也是一些可以用的指令。這對我來說已經是夠新奇了，充滿了期待，輸入不同的東西，我都期待著他會顯示什麼。於是我花了很多時間，想盡辦法要在這台電腦上玩出一點花樣。 有一天，我看著輸入"dir"後的畫...
閱讀完整內容