如何在 C++ 代碼中提示編譯器某個分支的執行概率高？

01-03

GCC 對此有擴展：likely 和 unlikely。

if (likely(x)) { // 我覺得這裡概率高 } else { // 我覺得這裡概率低 }

見 https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html 的 __builtin_expect。likely 和 unlikely 是它的宏。

首先，C++是做不到提示分支預測的，Ｃ++層面處理的都是高級語言了，唯一能訪問到的層次就是指針（內存地址）。CPU層面的功能是需要彙編才能訪問的，C++內嵌彙編的方式取決於你用的編譯器。同樣，提示分支預測也是編譯器的功能，需要看對於的編譯器是否有這個功能，以及這個功能做到了什麼樣的程度。比如說GCC就有likely這樣的宏。

而通過彙編的方式操縱CPU分支的，是RISC的理念：即最簡化硬體設計，完全沒有分支預測器，或者只有最簡單的1bit分支預測器的時候，可以用彙編的方式改變不同分支結果時CPU的處理方式。我接觸過的MIPS中，早期的MIPS指令集（MIPS II）中，分支語句有其likely的變體。由於MIPS中，流水線對於彙編來說是可見的。分支後出現的分支延遲槽是需要程序員（編譯器）手動去填補的。

loop: inst 1 inst 2 ... blez t0, loop nop

其中，nop就是用於填充延遲槽的空白指令。而使用了likely變體後，可以寫成這樣：

loop: inst 1 inst 2 ... blezl t0, loop inst 1

使用分支指令的likely變體，意味著當分支偏向loop方向的時候，在延遲槽中允許的第一條指令結果可以提交，而當分支失敗的時候，第一條指令的結果被丟棄。

而現代的MIPS中，這個likely指令已經被移出指令集（MIPS32）了。實際上，分支的延遲槽已經不是MIPS剛誕生的時候那樣只有一個周期，不同的CPU可能有不同的實際延遲。而延遲槽填充只是作為語言特性保留下來。單就這個指令來說，僅僅在編譯器不能正確填充延遲槽的時候才有意義，而這個是很少出現的。隨著流水線的複雜化，要實現likely指令不容易，而實現了的獲益不明顯。特別是在多發射的現代超標量CPU上，分支延遲槽部分即便保留nop，由於有強大的分支預測器和預測執行（speculative execution），實際運作的時候也很容易被填充。使用likely指令的意義就沒有了，大多數時候還會有相反的作用。

拋開這些特殊的指令，從編譯器生成代碼的角度來說，無論代碼在分支中的順序怎麼樣子，遇到帶預測執行的CPU，他們的區別都可以被分支預測的結果抹平。

所以，請相信你的CPU的分支預測器（除非它特別弱），大部分時候，手動提示的效果是不如分支預測器的。

gcc內置的__builtin_expect

如果是VC++的話，直接使用optimize by profiling就好了，誰知道你指定的分支預測是否符合真實情況，為什麼不直接跑一段時間然後拿profiling的結果來優化呢。

告訴編譯器有兩種方法：

一種是大家說的編譯器內建宏，如gcc的__builtin_expect(!!(x), 1);

另一種是大家code編寫習慣（策略），比如不要在循環中嵌套較多的條件分支；合併分支條件；概率大的條件分支放前面；盡量使用排過序的數據；適當用goto和do while語句。

只這樣還是不夠的，編程還要考慮空間局部性原理，考慮使用寄存器和cache影響。

參考《深入理解計算機系統》

如果是GCC的話，可以使用gcov

編譯的時候加-fprofile-arcs -ftest-coverage

然後進行測試，測試全部結束以後，再導一下，就可以看到運行的次數了

「某個分支的執行概率高」，除非概率明顯高，否則不要試用這樣的功能。不同的分支的執行是相互對稱。某個分支優化，意味著其他的情況效率就降低了。如

if(Condition){ Case A; }else{ Case B; } 優化為： Case B; if(Condition){ Undo Case B; Case A; }