說明： 本文以stackoverflow上Why is it faster to process a sorted array than an unsorted array?為原型，翻譯了問題和高票回答并加入了大量補充說明，方便讀者理解。

背景

先來看段c++代碼，我們用256的模數隨機填充一個固定大小的大數組，然后對數組的一半元素求和：

#include <algorithm> 
#include <ctime> 
#include <iostream> 
 
int main() 
{ 
    // 隨機產生整數，用分區函數填充，以避免出現分桶不均 
    const unsigned arraySize = 32768; 
    int data[arraySize]; 
 
    for (unsigned c = 0; c < arraySize; ++c) 
        data[c] = std::rand() % 256; 
 
    // !!! 排序后下面的Loop運行將更快 
    std::sort(data, data + arraySize); 
 
    // 測試部分 
    clock_t start = clock(); 
    long long sum = 0; 
 
    for (unsigned i = 0; i < 100000; ++i) 
    { 
        // 主要計算部分，選一半元素參與計算 
        for (unsigned c = 0; c < arraySize; ++c) 
        { 
            if (data[c] >= 128) 
                sum += data[c]; 
        } 
    } 
 
    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; 
 
    std::cout << elapsedTime << std::endl; 
    std::cout << "sum = " << sum << std::endl; 
}  

編譯并運行：

g++ branch_prediction.cpp 
./a.out  

在我的macbook air上運行結果：

# 1. 取消std::sort(data, data + arraySize);的注釋，即先排序后計算 
10.218 
sum = 312426300000 
 
# 2. 注釋掉std::sort(data, data + arraySize);即不排序，直接計算 
29.6809 
sum = 312426300000  

由此可見，先排序后計算，運行效率有進3倍的提高。

為保證結論的可靠性， 我們再用java來測一遍：

import java.util.Arrays; 
import java.util.Random; 
 
public class Main 
{ 
    public static void main(String[] args) 
    { 
        // Generate data 
        int arraySize = 32768; 
        int data[] = new int[arraySize]; 
 
        Random rnd = new Random(0); 
        for (int c = 0; c < arraySize; ++c) 
            data[c] = rnd.nextInt() % 256; 
 
        // !!! With this, the next loop runs faster 
        Arrays.sort(data); 
 
        // Test 
        long start = System.nanoTime(); 
        long sum = 0; 
 
        for (int i = 0; i < 100000; ++i) 
        { 
            // Primary loop 
            for (int c = 0; c < arraySize; ++c) 
            { 
                if (data[c] >= 128) 
                    sum += data[c]; 
            } 
        } 
 
        System.out.println((System.nanoTime() - start) / 1000000000.0); 
        System.out.println("sum = " + sum); 
    } 
}  

在intellij idea中運行結果：

# 1. 先排序后計算 
5.549553 
sum = 155184200000 
# 2. 不排序直接結算 
15.527867 
sum = 155184200000  

也有三倍左右的差距。且java版要比c++版整體快近乎1倍?這應該是編譯時用了默認選項，gcc優化不夠的原因，后續再調查這個問題。

問題的提出

以上代碼在數組填充時已經加入了分區函數，充分保證填充值的隨機性，計算時也是按一半的元素來求和，所以不存在特例情況。而且，計算也完全不涉及到數據的有序性，即數組是否有序理論上對計算不會產生任何作用。在這樣的前提下，為什么排序后的數組要比未排序數組運行快3倍以上?

分析

想象一個鐵路分叉道口。

[[171601]]

 為了論證此問題，讓我們回到19世紀，那個遠距離無線通信還未普及的年代。你是鐵路交叉口的扳道工。當聽到火車快來了的時候，你無法猜測它應該朝哪個方向走。于是你叫停了火車，上前去問火車司機該朝哪個方向走，以便你能正確地切換鐵軌。

要知道，火車是非常龐大的，切急速行駛時有巨大的慣性。為了完成上述停車-問詢-切軌的一系列動作，火車需耗費大量時間減速，停車，重新開啟。

既然上述過車非常耗時，那是否有更好的方法?當然有!當火車即將行駛過來前，你可以猜測火車該朝哪個方向走。

• 如果猜對了，它直接通過，繼續前行。
• 如果猜錯了，車頭將停止，倒回去，你將鐵軌扳至反方向，火車重新啟動，駛過道口。

如果你不幸每次都猜錯了，那么火車將耗費大量時間停車-倒回-重啟。如果你很幸運，每次都猜對了呢?火車將從不停車，持續前行!

