java - 為什麼處理排序數組比處理未排序數組更快?

c++ performance (14)

分支預測。

對於排序數組，條件data[c] >= 128對於條紋值首先為false ，然後對於所有後續值變為true 。這很容易預測。使用未排序的數組，您需要支付分支成本。

這是一段看似非常特殊的C ++代碼。出於某些奇怪的原因，奇蹟般地對數據進行排序使得代碼快了近六倍。

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        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;
}

沒有std::sort(data, data + arraySize); ，代碼運行時間為11.54秒。
使用排序數據，代碼運行1.93秒。

最初，我認為這可能只是一種語言或編譯器異常。所以我用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);
    }
}

有點相似但不太極端的結果。

我的第一個想法是排序將數據帶入緩存，但後來我認為這是多麼愚蠢，因為數組剛剛生成。

到底是怎麼回事？
為什麼處理排序數組比處理未排序數組更快？
代碼總結了一些獨立的術語，順序無關緊要。

分支預測增益！

重要的是要理解分支錯誤預測不會減慢程序的速度。錯過預測的成本就像分支預測不存在一樣，您等待表達式的評估以決定運行什麼代碼（在下一段中進一步說明）。

if (expression)
{
    // Run 1
} else {
    // Run 2
}

只要有if-else\ switch_語句，就必須計算表達式以確定應該執行哪個塊。在編譯器生成的彙編代碼中，插入了條件branch指令。

分支指令可以使計算機開始執行不同的指令序列，從而偏離其按順序執行指令的默認行為（即，如果表達式為假，則程序跳過if塊的代碼），這取決於某些條件，即在我們的案例中的表達評估。

話雖這麼說，編譯器會嘗試在實際評估之前預測結果。它會從if塊中獲取指令，如果表達式是真的，那就太好了！我們獲得了評估它並在代碼中取得進展所花費的時間; 如果沒有，那麼我們運行錯誤的代碼，刷新管道，並運行正確的塊。

可視化：

假設您需要選擇路線1或路線2.等待您的伴侶檢查地圖，您已停在##並等待，或者您可以選擇路線1，如果您幸運（路線1是正確路線），然後很棒，你不必等待你的伴侶檢查地圖（你節省了檢查地圖所需的時間），否則你只需要回頭。

雖然沖洗管道速度非常快，但現在採取這種賭博是值得的。預測排序數據或變化緩慢的數據總是比預測快速變化更容易和更好。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

在同一行（我認為沒有任何答案突出顯示），有時候（特別是在性能很重要的軟件中，比如在Linux內核中）你可以找到一些if語句如下所示：

if (likely( everything_is_ok ))
{
    /* Do something */
}

或者類似的：

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

雙方likely()並unlikely()在由使用像海灣合作委員會的定義其實宏__builtin_expect幫助編譯器插入代碼的預測偏向考慮到用戶提供的信息的條件。 GCC支持其他可能改變正在運行的程序行為的內置函數或發出低級指令，如清除緩存等。請參閱此文檔，該文檔通過可用的GCC內置函數。

通常，這種優化主要在硬實時應用程序或嵌入式系統中找到，其中執行時間很重要且非常重要。例如，如果您正在檢查僅發生1/10000000次的錯誤情況，那麼為什麼不通知編譯器呢？這樣，默認情況下，分支預測會假設條件為假。

在排序的情況下，您可以做得比依賴成功的分支預測或任何無分支比較技巧更好：完全刪除分支。

實際上，陣列被分隔在一個連續的區域data < 128和另一個區域data >= 128。因此，您應該使用二分法搜索（使用Lg(arraySize) = 15比較）找到分區點，然後從該點直接累積。

像（未選中）的東西

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

或者，稍微混淆一點

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

一種更快的方法，即為排序或未排序提供近似解決方案:( sum= 3137536;假設真正均勻分佈，16384個樣本，期望值為191.5）:-)

官方的答案是來自

英特爾 - 避免分支機構錯誤預測的成本
英特爾 - 分支和循環重組以防止錯誤預測
科學論文 - 分支預測計算機結構
書籍：JL Hennessy，DA Patterson：計算機體系結構：定量方法
科學出版物中的文章：TY Yeh，YN Patt在分支預測中做了很多這些。

您還可以從這個可愛的diagram看到為什麼分支預測器會混淆。

原始代碼中的每個元素都是隨機值

data[c] = std::rand() % 256;

因此，預測因素將會改變方向std::rand()。

另一方面，一旦它被排序，預測器將首先進入強烈未被採用的狀態，並且當值變為高值時，預測器將在三次運行中通過從強烈不採取到強烈採取的一直改變。

