淺談分支預測、流水線與條件轉移

一、一個問題

在StackOverflow上有這么一個問題 Why is processing a sorted array faster than an unsorted array? 。例子中，對一個數組進行條件求和，在排序前和排序后，性能有很大的差別。原始的例子是C++和Java的，這里將其換成了C# ：

static void Main(string[] args)
{
    // Generate data
    int arraySize;
    int[] data;
    Random rnd;

    arraySize = 32768;
    data = new int[arraySize];

    rnd = new Random(0);
    for (int c = 0; c < arraySize; ++c)
        data[c] = rnd.Next(256);

    // Test
    long sum = 0;
    CodeTimer.Time("unsorted array", 100000, () =>
    {
        for (int c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    });

    Array.Sort(data);

    sum = 0;
    CodeTimer.Time("sorted array", 100000, () =>
    {
        for (int c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    });
    Console.ReadKey();
}

代碼中首先初始化了一個 32768大小的int型數組，給這個數組的每個元素隨機賦予0-256之間的值，然后對該數組中大于128部分的數據進行求和，并將這個過程累加100000次。然后分別測量數組在排序前和排序后的 耗時。 這里使用了老趙的CodeTimer工具來，本人機器Xeon? E3-1230 v3@3.30GHz，在debug條件下，結果如下：

在release條件下，結果如下：

然后作者提出了問題，為什么僅僅對數據進行了排序，處理速度就快了將近一倍還要多呢？

排名第一的回答，解釋到是由于分支預測錯誤導致的性能懲罰，所以會產生性能的差別。要解釋分支預測的懲罰，首先來看什么是分支預測，以及為什么預測錯誤會導致懲罰。

二、分支預測

什么是分支預測? 直接說計算機概念或許不太好理解，答案以一個鐵路分支路口的例子來說明了什么是分支預測。

考慮下面的鐵軌分支:

假設在還沒有遠距離信號通訊的時代。你是一個鐵路分支路口的操作人員，當聽到火車要來了，你根本不知道即將到來的這輛火車要開往哪個方向。于是，你讓這輛或者停下來，問列車長這輛車要開往那個方向，然后將鐵軌扳到對應的方向上。

火車是一個很笨重的東西，因此具有很大的慣性，需要花很多時間啟動和停止。

那么，有沒有更好的辦法呢？那就是，由你來猜這輛火車要往那個方向走！

• 如果猜對了，火車可以直接開往要去的方向
• 如果猜錯了，火車要停下來，然后倒車，然后將車軌扳到正確的方向，然后火車重新開往正確的方向。

如果你的猜測總是正確的，那么火車就不用停下來了

如果你經常猜錯，那么火車就要花很多的時間停下來，后退，然后重新開動。

現在，考慮一個if語句。if 語句編譯為一個分支判斷指令：

如果你是處理器，你看到了這個分支，你事先完全沒沒有辦法知道將從那個分支走。那么怎么辦呢？你可以讓指令暫停，等待直到之前的指令執行完成，然后比較結果，然后往正確的那個方向走。

現代處理器很復雜，并且有很長的流水線，因此如果是這樣的話，就需要很多時間來預熱啟動和停止。

那么，有沒有更好一點兒的辦法呢？你來猜這個指令將往那個方向走:

• 如果猜對了，語句可以繼續執行
• 如果猜錯了，處理器會放棄整個流水線，然后回退到分支地方，繼續朝正確的分支執行。

如果每次都猜對，那么處理器不需要暫停可以一直執行

如果經常猜錯，那么處理器就要話很多時間來暫停，回退，然后重新啟動。

這就是分支預測，雖然用火車鐵軌的方式來解釋可能不太恰當，因為通過旗幟或者信號可以提前通知要往那個方向。 但是對于計算機來說，處理器提前是不知道將要執行那個分支的，只有等到執行到分支判斷的那一刻，值求出來之后才可以確定。

因此如何采用一種策略來減少出錯的次數，減少類似火車停車，倒車，再啟動的問題呢？很自然的，可以根據以往的情形來推斷！如果這個火車以前有99% 的情況走左邊，那么就可以在火車來之前猜測他走左邊。如果行為發生變化，可以做相應的調整。如果發現每3次調整一次方向，那么總結出這個規律后就可以做出 適當的調整。

換句話說，我們需要總結出一些模式，然后遵循。這或多或少就是分支預測器的工作。

大多數的應用都有行為良好的分支。因此現代的分支預測器能到達到90%以上的預測正確率。但是面對一些不可預見的分支和不可知的模式，分支預測器就沒有多大用了。

通過上面的描述，出現性能差別的問題關鍵在于這個if語句：

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

注意到data這個數組里面的值是平均分布于0-255之間的。當數據排好序之后，前半部分的數據都會小于128，所以不會進到if語句里面，后半部分的值都大于128，所以會進到循環語句。

這種規律對于分支預測器非常友好，因為分支判斷語句發現總是選擇某個方向很多次，于是就很容易做出判斷。即使一個簡單的計數器就可以正確預測分支的方向，除了改變方向之后的一兩次預測失敗之外。

下面描述了理器在分支預測時的行為：

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 (很容易進行預測)

可以看到，當數據排好序之后，對分支預測器十分友好，很容易進行預測。

但是，當數據完全是隨機的時候，分支預測器便失去了用處，因為他無法預測隨機的數據。因此會有大概50%的預測失敗率。

那么怎么辦呢？

如果計算機沒有辦法將分支優化成條件轉移，也可以使用一些技巧，犧牲一些可讀性，移除條件判斷，來提高性能

比如，可以將下面的分支語句：

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

替換為：

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

這里使用了位運算，移除了分支預測。 移除分之后，再進行測試，在release條件下，結果如下：

可以看到，在沒有分支判斷的條件下，對有序和無序數組的處理，在速度上是差不多的。

但是，為什么分支預測能夠提高應用程序的執行效率，這就要來看看現代CPU的流水線設計了。

三、指令的流水線

指令的流水線化(pipelining)是一種增加指令吞吐量(throughput)的方法，即在單位時間內能夠提高同時執行指令的個數。他將一個基本的流水線拆分為了幾個連續的，獨立的步驟，然后某些步驟就可以同時執行。

流水線化通過同時執行一系列操作增加了吞吐量，但是她并沒有減少延遲，即并沒有減少一條指令從執行開始到執行結束的時間，仍要等到這一系列指令完成。實際上,流水線化由于將一條指令拆分成了幾個步驟從而可能會增加延遲。

上圖是一個具有4層流水線的示意圖，一般的一個方法可以分為四個步驟，讀取指令(Fetch)，指令解碼(Decode),運行指令(Execute)和寫回運行結果(Write back)。

上方灰色部分是一連串未運行的指令；下方灰色部分是已執行完成的指令，中間白色部分是流水線。下面是在每個時鐘周期下指令的執行狀態。

可見，流水線技術的主要目的就是通過重疊連續指令的步驟來提高吞吐量從而獲得性能，要做到這一點，就必須能夠實現確定要執行指令的序列和先后順序， 這樣才能使流水線中充滿了待執行的指令。當處理器遇到分支條件跳轉時，通常不能確定執行那個分支，因此處理器采用分支預測器來猜測每條跳轉指令是否會執 行。如果猜測比較可靠，那么流水線中就會充滿指令。但是，如果對跳轉的指令猜測錯誤，那么就要要求處理器丟掉它這個跳轉指令后的所有已做的操作，然后再開 始用從正確位置處起始的指令去填充流水線，可以看到這種預測錯誤會導致很嚴重的性能懲罰，會導致大約20-40個時鐘周期的浪費，從而導致性能的嚴重下 降。

在這部分開始處已經說明，如果編譯器不能將分支跳轉優化為條件轉移指令，可以使用一些技巧，比如位運算來移除分支判斷。

那就是說，如果能夠優化為條件轉移指令，也能提升性能。在該問題的Update部分，提問者說:

“GCC 4.6.1 with -O3 or -ftree-vectorize on x64 is able to generate a conditional move. So there is no difference between the sorted and unsorted data – both are fast. ”

GCC是C/C++編譯器，-O3是表示優化級別，可以將條件跳轉優化為條件傳送指令，從而使得在有序和無序情況下，對數據的處理同樣高效，那么條件轉移指令是什么呢？

四、條件傳送指令

關于條件傳送指令，在CSAPP這本書的第3.6.6部分有教詳細的介紹。這里針對這一具體問題詳細介紹一下，條件轉移指令是如何優化條件分支判斷，從而利用流水線從而提高應用程序效率的。

條件傳送是一種條件跳轉的一種替換策略，他首先就計算出一個條件的兩種結果，然后等到執行到分支判斷的地方，根據條件選擇一個結果。只有在一些受限 的條件下這種策略才可行，比如這個例子中的判斷數字是否大于128然后求和。但是如果可行，就可以通過一條簡單的條件傳送指令來實現，而不是需要條件跳轉 指令來實現分支判斷。比如下面的求兩個數相減絕對值的方法，如果不使用條件傳送指令：

在比較大小之后，通過跳轉指令，可以跳轉到正確的分支然后執行接下來的邏輯。 要利用流水線技術，分支預測器不能依賴上一步驟的結果出來了再去做判斷，它不可能等到cmpl執行完成再去選擇分支，它需要提前做出判斷，如果判斷正確， 沒有問題，如果錯誤，就有比較嚴重的錯誤懲罰，從而影響應用程序性能。

但是，如果使用條件跳轉，情況如下：

首先計算出了兩個分支的結果，然后判斷條件，對兩個分支的結果做出選擇。這里面就沒有分支判斷和跳轉指令，通過一條cmovl指令 (c表示條件，l表示less)就可以完成判斷和賦值，這樣分支預測器不需要做出分支判斷，能夠利用流水線，從而提高應用程序性能。

但是，使用條件傳送也不總是能夠提高代碼效率。如果條件的兩個分支都需要大量的計算，那么實現計算出來就需要很多時間，當條件不滿足時，這部分工作 就浪費了。編譯器必須在條件傳送浪費的計算時間和分支預測錯誤造成的性能處罰之間做出權衡。一般的，只有在分支處的兩個表達式都很容易計算時，比如只有一 條加法指令，就像本例中的”

sum += data[c]; “ 這樣，條件傳送替換條件跳轉才能提高效率。總的來說，條件數據傳送提供了一種用條件轉移來實現條件操作的替換策略，他只能用于一些很簡單的場景，但是這種情況還是比較常見的，它能夠充分利用現代處理器的流水線從而提高效率。

五、結論

本文首先引用了StackOverflow上的一個問題及其解答說明了分支預測錯誤對應于程序性能的影響，然后簡單分析了現代處理器流水線中如何使 用分支預測提高應用程序性能以及分支預測錯誤導致的性能懲罰，最后結合問題給出的使用技巧替換分支判斷，簡要分析了為什么通過將條件跳轉優化為條件傳送能 夠充分利用指令流水線，從而同樣能夠提高程序性能。

希望本文對您了解分支預測、條件轉移和指令流水線有所幫助。

來源：寒江獨釣