上述比喻可應用于處理器級別的分支跳轉指令里：

原程序：

if (data[c] >= 128) 
    sum += data[c];    

匯編碼：

cmp edx, 128 
jl SHORT $LN3@main 
add rbx, rdx 
$LN3@main:  

讓我們回到文章開頭的問題。現在假設你是處理器，當看到上述分支時，當你并不能決定該如何往下走，該如何做?只能暫停運行，等待之前的指令運行結束。然后才能繼續沿著正確地路徑往下走。

要知道，現代編譯器是非常復雜的，運行時有著非常長的pipelines， 減速和熱啟動將耗費巨量的時間。

那么，有沒有好的辦法可以節省這些狀態切換的時間呢?你可以猜測分支的下一步走向!

如果猜錯了，處理器要flush掉pipelines, 回滾到之前的分支，然后重新熱啟動，選擇另一條路徑。

如果猜對了，處理器不需要暫停，繼續往下執行。

如果每次都猜錯了，處理器將耗費大量時間在停止-回滾-熱啟動這一周期性過程里。如果僥幸每次都猜對了，那么處理器將從不暫停，一直運行至結束。

上述過程就是分支預測(branch prediction)。雖然在現實的道口鐵軌切換中，可以通過一個小旗子作為信號來判斷火車的走向，但是處理器卻無法像火車那樣去預知分支的走向--除非最后一次指令運行完畢。

那么處理器該采用怎樣的策略來用最小的次數來盡量猜對指令分支的下一步走向呢?答案就是分析歷史運行記錄： 如果火車過去90%的時間都是走左邊的鐵軌，本次軌道切換，你就可以猜測方向為左，反之，則為右。如果在某個方向上走過了3次，接下來你也可以猜測火車將繼續在這個方向上運行...

換句話說，你試圖通過歷史記錄，識別出一種隱含的模式并嘗試在后續鐵道切換的抉擇中繼續應用它。這和處理器的分支預測原理或多或少有點相似。

大多數應用都具有狀態良好的(well-behaved)分支，所以現代化的分支預測器一般具有超過90%的命中率。但是面對無法預測的分支，且沒有識別出可應用的的模式時，分支預測器就無用武之地了。

關于分支預測期，可參考維基百科相關詞條"Branch predictor" article on Wikipedia..

文首導致非排序數組相加耗時顯著增加的罪魁禍首便是if邏輯：

if (data[c] >= 128) 
    sum += data[c];  

注意到data數組里的元素是按照0-255的值被均勻存儲的(類似均勻的分桶)。數組data有序時，前面一半元素的迭代將不會進入if-statement, 超過一半時，元素迭代將全部進入if-statement.

這樣的持續朝同一個方向切換的迭代對分支預測器來說是非常友好的，前半部分元素迭代完之后，后續迭代分支預測器對分支方向的切換預測將全部正確。

簡單地分析一下：有序數組的分支預測流程：

T = 分支命中 
N = 分支沒有命中 
 
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... 
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ... 
 
       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (非常容易預測)  

無序數組的分支預測流程：

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ... 
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ... 
 
       = TTNTTTTNTNNTTTN ...   (完全隨機--無法預測)  

在本例中，由于data數組元素填充的特殊性，決定了分支預測器在未排序數組迭代過程中將有50%的錯誤命中率，因而執行完整個sum操作將會耗時更多。

優化

利用位運算取消分支跳轉。基本知識：

|x| >> 31 = 0 # 非負數右移31為一定為0 
~(|x| >> 31) = -1 # 0取反為-1 
 
-|x| >> 31 = -1 # 負數右移31為一定為0xffff = -1 
~(-|x| >> 31) = 0 # -1取反為0 
 
-1 = 0xffff 
-1 & x = x # 以-1為mask和任何數求與，值不變  

故分支判斷可優化為：

int t = (data[c] - 128) >> 31; # statement 1 
sum += ~t & data[c]; # statement 2  

分析：

1. data[c] < 128, 則statement 1值為: 0xffff = -1, statement 2等號右側值為: 0 & data[c] == 0;
2. data[c] >= 128, 則statement 1值為: 0, statement 2等號右側值為: ~0 & data[c] == -1 & data[c] == 0xffff & data[c] == data[c];

故上述位運算實現的sum邏輯完全等價于if-statement, 更多的位運算hack操作請參見bithacks.

若想避免移位操作，可以使用如下方式：

int t=-((data[c]>=128)); # generate the mask 
sum += ~t & data[c]; # bitwise AND  

結論