我剛剛讀到了這個問題及其答案，我覺得答案遺失了。

消除我發現在託管語言中工作特別好的分支預測的常用方法是查找表而不是使用分支（儘管在這種情況下我還沒有測試過它）。

如果符合以下情況，此方法通用

它是一個小桌子，可能會被緩存在處理器中
您正在以非常緊湊的循環運行和/或處理器可以預加載數據

背景和原因

Pfew，那到底是什麼意思呢？

從處理器的角度來看，你的記憶很慢。為了彌補速度上的差異，他們在處理器（L1 / L2緩存）中構建了幾個緩存來補償這一點。所以想像一下，你正在做你很好的計算，並發現你需要一塊記憶。處理器將進行“加載”操作並將內存加載到緩存中 - 然後使用緩存執行其餘計算。因為內存相對較慢，這種“加載”會降低程序的速度。

與分支預測一樣，這在Pentium處理器中進行了優化：處理器預測它需要加載一段數據並嘗試在操作實際到達緩存之前將其加載到緩存中。正如我們已經看到的那樣，分支預測有時會出現可怕的錯誤 - 在最壞的情況下，您需要返回並實際等待內存負載，這將需要永遠（ 換句話說：失敗的分支預測是壞的，一個內存在分支預測失敗後加載是非常可怕的！ ）。

幸運的是，如果內存訪問模式是可預測的，處理器將把它加載到快速緩存中，一切都很好。

我們需要知道的第一件事是小什麼？雖然較小通常更好，但經驗法則是堅持查找大小<= 4096字節的表。作為上限：如果您的查找表大於64K，則可能值得重新考慮。

構建一個表

所以我們已經發現我們可以創建一個小表。接下來要做的是獲得一個查找功能。查找函數通常是使用幾個基本整數運算的小函數（和，或者，xor，shift，add，remove和multiply）。您希望通過查找功能將您的輸入轉換為表格中的某種“唯一鍵”，然後簡單地為您提供您希望它完成的所有工作的答案。

在這種情況下：> = 128意味著我們可以保留值，<128意味著我們擺脫它。最簡單的方法是使用'AND'：如果我們保留它，我們和它一起使用7FFFFFFF; 如果我們想擺脫它，我們和它為0.注意，128也是2的冪 - 所以我們可以繼續製作一個32768/128整數的表並填充一個零和很多7FFFFFFFF的。

託管語言

您可能想知道為什麼這在託管語言中運行良好。畢竟，託管語言使用分支檢查數組的邊界，以確保您不會陷入困境......

好吧，不完全...... :-)

為管理語言消除此分支已經做了相當多的工作。例如：

for (int i=0; i<array.Length; ++i)
   // Use array[i]

在這種情況下，編譯器顯然不會遇到邊界條件。至少Microsoft JIT編譯器（但我希望Java做類似的事情）會注意到這一點，並完全取消檢查。哇 - 這意味著沒有分支。同樣，它將處理其他明顯的案例。

如果您在託管語言上查找時遇到麻煩 - 關鍵是在查找函數中添加& 0x[something]FFF以使邊界檢查可預測 - 並且觀察它更快。

這種情況的結果

// 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.Next(256);

//To keep the spirit of the code in-tact I'll make a separate lookup table
// (I assume we cannot modify 'data' or the number of loops)
int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
    lookup[c] = (c >= 128) ? c : 0;

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        // Here you basically want to use simple operations - so no
        // random branches, but things like &, |, *, -, +, etc. are fine.
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);

Console.ReadLine();

由於分支預測，上述行為正在發生。

要理解分支預測，首先必須了解指令管道：

任何指令都被分成一系列步驟，以便可以並行地同時執行不同的步驟。這種技術稱為指令流水線，用於提高現代處理器的吞吐量。要更好地理解這一點，請在維基百科上查看此示例。

通常，現代處理器具有相當長的流水線，但為了方便起見，我們只考慮這4個步驟。

IF - 從內存中獲取指令
ID - 解碼指令
EX - 執行指令
WB - 寫回CPU寄存器

4級管道一般用於2條指令。

回到上面的問題，讓我們考慮以下說明：

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

如果沒有分支預測，將發生以下情況：

為了執行指令B或指令C，處理器必須等到指令A沒有到達流水線中的EX階段，因為轉到指令B或指令C的決定取決於指令A的結果。所以管道會是這樣的。

當if條件返回true時：

當if條件返回false時：

作為等待指令A的結果的結果，在上述情況下花費的總CPU週期（沒有分支預測;對於真和假）都是7。

