java 為什麼處理排序數組比處理未排序數組更快?
c++ performance (17)
這是一段看似非常特殊的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);
}
}
有點相似但不太極端的結果。
我的第一個想法是排序將數據帶入緩存，但後來我認為這是多麼愚蠢，因為數組剛剛生成。
- 到底是怎麼回事？
- 為什麼處理排序數組比處理未排序數組更快？
- 代碼總結了一些獨立的術語，順序無關緊要。
由於稱為分支預測的現象，排序的陣列比未排序的陣列處理得更快。
分支預測器是一種數字電路（在計算機體系結構中），試圖預測分支將採用哪種方式，從而改善指令流水線中的流量。電路/計算機預測下一步並執行它。
做出錯誤的預測會導致返回上一步，並執行另一個預測。假設預測正確，代碼將繼續下一步。錯誤的預測導致重複相同的步驟，直到發生正確的預測。
你的問題的答案很簡單。
在未排序的數組中，計算機會進行多次預測，從而導致出錯的可能性增加。然而，在排序中，計算機進行的預測更少，從而減少了出錯的可能性。進行更多預測需要更多時間。
分類陣列：直道
____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
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語句比“ 好 ”模式慢六倍！當然，哪種模式好，哪種模式不好取決於編譯器和特定處理器生成的確切指令。
因此，分支預測對性能的影響毫無疑問！
我剛剛讀到了這個問題及其答案，我覺得答案遺失了。
消除我發現在託管語言中工作特別好的分支預測的常用方法是查找表而不是使用分支（儘管在這種情況下我還沒有測試過它）。
如果符合以下情況，此方法通用
- 它是一個小桌子，可能會被緩存在處理器中
- 您正在以非常緊湊的循環運行和/或處理器可以預加載數據
背景和原因
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();
毫無疑問，我們中的一些人會對識別對CPU的分支預測器有問題的代碼感興趣。 Valgrind工具cachegrind有一個分支預測模擬器，使用--branch-sim=yes標誌啟用。 在這個問題的例子中運行它，外部循環的數量減少到10000並用g++編譯，給出了以下結果：
排序方式：
==32551== Branches: 656,645,130 ( 656,609,208 cond + 35,922 ind)
==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind)
==32551== Mispred rate: 0.0% ( 0.0% + 1.2% )
未排序：
==32555== Branches: 655,996,082 ( 655,960,160 cond + 35,922 ind)
==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind)
==32555== Mispred rate: 25.0% ( 25.0% + 1.2% )
深入研究由cg_annotate生成的cg_annotate輸出，我們看到有問題的循環：
排序方式：
Bc Bcm Bi Bim
10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i)
. . . . {
. . . . // primary loop
327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c)
. . . . {
327,680,000 10,006 0 0 if (data[c] >= 128)
0 0 0 0 sum += data[c];
. . . . }
. . . . }
未排序：
Bc Bcm Bi Bim
10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i)
. . . . {
. . . . // primary loop
327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c)
. . . . {
327,680,000 164,050,007 0 0 if (data[c] >= 128)
0 0 0 0 sum += data[c];
. . . . }
. . . . }
這使您可以輕鬆識別有問題的行 - 在未排序的版本中， if (data[c] >= 128)行在cachegrind的branch-predictor模型下導致164,050,007個錯誤預測的條件分支（ Bcm ），而它僅在排序版本中導致10,006 。
或者，在Linux上，您可以使用性能計數器子系統來完成相同的任務，但使用CPU計數器具有本機性能。
perf stat ./sumtest_sorted
排序方式：
Performance counter stats for './sumtest_sorted':
11808.095776 task-clock # 0.998 CPUs utilized
1,062 context-switches # 0.090 K/sec
14 CPU-migrations # 0.001 K/sec
337 page-faults # 0.029 K/sec
26,487,882,764 cycles # 2.243 GHz
41,025,654,322 instructions # 1.55 insns per cycle
6,558,871,379 branches # 555.455 M/sec
567,204 branch-misses # 0.01% of all branches
11.827228330 seconds time elapsed
未排序：
Performance counter stats for './sumtest_unsorted':
28877.954344 task-clock # 0.998 CPUs utilized
2,584 context-switches # 0.089 K/sec
18 CPU-migrations # 0.001 K/sec
335 page-faults # 0.012 K/sec
65,076,127,595 cycles # 2.253 GHz
41,032,528,741 instructions # 0.63 insns per cycle
6,560,579,013 branches # 227.183 M/sec
1,646,394,749 branch-misses # 25.10% of all branches
28.935500947 seconds time elapsed
它還可以使用反彙編來執行源代碼註釋。
perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
Percent | Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
: sum += data[c];
0.00 : 400a1a: mov -0x14(%rbp),%eax
39.97 : 400a1d: mov %eax,%eax
5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax
4.60 : 400a26: cltq
0.00 : 400a28: add %rax,-0x30(%rbp)
...
有關詳細信息，請參閱性能教程 。
正如其他人已經提到的那樣，神秘的背後是分支預測器。
我不是想添加一些東西，而是以另一種方式解釋這個概念。維基上有一個簡明的介紹，其中包含文本和圖表。我喜歡下面的解釋，它使用圖表直觀地闡述了分支預測器。
在計算機體系結構中，分支預測器是一種數字電路，它試圖猜測分支（例如if-then-else結構）在確定之前會走哪條路。分支預測器的目的是改善指令流水線中的流程。分支預測器在許多現代流水線微處理器架構（如x86）中實現高效性能方面發揮著關鍵作用。
雙向分支通常使用條件跳轉指令來實現。條件跳轉可以是“未採用”並繼續執行第一個代碼分支，緊接在條件跳轉之後，或者可以“採取”並跳轉到程序存儲器中的不同位置，其中第二個代碼分支是存儲。在計算條件並且條件跳轉已經過指令流水線中的執行階段之前，不確定是否採取條件跳轉是未知的（見圖1）。
基於所描述的場景，我編寫了一個動畫演示，以顯示在不同情況下如何在管道中執行指令。
- 沒有分支預測器。
在沒有分支預測的情況下，處理器必須等到條件跳轉指令已經通過執行階段，然後下一條指令才能進入流水線中的獲取階段。
該示例包含三條指令，第一條是條件跳轉指令。後兩條指令可以進入流水線，直到執行條件跳轉指令。
完成3條指令需要9個時鐘週期。
- 使用分支預測器，不要進行條件跳轉。讓我們假設預測沒有採取條件跳躍。
完成3條指令需要7個時鐘週期。
- 使用分支預測器並進行條件跳轉。讓我們假設預測沒有採取條件跳躍。
完成3條指令需要9個時鐘週期。
在分支錯誤預測的情況下浪費的時間等於從提取階段到執行階段的管道中的階段的數量。現代微處理器往往具有相當長的流水線，因此誤預測延遲在10到20個時鐘週期之間。因此，使管道更長時間增加了對更高級分支預測器的需求。
如您所見，似乎我們沒有理由不使用Branch Predictor。
這是一個非常簡單的演示，闡明了Branch Predictor的基本部分。如果這些GIF很煩人，請隨時將它們從答案中刪除，訪問者也可以從git獲取演示git
分支預測增益！
重要的是要理解分支錯誤預測不會減慢程序的速度。錯過預測的成本就像分支預測不存在一樣，您等待表達式的評估以決定運行什麼代碼（在下一段中進一步說明）。
if (expression)
{
// Run 1
} else {
// Run 2
}
只要有if-else\ switch_語句，就必須計算表達式以確定應該執行哪個塊。在編譯器生成的彙編代碼中，插入了條件branch指令。
分支指令可以使計算機開始執行不同的指令序列，從而偏離其按順序執行指令的默認行為（即，如果表達式為假，則程序跳過if塊的代碼），這取決於某些條件，即在我們的案例中的表達評估。
話雖這麼說，編譯器會嘗試在實際評估之前預測結果。它會從if塊中獲取指令，如果表達式是真的，那就太好了！我們獲得了評估它並在代碼中取得進展所花費的時間; 如果沒有，那麼我們運行錯誤的代碼，刷新管道，並運行正確的塊。
可視化：
假設您需要選擇路線1或路線2.等待您的伴侶檢查地圖，您已停在##並等待，或者您可以選擇路線1，如果您幸運（路線1是正確路線），然後很棒，你不必等待你的伴侶檢查地圖（你節省了檢查地圖所需的時間），否則你只需要回頭。
雖然沖洗管道速度非常快，但現在採取這種賭博是值得的。預測排序數據或變化緩慢的數據總是比預測快速變化更容易和更好。
O Route 1 /-------------------------------
/|\ /
| ---------##/
/ \ \
\
Route 2 \--------------------------------
這個問題已經多次得到了很好的回答。我仍然希望將該小組的注意力吸引到另一個有趣的分析上。
最近這個例子（稍微修改過）也被用來演示如何在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
避免分支預測錯誤的一種方法是構建查找表，並使用數據對其進行索引。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];
這是這段代碼的鏈接：紅黑樹，永恆的混淆
在同一行（我認為沒有任何答案突出顯示），有時候（特別是在性能很重要的軟件中，比如在Linux內核中）你可以找到一些if語句如下所示：
if (likely( everything_is_ok ))
{
/* Do something */
}
或者類似的：
if (unlikely(very_improbable_condition))
{
/* Do something */
}
雙方likely()並unlikely()在由使用像海灣合作委員會的定義其實宏__builtin_expect幫助編譯器插入代碼的預測偏向考慮到用戶提供的信息的條件。 GCC支持其他可能改變正在運行的程序行為的內置函數或發出低級指令，如清除緩存等。請參閱此文檔，該文檔通過可用的GCC內置函數。
通常，這種優化主要在硬實時應用程序或嵌入式系統中找到，其中執行時間很重要且非常重要。例如，如果您正在檢查僅發生1/10000000次的錯誤情況，那麼為什麼不通知編譯器呢？這樣，默認情況下，分支預測會假設條件為假。
當數據被排序時，性能提高的原因是分支預測懲罰被消除，正如的答案中精美地解釋的那樣。
現在，如果我們看一下代碼
if (data[c] >= 128)
sum += data[c];
我們可以發現這個特殊的if... else...分支的含義是在條件滿足時添加一些東西。 這種類型的分支可以很容易地轉換為條件移動語句，它將被編譯成x86系統中的條件移動指令： cmovl 。 分支以及因此潛在的分支預測懲罰被移除。
在C ， C++ ，這個語句可以直接編譯（沒有任何優化）到x86的條件移動指令，是三元運算符... ? ... : ... ... ? ... : ... 所以我們將上面的語句重寫為等價的語句：
sum += data[c] >=128 ? data[c] : 0;
在保持可讀性的同時，我們可以檢查加速因子。
在Intel Core i7 -2600K @ 3.4 GHz和Visual Studio 2010發布模式下，基準是（從Mysticial複製的格式）：
86
// Branch - Random
seconds = 8.885
// Branch - Sorted
seconds = 1.528
// Branchless - Random
seconds = 3.716
// Branchless - Sorted
seconds = 3.71
64位
// Branch - Random
seconds = 11.302
// Branch - Sorted
seconds = 1.830
// Branchless - Random
seconds = 2.736
// Branchless - Sorted
seconds = 2.737
結果在多個測試中是穩健的。 當分支結果不可預測時，我們獲得了很大的加速，但是當它是可預測的時候我們會受到一點點的影響。 實際上，在使用條件移動時，無論數據模式如何，性能都是相同的。
現在讓我們通過調查它們生成的x86程序集來更仔細地查看。 為簡單起見，我們使用max1和max2兩個函數。
max1使用條件分支if... else ... ：
int max1(int a, int b) {
if (a > b)
return a;
else
return b;
}
max2使用三元運算符... ? ... : ... ... ? ... : ... ：
int max2(int a, int b) {
return a > b ? a : b;
}
在x86-64機器上， GCC -S生成下面的組件。
:max1
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jle .L2
movl -4(%rbp), %eax
movl %eax, -12(%rbp)
jmp .L4
.L2:
movl -8(%rbp), %eax
movl %eax, -12(%rbp)
.L4:
movl -12(%rbp), %eax
leave
ret
:max2
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl %eax, -8(%rbp)
cmovge -8(%rbp), %eax
leave
ret
由於使用了指令cmovge max2使用的代碼要少cmovge 。 但真正的好處是max2不涉及分支跳轉， jmp ，如果預測結果不正確，則會產生顯著的性能損失。
那麼為什麼有條件的移動表現更好呢？
在典型的x86處理器中，指令的執行分為幾個階段。 粗略地說，我們有不同的硬件來處理不同的階段。 因此，我們不必等待一條指令完成開始新指令。 這稱為pipelining 。
在分支情況下，以下指令由前一個指令確定，因此我們不能進行流水線操作。 我們必須等待或預測。
在條件移動的情況下，執行條件移動指令被分成幾個階段，但是像Fetch和Decode這樣的早期階段不依賴於前一個指令的結果; 只有後期才需要結果。 因此，我們等待一個指令執行時間的一小部分。 這就是為什麼當預測很容易時，條件移動版本比分支慢。
“ 計算機系統：程序員視角 ”一書第二版詳細解釋了這一點。 您可以檢查第3.6.6節有關條件移動指令 ，整個第4章用於處理器體系結構 ，第5.11.2節用於特殊處理分支預測和錯誤預測懲罰 。
有時，一些現代編譯器可以優化我們的代碼以便以更好的性能進行彙編，有時一些編譯器不能（有問題的代碼使用Visual Studio的本機編譯器）。 在不可預測的情況下了解分支和條件移動之間的性能差異可以幫助我們在場景變得如此復雜以至於編譯器無法自動優化它們時編寫具有更好性能的代碼。
您是分支預測失敗的受害者。
什麼是分支預測？
考慮一個鐵路交界處：
來自Mecanismo，來自Wikimedia Commons。 在CC-By-SA 3.0許可下使用。
現在為了爭論，假設這是在19世紀 - 在長途或無線電通信之前。
您是交叉路口的運營商，您會聽到火車即將到來。 你不知道應該走哪條路。 你停下火車去詢問司機他們想要的方向。 然後適當地設置開關。
火車很重，有很多慣性。 所以他們需要永遠的啟動和放慢速度。
有沒有更好的辦法？ 你猜猜火車往哪個方向走！
- 如果你猜對了，那就繼續吧。
- 如果你猜對了，機長會停下來，然後向你大喊大叫，然後翻轉開關。 然後它可以重新啟動另一條路徑。
如果你每次都猜對了 ，火車就永遠不會停下來。
如果您經常猜錯 ，列車將花費大量時間停止，備份和重新啟動。
考慮一個if語句：在處理器級別，它是一個分支指令：
你是一個處理器，你看到一個分支。 你不知道它會走哪條路。 你是做什麼？ 您暫停執行並等待前面的指令完成。 然後繼續沿著正確的路徑前進。
現代處理器很複雜，管道很長。 所以他們永遠地“熱身”和“慢下來”。
有沒有更好的辦法？ 你猜猜分支的方向！
- 如果你猜對了，你繼續執行。
- 如果您猜錯了，則需要刷新管道並回滾到分支。 然後你可以重新啟動另一條路徑。
如果你每次都猜對了 ，執行將永遠不會停止。
如果你經常猜錯 ，你會花很多時間停滯，回滾和重新啟動。
這是分支預測。 我承認這不是最好的類比，因為火車可以用旗幟向方向發出信號。 但是在計算機中，處理器直到最後一刻才知道分支將朝哪個方向發展。
那麼你如何戰略性地猜測火車必須備份並沿著另一條路走下去的次數呢？ 你看看過去的歷史！ 如果火車99％的時間都離開了，那麼你猜對了。 如果它交替，那麼你交替猜測。 如果它每3次走一條路，你就猜相同......
換句話說，您嘗試識別模式並遵循它。 這或多或少是分支預測器的工作方式。
大多數應用程序具有良好的分支。 因此，現代分支預測器通常會達到> 90％的命中率。 但是當面對不可預測的分支而沒有可識別的模式時，分支預測器實際上是無用的。
進一步閱讀： 維基百科上的“分支預測”一文 。
如上所述，罪魁禍首就是這個if語句：
if (data[c] >= 128)
sum += data[c];
請注意，數據均勻分佈在0到255之間。當數據排序時，大致前半部分的迭代不會進入if語句。 之後，他們都將進入if語句。
這對分支預測器非常友好，因為分支連續多次朝同一方向運行。 即使是簡單的飽和計數器也會正確地預測分支，除了在切換方向後的幾次迭代。
快速可視化：
T = branch taken
N = branch not taken
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 (easy to predict)
但是，當數據完全隨機時，分支預測器變得無用，因為它無法預測隨機數據。 因此可能會有大約50％的錯誤預測。 （不比隨機猜測好）
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 ... (completely random - hard to predict)
那可以做些什麼呢？
如果編譯器無法將分支優化為條件移動，那麼如果您願意犧牲性能的可讀性，則可以嘗試一些黑客攻擊。
更換：
if (data[c] >= 128)
sum += data[c];
有：
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
這消除了分支並用一些按位操作替換它。
（注意，這個hack並不完全等同於原始的if語句。但在這種情況下，它對data[]所有輸入值都有效。）
基準測試：酷睿i7 920 @ 3.5 GHz
C ++ - Visual Studio 2010 - x64發行版
// Branch - Random
seconds = 11.777
// Branch - Sorted
seconds = 2.352
// Branchless - Random
seconds = 2.564
// Branchless - Sorted
seconds = 2.587
Java - Netbeans 7.1.1 JDK 7 - x64
// Branch - Random
seconds = 10.93293813
// Branch - Sorted
seconds = 5.643797077
// Branchless - Random
seconds = 3.113581453
// Branchless - Sorted
seconds = 3.186068823
觀察：
- 使用分支：已排序和未排序的數據之間存在巨大差異。
- 使用Hack：排序和未排序數據之間沒有區別。
- 在C ++的情況下，當數據被排序時，hack實際上比分支慢一點。
一般的經驗法則是避免在關鍵循環中依賴數據進行分支。 （例如在這個例子中）
更新：
在x64上使用
-O3或-ftree-vectorizeGCC 4.6.1能夠生成條件移動。 因此，排序和未排序數據之間沒有區別 - 兩者都很快。即使在
/Ox下，VC ++ 2010也無法為此分支生成條件移動。英特爾編譯器11做了一些奇蹟。 它交換兩個循環 ，從而將不可預測的分支提升到外循環。 因此，它不僅能夠免受錯誤預測的影響，而且速度也是VC ++和GCC能夠產生的速度的兩倍！ 換句話說，ICC利用測試循環來擊敗基準......
如果你給英特爾編譯器提供無分支代碼，那麼它就是向右矢量化它......並且與分支一樣快（使用循環交換）。
這表明即使是成熟的現代編譯器在優化代碼的能力方面也會有很大差異......
由於分支預測，上述行為正在發生。
要理解分支預測，首先必須了解指令管道：
任何指令都被分成一系列步驟，以便可以並行地同時執行不同的步驟。這種技術稱為指令流水線，用於提高現代處理器的吞吐量。要更好地理解這一點，請在維基百科上查看此示例。
通常，現代處理器具有相當長的流水線，但為了方便起見，我們只考慮這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週期。
這是關於分支預測。 它是什麼？
分支預測器是古老的性能改進技術之一，它仍然與現代建築相關。雖然簡單的預測技術提供快速查找和功率效率，但是它們具有高的誤預測率。
另一方面，複雜的分支預測 - 無論是基於神經的還是兩級分支預測的變體 - 提供更好的預測準確性，但它們消耗更多的功率和復雜性以指數方式增加。
除此之外，在復雜的預測技術中，預測分支所花費的時間本身非常高，從2到5個週期 - 這與實際分支的執行時間相當。
分支預測本質上是一種優化（最小化）問題，其中重點在於以最少的資源實現最低可能的未命中率，低功耗和低複雜度。
確實有三種不同的分支：
轉發條件分支 - 基於運行時條件，PC（程序計數器）被改變為指向指令流中的前向地址。
向後條件分支 - PC在指令流中變為指向後向。分支基於某些條件，例如，當循環結束時的測試表明循環應該再次執行時，向後分支到程序循環的開頭。
無條件分支 - 包括跳轉，過程調用和沒有特定條件的返回。例如，無條件跳轉指令可能用彙編語言編碼為簡單的“jmp”，並且指令流必須立即定向到跳轉指令指向的目標位置，而條件跳轉可能被編碼為“jmpne”僅當先前“比較”指令中兩個值的比較結果顯示值不相等時，才會重定向指令流。 （x86架構使用的分段尋址方案增加了額外的複雜性，因為跳轉可以是“接近”（在一個段內）或“遠”（在段外）。每種類型對分支預測算法都有不同的影響。）
靜態/動態分支預測：微處理器在第一次遇到條件分支時使用靜態分支預測，並且動態分支預測用於條件分支代碼的後續執行。
參考文獻：
在C ++中經常使用的布爾運算在編譯的程序中產生許多分支。如果這些分支在內部循環中並且很難預測它們會顯著減慢執行速度。布爾變量存儲為8位整數，其值為0for false和1for true。
布爾變量是超定的，因為所有具有布爾變量作為輸入的運算符檢查輸入是否具有除0or 之外的任何其他值1，但是具有布爾值作為輸出的運算符不能產生除0or 之外的其他值1。這使得使用布爾變量作為輸入的操作效率低於必要的效率。考慮示例：
bool a, b, c, d;
c = a && b;
d = a || b;
這通常由編譯器以下列方式實現：
bool a, b, c, d;
if (a != 0) {
if (b != 0) {
c = 1;
}
else {
goto CFALSE;
}
}
else {
CFALSE:
c = 0;
}
if (a == 0) {
if (b == 0) {
d = 0;
}
else {
goto DTRUE;
}
}
else {
DTRUE:
d = 1;
}
這段代碼遠非最佳。如果誤預測，分支機構可能需要很長時間。如果已經確定操作數沒有除了0和之外的其他值，則可以使布爾運算更有效1。編譯器沒有做出這樣的假設的原因是，如果變量未初始化或來自未知來源，則變量可能具有其他值。上面的代碼可以被優化，如果a和b都被初始化為有效值，或者如果它們來自運營商產生布爾輸出。優化的代碼如下所示：
char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char而不是bool為了使得可以使用按位運算符（&和|）而不是布爾運算符（&&和||）。按位運算符是單指令，只需一個時鐘週期。OR運算符（|）即使a並且b具有除0或之外的其他值也可以工作1。如果操作數具有除和之外的其他值，則AND運算符（&）和EXCLUSIVE OR運算符（^）可能會產生不一致的結果。01
~不能用於NOT。相反，你可以對已知的變量0或1通過XOR對其進行布爾值1：
bool a, b;
b = !a;
可以優化為：
char a = 0, b;
b = a ^ 1;
a && b不能替換為a & bif b是一個不應該被評估的表達式，如果a是false（&&將不會評估b，&將）。同樣地，a || b不能被替換a | b，如果b是，如果不應該被計算的表達式a是true。
如果操作數是變量而不是操作數是比較，則使用按位運算符更有利：
bool a; double x, y, z;
a = x > y && z < 5.0;
在大多數情況下是最佳的（除非您希望&&表達式生成許多分支錯誤預測）。
在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
官方的答案是來自
- 英特爾 - 避免分支機構錯誤預測的成本
- 英特爾 - 分支和循環重組以防止錯誤預測
- 科學論文 - 分支預測計算機結構
- 書籍：JL Hennessy，DA Patterson：計算機體系結構：定量方法
- 科學出版物中的文章：TY Yeh，YN Patt在分支預測中做了很多這些。
您還可以從這個可愛的diagram看到為什麼分支預測器會混淆。
原始代碼中的每個元素都是隨機值
data[c] = std::rand() % 256;
因此，預測因素將會改變方向std::rand()。
另一方面，一旦它被排序，預測器將首先進入強烈未被採用的狀態，並且當值變為高值時，預測器將在三次運行中通過從強烈不採取到強烈採取的一直改變。
如果您對可以對此代碼進行更多優化感到好奇，請考慮以下事項：
從原始循環開始：
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倍