• 使用分支預測: 是否排序嚴重影響performance
• 使用bithack: 是否排序對performance無顯著影響

這個例子告訴給我們啟示: 在大規模循環邏輯中要盡量避免數據強依賴的分支(data-dependent branching).

補充知識

Pipeline

先簡單說明一下CPU的instruction pipeline(指令流水線)，以下簡稱pipeline。 Pipieline假設程序運行時有一連串指令要被運行，將程序運行劃分成幾個階段，按照一定的順序并行處理之，這樣便能夠加速指令的通過速度。

絕大多數pipeline都由時鐘頻率(clock)控制，在數字電路中，clock控制邏輯門電路(logical cicuit)和觸發器(trigger), 當受到時鐘頻率觸發時，觸發器得到新的數值，并且邏輯門需要一段時間來解析出新的數值，而當受到下一個時鐘頻率觸發時觸發器又得到新的數值，以此類推。

而借由邏輯門分散成很多小區塊，再讓觸發器鏈接這些小區塊組，使邏輯門輸出正確數值的時間延遲得以減少，這樣一來就可以減少指令運行所需要的周期。 這對應Pipeline中的各個stages。

一般的pipeline有四個執行階段(execuate stage): 讀取指令(Fetch) -> 指令解碼(Decode) -> 運行指令(Execute) -> 寫回運行結果(Write-back).

分支預測器

分支預測器是一種數字電路，在分支指令執行前，猜測哪一個分支會被執行，能顯著提高pipelines的性能。

條件分支通常有兩路后續執行分支，not token時,跳過接下來的JMP指令，繼續執行， token時，執行JMP指令，跳轉到另一塊程序內存去執行。

為了說明這個問題，我們先考慮如下問題。

沒有分支預測器會怎樣?

加入沒有分支預測器，處理器會等待分支指令通過了pipeline的執行階段(execuate stage)才能把下一條指令送入pipeline的fetch stage。

這會造成流水線停頓(stalled)或流水線冒泡(bubbling)或流水線打嗝(hiccup)，即在流水線中生成一個沒有實效的氣泡， 如下圖所示：

圖中一個氣泡在編號為3的始終頻率中產生，指令運行被延遲。

Stream hiccup現象在早期的RISC體系結構處理器中常見。

有分支預測期的pipeline

我們來看分支預測器在條件分支跳轉中的應用。條件分支通常有兩路后續執行分支，not token時,跳過接下來的JMP指令，繼續執行， token時，執行JMP指令，跳轉到另一塊程序內存去執行。

加入分支預測器后，為避免pipeline停頓(stream stalled)，其會猜測兩路分支哪一路最有可能執行，然后投機執行，如果猜錯，則流水線中投機執行中間結果全部拋棄，重新獲取正確分支路線上的指令執行。可見，錯誤的預測會導致程序執行的延遲。

由前面可知，Pipeline執行主要涉及Fetch, Decode, Execute, Write-back幾個stages, 分支預測失敗會浪費Write-back之前的流水線級數。現代CPU流水線級數非常長，分支預測失敗可能會損失20個左右的時鐘周期，因此對于復雜的流水線，好的分支預測器非常重要。

常見的分支預測器

• 靜態分支預測器

靜態分支預測器有兩個解碼周期，分別評價分支，解碼。即在分支指令執行前共經歷三個時鐘周期。詳情見圖：

• 雙模態預測器(bimodal predictor)

也叫飽和計數器，是一個四狀態狀態機. 四個狀態對應兩個選擇: token, not token， 每個選擇有兩個狀態區分強弱：strongly,weakly。分別是Strongly not taken，Weakly not taken, Weakly taken, Strongly taken。

狀態機工作原理圖如下：

圖左邊兩個狀態為不采納(not token)，右邊兩個為采納(token)。由not token到token中間有兩個漸變狀態。由紅色到綠色翻轉需要連續兩次分支選擇。

技術實現上可用兩個二進制位來表示，00, 01, 10, 11分別對應strongly not token, weakly not token, weakly token, strongly token。 一個判斷兩個分支預測規則是否改變的簡單方法便是判斷這個二級制狀態高位是否跳變。高位從0變為1， 強狀態發生翻轉，則下一個分支指令預測從not token變為token，反之亦然。

據評測，雙模態預測器的正確率可達到93.5%。預測期一般在分支指令解碼前起作用。

其它常見分支預測器如兩級自適應預測器，局部/全局分支預測器，融合分支預測器，Agree預測期，神經分支預測器等。