那麼什麼是分支預測？

分支預測器將嘗試猜測分支（if-then-else結構）將以何種方式確定之前。它不會等待指令A到達流水線的EX階段，但是它會猜測決定並轉到該指令（在我們的例子中是B或C）。

如果猜測正確，管道看起來像這樣：

如果稍後檢測到猜測錯誤則丟棄部分執行的指令，並且管道以正確的分支重新開始，從而引起延遲。在分支錯誤預測的情況下浪費的時間等於從提取階段到執行階段的管道中的階段的數量。現代微處理器往往具有相當長的流水線，因此誤預測延遲在10到20個時鐘週期之間。管道越長，對分支預測器的需求就越大。

在OP的代碼中，第一次有條件時，分支預測器沒有任何基於預測的信息，所以第一次它會隨機選擇下一條指令。稍後在for循環中，它可以基於歷史記錄進行預測。對於按升序排序的數組，有三種可能性：

所有元素都小於128
所有元素都大於128
一些起始新元素小於128，後來大於128

讓我們假設預測器將始終在第一次運行時假設真正的分支。

因此，在第一種情況下，它始終採用真正的分支，因為歷史上它的所有預測都是正確的。在第二種情況下，最初它會預測錯誤，但經過幾次迭代後，它會正確預測。在第三種情況下，它將最初正確地預測，直到元素小於128.之後它將失敗一段時間並且當它看到歷史中的分支預測失敗時正確。

在所有這些情況下，故障的數量將會減少，因此，只需要幾次就可以丟棄部分執行的指令並重新使用正確的分支，從而減少CPU週期。

但是在隨機未排序的數組的情況下，預測將需要丟棄部分執行的指令並且在大多數時間重新開始使用正確的分支，並且與排序的數組相比產生更多的CPU週期。

由於稱為分支預測的現象，排序的陣列比未排序的陣列處理得更快。

分支預測器是一種數字電路（在計算機體系結構中），試圖預測分支將採用哪種方式，從而改善指令流水線中的流量。電路/計算機預測下一步並執行它。

做出錯誤的預測會導致返回上一步，並執行另一個預測。假設預測正確，代碼將繼續下一步。錯誤的預測導致重複相同的步驟，直到發生正確的預測。

你的問題的答案很簡單。

在未排序的數組中，計算機會進行多次預測，從而導致出錯的可能性增加。然而，在排序中，計算機進行的預測更少，從而減少了出錯的可能性。進行更多預測需要更多時間。

分類陣列：直道

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

未排序的陣列：彎曲的道路

______   ________
|     |__|

分支預測：猜測/預測哪條道路是直的並且在沒有檢查的情況下跟隨它

___________________________________________ Straight road
 |_________________________________________|Longer road

雖然兩條道路都到達同一目的地，但直道較短，而另一條道路較長。如果那時你錯誤地選擇了另一個，那麼就沒有回頭了，所以如果你選擇更長的路，你會浪費一些額外的時間。這與計算機上發生的情況類似，我希望這有助於您更好地理解。

更新：在@Simon_Weaver所說的之後，我想添加另一個事實......“它不會做出更少的預測 - 它會減少不正確的預測。它仍然需要預測每次循環。”

當數組排序時，數據在0到255之間分配，迭代的前半部分將不會進入if -statement（ if語句在下面共享）。

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

問題是：在某些情況下，如果排序數據的情況，上述語句不執行的原因是什麼？這是“分支預測器”。分支預測器是一種數字電路，它試圖猜測分支（例如if-then-else結構）在確定之前會走哪條路。分支預測器的目的是改善指令流水線中的流程。分支預測器在實現高效性能方面發揮著關鍵作用！

讓我們做一些基準測試來更好地理解它

if-statement 的表現取決於其條件是否具有可預測的模式。如果條件始終為真或始終為假，則處理器中的分支預測邏輯將獲取模式。另一方面，如果模式不可預測，那麼 - if陳述將更加昂貴。

讓我們用不同的條件來衡量這個循環的性能：

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

以下是具有不同真假模式的循環的時序：

Condition            Pattern                 Time (ms)

