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


10 Answers

分支預測。

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

Question

這是一段看似非常特殊的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);
    }
}

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

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

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



如果您對可以對此代碼進行更多優化感到好奇,請考慮以下事項:

從原始循環開始:

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

通過循環交換,我們可以安全地將此循環更改為:

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

然後,你可以看到if條件在i循環的執行過程中是恆定的,所以你可以提升if out:

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

然後,您會看到內部循環可以折疊成一個單獨的表達式,假設浮點模型允許它(例如,/ fp:fast被拋出)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

那個比以前快了100,000倍




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

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

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

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

背景和原因

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();



避免分支預測錯誤的一種方法是構建查找表,並使用數據對其進行索引。Stefan de Bruijn在他的回答中討論了這一點。

但在這種情況下,我們知道值在[0,255]範圍內,我們只關心值> = 128.這意味著我們可以輕鬆地提取一個位,告訴我們是否需要一個值:通過移位數據向右7位,我們留下0位或1位,我們只想在有1位時添加該值。我們稱這個位為“決策位”。

通過使用決策位的0/1值作為數組的索引,無論數據是排序還是未排序,我們都可以製作同樣快速的代碼。我們的代碼總是會添加一個值,但是當決策位為0時,我們會將值添加到我們不關心的地方。這是代碼:

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

此代碼浪費了一半的添加但從未有分支預測失敗。隨機數據的速度比具有實際if語句的版本快得多。

但在我的測試中,顯式查找表略快於此,可能是因為索引到查找表的速度比位移略快。這顯示了我的代碼如何設置和使用查找表(lut代碼中缺乏想像力的“LookUp表”)。這是C ++代碼:

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

在這種情況下,查找表只有256個字節,因此它非常適合緩存,而且速度很快。如果數據是24位值並且我們只想要它們中的一半,這種技術將無法正常工作......查找表太大而不實用。另一方面,我們可以結合上面顯示的兩種技術:首先將位移位,然后索引查找表。對於我們只想要上半部分值的24位值,我們可能將數據右移12位,並為表索引留下12位值。12位表索引意味著一個包含4096個值的表,這可能是實用的。

編輯:有一件事我忘記了。

索引到數組而不是使用if語句的技術可用於決定使用哪個指針。我看到一個實現二叉樹的庫,而不是有兩個命名指針(pLeft和/ pRight或其他)有一個長度為2的指針數組,並使用“決策位”技術來決定遵循哪一個。例如,而不是:

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

這個庫會做類似的事情:

i = (x < node->value);
node = node->link[i];

這是這段代碼的鏈接:紅黑樹永恆的混淆




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

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

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

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

  1. IF - 從內存中獲取指令
  2. ID - 解碼指令
  3. EX - 執行指令
  4. 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循環中,它可以基於歷史記錄進行預測。對於按升序排序的數組,有三種可能性:

  1. 所有元素都小於128
  2. 所有元素都大於128
  3. 一些起始新元素小於128,後來大於128

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

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

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

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




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

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

或者類似的:

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

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

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




這是肯定的!...

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

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

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

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

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

1.靜態

2.動態

微處理器在第一次遇到條件分支時使用靜態分支預測,並且動態分支預測用於條件分支代碼的後續執行。

為了有效地編寫代碼以利用這些規則,在編寫if-elseswitch語句時,首先檢查最常見的情況,然後逐步降低到最不常見的情況。循環不一定需要任何特殊的靜態分支預測代碼排序,因為通常只使用循環迭代器的條件。




分支預測增益!

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

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

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

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

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

可視化:

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

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

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



這是關於分支預測。 它是什麼?

  • 分支預測器是古老的性能改進技術之一,它仍然與現代建築相關。雖然簡單的預測技術提供快速查找和功率效率,但是它們具有高的誤預測率。

  • 另一方面,複雜的分支預測 - 無論是基於神經的還是兩級分支預測的變體 - 提供更好的預測準確性,但它們消耗更多的功率和復雜性以指數方式增加。

  • 除此之外,在復雜的預測技術中,預測分支所花費的時間本身非常高,從2到5個週期 - 這與實際分支的執行時間相當。

  • 分支預測本質上是一種優化(最小化)問題,其中重點在於以最少的資源實現最低可能的未命中率,低功耗和低複雜度。

確實有三種不同的分支:

轉發條件分支 - 基於運行時條件,PC(程序計數器)被改變為指向指令流中的前向地址。

向後條件分支 - PC在指令流中變為指向後向。分支基於某些條件,例如,當循環結束時的測試表明循環應該再次執行時,向後分支到程序循環的開頭。

無條件分支 - 包括跳轉,過程調用和沒有特定條件的返回。例如,無條件跳轉指令可能用彙編語言編碼為簡單的“jmp”,並且指令流必須立即定向到跳轉指令指向的目標位置,而條件跳轉可能被編碼為“jmpne”僅當先前“比較”指令中兩個值的比較結果顯示值不相等時,才會重定向指令流。 (x86架構使用的分段尋址方案增加了額外的複雜性,因為跳轉可以是“接近”(在一個段內)或“遠”(在段外)。每種類型對分支預測算法都有不同的影響。)

靜態/動態分支預測:微處理器在第一次遇到條件分支時使用靜態分支預測,並且動態分支預測用於條件分支代碼的後續執行。

參考文獻:




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

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

 // 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];               
 }





Related