CPU分支預測——BPU——性能小議

BPU是CPU中，對性能影響最常見的組件，性能在不同的場景下受影響的單元不一樣（Intel 管這個受影響的單元位Slot），但是BPU作為分支預測的功能，屬於一個邏輯層面的性能提高，不是技術層面的。邏輯層面的一個提高可能就相當於技術層面的很多細緻的提升，這也是為什麼很多程序的性能優化最好的方式是修改邏輯是一個道理，只是更加下沉一些。

BPU的一個預測錯誤會導致很大的性能懲罰，因為BPU的一個決策涉及到真實的代碼家在，解碼，甚至執行。BPU如果預測對了，被提前載入的代碼，甚至提前執行的代碼就會直接生效。生效這個操作叫Retire，是CPU微架構的Backend中一個很重要的組件，它將指令執行的結果真實的去影響寄存器，把結果反映到寄存器上。也就是這一步一單執行，這個指令在CPU外部看，就是已經執行了。而BPU的代碼，在不確定分支的情況下，是不可能到達Retire這一步，也就是說越晚證明BPU預測的解決是錯誤的，就會導致越多的CPU額外開銷來執行BPU錯誤預測的指令。

所以編寫代碼讓BPU能夠準確的進行預測是非常重要的。Intel並沒有把這個問題徹底的甩給程序員，而是添加了一個BPB（Branch Prediction Buffer）組件，來緩存分支預測的結果。這個BPB很小，所以BPB的作用在大部分情況下是無法看出來的。兩個情況比較容易使得BPB的使用效果提高，一個是循環裡面的判斷，另外一個是高頻率的演算法執行會頻繁觸及到同一個判斷。總之就是同一個分支被頻繁執行的時候。之所以頻繁執行會得到優化，是因為一個事實是同一個分支的判斷結果一般不是50%的，而是更有可能去到某一個分支。如果在統計上更有可能去到某一個分支，那麼在連續的兩次分支判斷的時候，同一個分支就會被更高概率的選中。BPU就是基於如此的事實，一旦摸一個分支被頻繁執行，並且選擇上不是50%，BPB就會起到加速分支預測的作用。因為我們可以想像BPU所進行的分支預測並不是一個簡單的開銷，而必須要涉及到一些緩存申請和釋放，硬體資源的額外佔用等問題，如果有了BPB命中，這些額外操作相當於直接節省掉了。

從BPB中也可以看到，CPU中的加速組件的局限性，並不是每個加速組件在所有的場景都有意義，大部分的加速組件都是在特定的場景下有意義。但是CPU硬體上有個好處，它可以硬體並行的去執行很多操作。並不會受限於軟體上一個操作不完成就不能執行下一個操作的局限。所以添加一個組件有提高更好，沒有提高在大部分情況下也不會有太大的性能問題，最多是提高無效。另外一個功耗損失也是一方面。

BPU的分支預測是有演算法的，如果在BPB中命中，會直接採用BPB中的分支選擇結果，但是如果BPB沒有命中，就會執行靜態分支預測演算法。這個演算法雖然說是CPU內部的硬體演算法，但是如果在編寫軟體的時候能夠提前知道這個演算法，就會順著這個演算法來寫邏輯，能達到一個比較高的性能提升。

BPU的分支預測演算法很簡單，if塊里的邏輯BPU默認不命中，而是去命中if後面的邏輯。循環結束的時候默認命中循環的開始，而不是循環後面的內容。直接跳轉例如call，jmp，ret等都是直接命中結果的，這個是確定性的判斷，條件跳轉的情況，例如jc（在判斷某個值符合特定的情況下的跳轉指令），BPU的預測結果是不命中跳轉，而是選擇順序執行的分支預測結果。

所以我們在寫邏輯的時候if內部的邏輯都應當是不常進入的（你可以通過likely和unlikely關鍵字手動的指明概率讓編譯器去幫你做BPU的適配調整）。或者是如果就是要在if內部的塊寫概率比較大的代碼，可以在緊接著if之後的塊執行之前添加UD2指令，這個指令能讓CPU進入錯誤狀態，使得分支預測暫停。如此BPU相當於臨時停止工作（反正就算工作很大概率也是錯的）。

還有一個情況是在編程語言的switch語法的情況下，會有很多可能的分支選擇，這個時候分支預測BPU會很難選，預測正確的概率是非常低的。在switch的場景下，如果想要分支預測儘可能的提高概率，應該把概率比較高的分支可能單獨提取出來，寫成if，把其他分支概率差不多的分支寫成switch內部語句。如此相當於通過增加if來換取分支預測正確的概率。也就是說switch語法適用於各個分支選擇概率類似的情況，如果不滿足，應當單獨寫if語法以提高分支預測的正確率。

要注意的是，Core這個微架構就沒有使用這個靜態預測的演算法，如果按照這個思路去在Core上寫邏輯，很可能導致不一樣的性能結果。當然，功能結果是怎麼寫都對的，邏輯對，結果肯定對。但是性能結果卻是跟平台相關的。如此多的複雜性的情況下，這也是一個編譯器存在的原因。編譯器的存在消弭了這種不一致性，使得每種不同的體系架構都能儘可能的優化得到一個優化之後的結果。對性能追求到這個地步的應用，都已經到了非常極致的層面，實際中除非超大規模計算集群有這種需求，大部分的高性能場景都可以通過上層的一些演算法優化或者邏輯優化來達到更好的效果。