(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0            TF alternating    760

(i & 3) == 0            TFFFTFFF…          513

(i & 2) == 0            TTFFTTFF…          1675

(i & 4) == 0            TTTTFFFFTTTTFFFF… 1275

(i & 8) == 0            8T 8F 8T 8F …     752

(i & 16) == 0            16T 16F 16T 16F … 490

一個“ 壞 ”的真假模式可以使一個if語句比“ 好 ”模式慢六倍！當然，哪種模式好，哪種模式不好取決於編譯器和特定處理器生成的確切指令。

因此，分支預測對性能的影響毫無疑問！

這是肯定的！...

分支預測會使邏輯運行速度變慢，因為代碼中會發生切換！這就像你要走一條直街或一條有很多轉彎的街道，肯定會直接做得更快！...

如果數組已排序，則第一步的條件為false：data[c] >= 128然後成為到街道盡頭的整個路徑的真值。這就是你如何更快地完成邏輯的結束。另一方面，使用未排序的數組，您需要進行大量的轉換和處理，這會使您的代碼運行速度變慢...

看下面我為你創建的圖像。哪條街要快點完成？

因此，以編程方式，分支預測會導致進程變慢...

最後，我們很高興知道我們有兩種分支預測，每種預測都會以不同的方式影響您的代碼：

1.靜態

2.動態

微處理器在第一次遇到條件分支時使用靜態分支預測，並且動態分支預測用於條件分支代碼的後續執行。
為了有效地編寫代碼以利用這些規則，在編寫if-else或switch語句時，首先檢查最常見的情況，然後逐步降低到最不常見的情況。循環不一定需要任何特殊的靜態分支預測代碼排序，因為通常只使用循環迭代器的條件。

除了分支預測可能會降低您的速度之外，排序數組還有另一個優勢：

您可以設置停止條件而不是僅檢查值，這樣您只需循環訪問相關數據，並忽略其餘數據。
分支預測只會遺漏一次。

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

在ARM上，不需要分支，因為每條指令都有一個4位條件字段，以零成本進行測試。這消除了對短分支的需要，並且不會出現分支預測。因此，由於排序的額外開銷，排序版本將比ARM上的未排序版本運行得慢。內部循環看起來如下所示：

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize

正如其他人已經提到的那樣，神秘的背後是分支預測器。

我不是想添加一些東西，而是以另一種方式解釋這個概念。維基上有一個簡明的介紹，其中包含文本和圖表。我喜歡下面的解釋，它使用圖表直觀地闡述了分支預測器。

在計算機體系結構中，分支預測器是一種數字電路，它試圖猜測分支（例如if-then-else結構）在確定之前會走哪條路。分支預測器的目的是改善指令流水線中的流程。分支預測器在許多現代流水線微處理器架構（如x86）中實現高效性能方面發揮著關鍵作用。
雙向分支通常使用條件跳轉指令來實現。條件跳轉可以是“未採用”並繼續執行第一個代碼分支，緊接在條件跳轉之後，或者可以“採取”並跳轉到程序存儲器中的不同位置，其中第二個代碼分支是存儲。在計算條件並且條件跳轉已經過指令流水線中的執行階段之前，不確定是否採取條件跳轉是未知的（見圖1）。

基於所描述的場景，我編寫了一個動畫演示，以顯示在不同情況下如何在管道中執行指令。

沒有分支預測器。

在沒有分支預測的情況下，處理器必須等到條件跳轉指令已經通過執行階段，然後下一條指令才能進入流水線中的獲取階段。

該示例包含三條指令，第一條是條件跳轉指令。後兩條指令可以進入流水線，直到執行條件跳轉指令。

完成3條指令需要9個時鐘週期。

使用分支預測器，不要進行條件跳轉。讓我們假設預測沒有採取條件跳躍。

完成3條指令需要7個時鐘週期。

使用分支預測器並進行條件跳轉。讓我們假設預測沒有採取條件跳躍。

完成3條指令需要9個時鐘週期。

在分支錯誤預測的情況下浪費的時間等於從提取階段到執行階段的管道中的階段的數量。現代微處理器往往具有相當長的流水線，因此誤預測延遲在10到20個時鐘週期之間。因此，使管道更長時間增加了對更高級分支預測器的需求。

如您所見，似乎我們沒有理由不使用Branch Predictor。

這是一個非常簡單的演示，闡明了Branch Predictor的基本部分。如果這些GIF很煩人，請隨時將它們從答案中刪除，訪問者也可以從git獲取演示git

這個問題已經多次得到了很好的回答。我仍然希望將該小組的注意力吸引到另一個有趣的分析上。

最近這個例子（稍微修改過）也被用來演示如何在Windows上的程序本身中分析一段代碼。在此過程中，作者還展示瞭如何使用結果來確定代碼在排序和未排序的情況下花費大部分時間的位置。最後，該文章還展示瞭如何使用HAL（硬件抽象層）的一個鮮為人知的特徵來確定在未排序的情況下發生了多少分支錯誤預測。

鏈接在這裡：http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm：http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm