為什麼處理排序數組比處理未排序數組快？

您是分支預測失敗的受害者。
什麼是分支預測？
考慮一個鐵路樞紐：
Mecanismo的圖片，通過Wikimedia Commons。在CC-By-SA 3.0許可下使用。
現在，為了爭論起見，假設這是在1800年代-在進行長距離或無線電通信之前。
您是路口的操作員，並且聽到火車駛入。您不知道應該走哪條路。您停下火車，問司機他們想要哪個方向。然後您適當地設置開關。
火車很重，慣性很大。因此，它們花了永遠的時間來啟動和減速。
有沒有更好的辦法？您猜火車將朝哪個方向行駛！
如果您猜對了，它將繼續進行。
如果您猜錯了，機長會停下來，後退並大喊大叫，以撥動開關。然後，它可以沿著其他路徑重新啟動。
如果您每次都猜對了，火車將永遠不會停止。如果您經常猜錯，火車將花費大量時間停止，備份和重新啟動。
考慮一個if語句：在處理器級別，它是一條分支指令：
您是處理器，並且看到一個分支。您不知道它將走哪條路。你是做什麼？您停止執行並等待直到前面的指令完成。然後，您沿著正確的路徑繼續。
現代處理器很複雜，而且流程很長。因此，他們需要永遠“熱身”和“放慢腳步”。
有沒有更好的辦法？您猜分支將朝哪個方向前進！
如果您猜對了，則繼續執行。
如果您猜錯了，則需要刷新管道並回滾到分支。然後，您可以沿著其他路徑重新啟動。
如果您每次都猜對了，執行將永遠不會停止。如果您經常猜錯，那麼您將花費大量時間來拖延，回滾和重新啟動。
這是分支預測。我承認這不是最好的類比，因為火車可以只用一個標誌來指示方向。但是在計算機中，處理器直到最後一刻才知道分支的方向。
那麼，您如何從戰略上猜測如何將火車必須倒退和走另一條路的次數減至最少？您看看過去的歷史！如果火車有99％的時間向左行駛，那麼您就猜到了。如果它交替出現，那麼您將交替猜測。如果它每三回​​去一次，您會猜到相同...
換句話說，您嘗試識別一個模式並遵循它。這或多或少是分支預測變量的工作方式。
大多數應用程序具有行為良好的分支。因此，現代分支預測器通常將達到90％以上的命中率。但是，當面對沒有可識別模式的不可預測分支時，分支預測變量實際上是無用的。
進一步閱讀：Wikipedia上的“分支預測器”文章。
從上面暗示，罪魁禍首是這個if陳述：
如果（data [c]> = 128）
sum + = data [c];
請注意，數據在0到255之間均勻分佈。對數據進行排序時，大約前一半的迭代將不會進入if語句。之後，他們都會進入if語句。
這對分支預測器非常友好，因為分支連續多次朝同一方向前進。即使是簡單的飽和計數器也可以正確預測分支，除了在切換方向後進行幾次迭代外。
快速可視化：
T =採取分支
N =未採取分支
data [] = 0，1，2，3，4，... 126，127，128，129，130，... 250，251，252，...
分支= N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT（易於預測）
但是，當數據完全隨機時，分支預測器將變得無用，因為它無法預測隨機數據。因此，可能會有大約50％的錯誤預測（沒有比隨機猜測好）。
data [] = 226、185、125、158、198、144、217、79、202、118、14、150、177、182、133，...
分支= T，T，N，T，T，T，T，N，T，N，N，T，T，T，N ...
= TTNTTTTNTNNTTTN ...（完全隨機-難以預測）
那該怎麼辦呢？
如果編譯器無法將分支優化為有條件的移動，那麼如果您願意犧牲可讀性來提高性能，則可以嘗試一些破解。
更換：
如果（data [c]> = 128）
sum + = data [c];
與：
int =（data [c]-128）>> 31;
sum + =〜t＆data [c];
這消除了分支，並用一些按位運算將其替換。
（請注意，這種破解並不嚴格等同於原始的if語句。但是在這種情況下，它對data []的所有輸入值均有效。）
基準：Core i7 920 @ 3.5 GHz
C ++-Visual Studio 2010-x64版本
//分支-隨機
秒= 11.777
//分支-排序
秒= 2.352
//無分支-隨機
秒= 2.564
//無分支-排序
秒= 2.587
Java-NetBeans 7.1.1 JDK 7-x64
//分支-隨機
秒= 10.93293813
//分支-排序
秒= 5.643797077
//無分支-隨機
秒= 3.113581453
//無分支-排序
秒= 3.186068823
觀察結果：
使用分支：排序和未排序的數據之間存在巨大差異。
使用Hack：排序和未排序的數據之間沒有區別。
在C ++情況下，對數據進行排序時，hack實際上比分支慢一點。
一般的經驗法則是避免在關鍵循環中避免依賴數據的分支（例如在此示例中）。
更新：
在x64上帶有-O3或-ftree-vectorize的GCC 4.6.1能夠生成條件移動。因此，已排序和未排序的數據之間沒有區別-兩者都很快速。
（或有些快：對於已經排序的情況，cmov可能會變慢，特別是如果GCC將其放在關鍵路徑上而不是僅僅添加，尤其是在Broadmov之前的Intel上，cmov有2個週期延遲：gcc優化標誌-O3使代碼變慢比-O2）
即使在/ Ox下，VC ++ 2010也無法為此分支生成條件移動。
英特爾C ++編譯器（ICC）11發揮了神奇的作用。它互換兩個循環，從而將不可預測的分支提升到外部循環。因此，它不僅可以避免錯誤預測，而且還比VC ++和GCC生成的速度快兩倍！換句話說，ICC利用測試循環擊敗了基準測試...
如果給Intel編譯器提供無分支的代碼，它將直接對其進行矢量化處理……並且速度與分支一樣快（通過循環交換）。
這表明即使是成熟的現代編譯器，其優化代碼的能力也可能存在巨大差異。
|
分支預測。
對於排序數組，條件data [c]> = 128對於值的條帶首先為false，然後對於所有後續值都為true。這很容易預測。使用未排序的數組，您需要支付分支成本。
|
如對Mysticial的回答所解釋的那樣，當對數據進行排序時，性能大幅提高的原因是刪除了分支預測損失。
現在，如果我們看一下代碼
如果（data [c]> = 128）
sum + = data [c];
我們可以發現，如果... else ...分支的特定含義是在滿足條件時添加一些內容。這種類型的分支可以很容易地轉換為條件移動語句，該條件語句將被編譯為條件移動指令：cmovl，在x86系統中。去除分支並因此去除潛在的分支預測損失。
在C中，因此在C ++中，將直接（無需任何優化）編譯為x86中的條件移動指令的語句就是三元運算符...？ ...：....因此，我們將以上語句重寫為等效的語句：
sum + = data [c]> = 128嗎？數據[c]：0；
在保持可讀性的同時，我們可以檢查加速因子。
在Intel Core i7-2600K @ 3.4 GHz和Visual Studio 2010 Release Mode上，基準是（從Mysticial複製的格式）：
x86
//分支-隨機
秒= 8.885
//分支-排序
秒= 1.528
//無分支-隨機
秒= 3.716
//無分支-排序
秒= 3.71
x64
//分支-隨機
秒= 11.302
//分支-排序
秒= 1.830
//無分支-隨機
秒= 2.736
//無分支-排序
秒= 2.737
在多次測試中，結果是可靠的。當分支結果不可預測時，我們可以大大提高速度，但是當分支結果不可預測時，我們會受到一點損失。實際上，使用條件移動時，無論數據模式如何，性能都是相同的。
現在，通過研究它們生成的x86程序集，讓我們更加仔細地研究。為簡單起見，我們使用兩個函數max1和max2。
如果... else ...，max1將使用條件分支：
int max1（int a，int b）{
如果（a> b）
返回
其他
返回b;
}
max2使用三元運算符...？ ...：...：
int max2（int a，int b）{
返回a> b？ a：b;
}
在x86-64機器上，GCC -S生成以下程序集。
：最大1
movl％edi，-4（％rbp）
movl％esi，-8（％rbp）
movl -4（％rbp），％eax
cmpl -8（％rbp），％eax
jle .L2
movl -4（％rbp），％eax
move％eax，-12（％rbp）
JMP .L4
.L2：
movl -8（％rbp），％eax
move％eax，-12（％rbp）
.L4：
movl -12（％rbp），％eax
離開
退回
：最大2
movl％edi，-4（％rbp）
movl％esi，-8（％rbp）
movl -4（％rbp），％eax
cmpl％eax，-8（％rbp）
cmovge -8（％rbp），％eax
離開
退回
由於使用指令cmovge，max2使用的代碼少得多。但是真正的好處是max2不涉及分支跳轉jmp，如果預測的結果不正確，則會對性能造成重大影響。
那麼，為什麼有條件舉動的表現更好呢？
在典型的x86處理器中，一條指令的執行分為幾個階段。大致來說，我們有不同的硬件來處理不同的階段。因此，我們不必等待一條指令完成就可以開始一條新指令。這稱為流水線。
在分支情況下，以下指令由前一條指令確定，因此我們無法進行流水線操作。我們必須等待或預測。
在有條件的情況下執行條件移動指令分為幾個階段，但較早的階段（如Fetch和Decode）並不取決於前一條指令的結果。只有後期才需要結果。因此，我們等待一條指令執行時間的一小部分。這就是為什麼在容易預測時條件移動版本比分支慢的原因。
第二版《計算機系統：程序員的觀點》一書對此進行了詳細解釋。您可以查看第3.6.6節中的“條件移動指令”，整個第4章中的“處理器體系結構”和第5.11.2節中的“分支預測和錯誤預測懲罰”的特殊處理。
有時，某些現代的編譯器可以優化我們的代碼以提高彙編性能，而有時某些編譯器則不能（問題代碼使用Visual Studio的本機編譯器）。當情況變得如此復雜以至於編譯器無法自動優化它們時，了解分支與條件移動之間的性能差異（這是不可預測的）可以幫助我們編寫性能更高的代碼。
|
如果您對可以對此代碼進行更多優化感到好奇，請考慮以下事項：
從原始循環開始：
對於（無符號i = 0; i <100000; ++ i）
{
for（無符號j = 0; j  = 128）
總和==數據[j];
}
}
使用循環交換，我們可以安全地將此循環更改為：
for（無符號j = 0; j  = 128）
總和=數據[j];
}
}
然後，您可以看到if條件在整個i循環執行期間是恆定的，因此可以將if提升：
for（無符號j = 0; j  = 128）
{
對於（無符號i = 0; i <100000; ++ i）
{
總和=數據[j];
}
}
}
然後，您可以看到內部循環可以折疊為一個表達式，假設浮點模型允許它（例如，拋出/ fp：fast）
for（無符號j = 0; j  = 128）
{
和+ = data [j] * 100000;
}
}
那是比以前快100,000倍。
|
毫無疑問，我們中的某些人會對識別對CPU的分支預測器有問題的代碼的方式感興趣。 Valgrind工具cachegrind具有分支預測器模擬器，可使用--branch-sim = yes標誌啟用。在此問題的示例上運行它，將外部循環數減少到10000並使用g ++進行編譯，得出以下結果：
排序：
== 32551 ==分支機構：656,645,130（656,609,208 cond + 35,922 ind）
== 32551 ==錯誤預測：169,556（169,095 cond + 461 ind）
== 32551 ==錯誤率：0.0％（0.0％+ 1.2％）
未分類：
== 32555 ==分支機構：655,996,082（655,960,160 cond + 35,922 ind）
== 32555 ==錯誤預測：164,073,152（164,072,692 cond + 460 ind）
== 32555 ==錯誤率：25.0％（25.0％+ 1.2％）
深入研究cg_annotate產生的逐行輸出，我們看到了所討論的循環：
排序：
Bc Bcm Bi Bim
10,001 4 0 0 for（無符號i = 0; i <10000; ++ i）
。 。 。 。 {
。 。 。 。 //主循環
327,690,000 10,016 0 0 for（無符號c = 0; c  = 128）
0 0 0 0 sum + =數據[c];
。 。 。 。 }
。 。 。 。 }
未分類：
Bc Bcm Bi Bim
10,001 4 0 0 for（無符號i = 0; i <10000; ++ i）
。 。 。 。 {
。 。 。 。 //主循環
327,690,000 10,038 0 0 for（無符號c = 0; c  = 128）
0 0 0 0 sum + =數據[c];
。 。 。 。 }
。 。 。 。 }
這使您可以輕鬆地確定問題行-在未排序版本中，if（data [c]> = 128）行在cachegrind的branch-predictor模型下導致164,050,007錯誤預測的條件分支（Bcm），而在排序版本中僅導致10,006 。
另外，在Linux上，您可以使用性能計數器子系統來完成相同的任務，但是使用CPU計數器可以實現本機性能。
性能統計./sumtest_sorted
排序：
“ ./sumtest_sorted”的性能計數器統計信息：
11808.095776任務時鐘＃0.998使用的CPU
1,062個上下文開關＃0.090 K /秒
14個CPU遷移＃0.001 K /秒
337頁錯誤＃0.029 K /秒
26,487,882,764週期＃2.243 GHz
每個週期41,025,654,322條指令＃1.55 insns
6,558,871,379個分支＃555.455 M / sec
567,204個分支缺失-所有分支的0.01％
經過了11.827228330秒的時間
未分類：
性能“ ./sumtest_unsorted”的計數器統計信息：
28877.954344任務時鐘＃0.998使用的CPU
2,584個上下文開關＃0.089 K /秒
18個CPU遷移＃0.001 K /秒
335頁錯誤＃0.012 K /秒
65,076,127,595週期＃2.253 GHz
每個週期41,032,528,741條指令＃0.63 insns
6,560,579,013個分支＃227.183 M / sec
1,646,394,749分行缺失＃佔所有分行的25.10％
經過28.935500947秒的時間
它還可以使用反彙編進行源代碼註釋。
性能記錄-e branch-misses ./sumtest_unsorted
性能註釋-d sumtest_unsorted
百分比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：添加％rax，-0x30（％rbp）
...
有關更多詳細信息，請參見性能教程。
|
我只是閱讀了這個問題及其答案，所以我覺得答案丟失了。
我發現在託管語言中消除分支預測特別有效的一種常見方法是使用表查找而不是使用分支（儘管在這種情況下我沒有對其進行測試）。
這種方法通常在以下情況下有效：
它是一個小表，可能會緩存在處理器中，並且
您正在以非常緊密的循環運行事物和/或處理器可以預加載數據。
背景和原因
從處理器的角度來看，您的內存很慢。為了彌補速度上的差異，處理器內置了兩個緩存（L1 / L2緩存）。因此，假設您正在執行出色的計算，並發現您需要一塊內存。處理器將執行其“加載”操作，並將內存塊加載到高速緩存中，然後使用高速緩存執行其餘的計算。由於內存相對較慢，因此此“加載”將減慢您的程序的速度。
像分支預測一樣，它在奔騰處理器中進行了優化：處理器預測它需要加載一條數據，並在操作實際到達緩存之前嘗試將其加載到緩存中。正如我們已經看到的那樣，分支預測有時會出現嚴重的錯誤-在最壞的情況下，您需要返回並實際上等待內存加載，這將永遠耗費時間（換句話說：失敗的分支預測很糟糕，內存不足）分支預測失敗後的加載太可怕了！）。
對我們來說幸運的是，如果內存訪問模式是可預測的，則處理器會將其加載到其快速緩存中，一切都很好。
我們需要知道的第一件事是小的？雖然通常較小會更好，但經驗法則是堅持使用<= 4096字節大小的查找表。作為上限：如果您的查找表大於64K，則可能值得重新考慮。
構造表
因此，我們發現可以創建一個小表。接下來要做的就是準備好查找功能。查找功能通常是使用幾個基本整數運算（和，或，異或，移位，加法，刪除和乘以乘法）的小型函數。您希望通過查找功能將輸入轉換為表中的某種“唯一鍵”，然後簡單地為您提供所需的所有工作的答案。
在這種情況下：> = 128表示我們可以保留該值，<128表示我們可以擺脫它。最簡單的方法是使用“ AND”：如果我們保留它，我們將其與7FFFFFFF進行AND；如果要刪除它，則將其與0進行“與”運算。還要注意，128是2的冪-因此，我們可以繼續製作一張32768/128整數的表，並用一個零和很多零填充7FFFFFFFF。
託管語言
您可能想知道為什麼這在託管語言中能很好地工作。畢竟，託管語言使用分支檢查數組的邊界，以確保您不會弄亂……
好吧，不完全是... :-)
關於消除託管語言的此分支，已經進行了很多工作。例如：
對於（int i = 0; i  = 128）嗎？ c：0；
}
//測試
DateTime startTime = System.DateTime.Now;
長和= 0;
對於（int i = 0; i <100000; ++ i）
{
//主循環
對於（int j = 0; j  = 128）
sum + = data [c];
問題是：是什麼使上述語句在某些情況下（如已排序的數據）無法執行？這是“分支預測器”。分支預測器是一種數字電路，它試圖猜測在確定之前知道分支（例如，if-then-else結構）的方向。分支預測器的目的是改善指令管道中的流程。分支預測變量在實現高效能方面起著至關重要的作用！
讓我們做一些基準測試以更好地了解它
if語句的性能取決於其條件是否具有可預測的模式。如果條件始終為真或始終為假，則處理器中的分支預測邏輯將選擇模式。另一方面，如果模式是不可預測的，則if語句將更加昂貴。
讓我們在不同條件下測量此循環的性能：
對於（int i = 0; i  =128。這意味著我們可以輕鬆地提取單個位來告訴我們是否需要一個值：數據右邊的7位，剩下的是0位或1位，我們只想在有1位的情況下將值相加。我們將此位稱為“決策位”。
通過將決策位的0/1值用作數組的索引，無論數據是否排序，我們都可以使代碼變得同樣快。我們的代碼將始終添加一個值，但是當決策位為0時，我們會將值添加到我們不在乎的位置。這是代碼：
//測試
clock_t start = clock（）;
long long a [] = {0，0};
長久的總和
對於（無符號i = 0; i <100000; ++ i）
{
//主循環
for（無符號c = 0; c > 7）;
a [j] + = data [c];
}
}
double elapsedTime = static_cast （clock（）-start）/ CLOCKS_PER_SEC;
sum = a [1];
此代碼浪費了添加的一半，但從未發生分支預測失敗。對於隨機數據，它比帶有實際if語句的版本要快得多。
但是在我的測試中，顯式查找表的速度比此表稍快，這可能是因為索引到查找表的速度比移位略快。這顯示了我的代碼如何設置和使用查找表（在代碼中，“ LookUp Table”意為“ lut”）。這是C ++代碼：
//聲明然後填寫查詢表
int lut [256];
for（無符號c = 0; c <256; ++ c）
lut [c] =（c> = 128）？ c：0；
//構建後使用查找表
對於（無符號i = 0; i <100000; ++ i）
{
//主循環
for（無符號c = 0; c 值）
node = node-> pLeft;
其他
node = node-> pRight;
該庫將執行以下操作：
i =（x <節點->值）;
node = node-> link [i];
這是此代碼的鏈接：永遠困惑的紅黑樹
|
在排序的情況下，您可以比依靠成功的分支預測或任何無分支比較技巧來做的更好：完全刪除分支。
確實，該數組在數據<128和數據> = 128的連續區域中進行分區。因此，您應該使用二分搜索（使用Lg（arraySize）= 15比較）找到分區點，然後從中進行直接累加那一點。
諸如此類（未選中）
int i = 0，j，k = arraySize;
而（i > 1;
如果（數據[j]> = 128）
k = j;
其他
i = j;
}
總和= 0;
為（;我> 1;
對於（i = 0，k = arraySize; i  = 128？k：i）= j）
j =（i + k）>> 1;
對於（sum = 0; i  = 128）
/ \
/ \
/ \
真假
/ \
/ \
/ \
/ \
B）和+ = data [c]; C）用於循環或print（）。
如果沒有分支預測，則會發生以下情況：
要執行指令B或指令C，處理器將必須等到指令A到達流水線中的EX階段為止，因為轉到指令B或指令C的決定取決於指令A的結果。因此，管線看起來像這樣
如果條件返回true：
如果條件返回假：
等待指令A的結果的結果是，在上述情況下（無分支預測；對於true和false而言）花費的總CPU週期為7。
那麼什麼是分支預測？
分支預測器將嘗試猜測在確定之前知道分支（if-then-else結構）的方向。它不會等待指令A到達流水線的EX階段，但會猜測該決定並轉到該指令（在本例中為B或C）。
在正確猜測的情況下，管道如下所示：
如果以後檢測到猜測是錯誤的，則將部分執行的指令丟棄，流水線將從正確的分支重新開始，從而導致延遲。
在分支預測錯誤的情況下所浪費的時間等於從獲取階段到執行階段的流水線中的階段數。現代微處理器往往具有很長的流水線，因此誤預測延遲在10到20個時鐘週期之間。流水線越長，對好的分支預測器的需求就越大。
在OP的代碼中，有條件的第一次，分支預測變量沒有任何信息可作為預測的基礎，因此，第一次它將隨機選擇下一條指令。稍後在for循環中，它可以基於歷史記錄進行預測。
對於按升序排序的數組，存在三種可能性：
所有元素均小於128
所有元素都大於128
一些開始的新元素小於128，後來又大於128
讓我們假設預測變量在首次運行時將始終假設為真實分支。
因此，在第一種情況下，它將始終從歷史上講，它的所有預測都是正確的。
在第二種情況下，最初將預測錯誤，但是經過幾次迭代後，它將正確預測。
在第3種情況下，它最初將正確預測直到元素少於128個。此後，它將失敗一段時間並在歷史中看到分支預測失敗時進行校正。
在所有這些情況下，失敗的次數將太少，因此，僅需幾次就可以丟棄部分執行的指令並從正確的分支重新開始，從而減少了CPU週期。
但是，如果是隨機未排序的數組，則預測將需要丟棄部分執行的指令，並在大部分時間中從正確的分支重新開始，與排序後的數組相比，將導致更多的CPU週期。
|
官方答案將來自
英特爾-避免分支機構失職的成本
英特爾-分支和循環重組可防止錯誤預測
科學論文-分支預測計算機體系結構
書籍：J.L。Hennessy，D.A. Patterson：計算機體系結構：定量方法
科學出版物中的文章：是的Patt在分支預測中做了很多。
您還可以從這張可愛的圖表中看到分支預測變量為何會感到困惑。
原始代碼中的每個元素都是隨機值
data [c] = std :: rand（）％256;
因此，隨著std :: rand（）的打擊，預測變量將改變方向。
另一方面，一旦將其排序，預測變量將首先進入強烈不採用的狀態，並且當值更改為高值時，預測變量將在三個過程中從強烈不採用變為強烈採取。
|
在同一行中（我認為這沒有任何答案突出顯示），值得一提的是，有時（尤其是在性能至關重要的軟件中，例如在Linux內核中），您會找到一些if語句，如下所示：
如果（可能是（everything_is_ok））
{
/* 做一點事 */
}
或類似的：
如果（不太可能（very_improbable_condition））
{
/* 做一點事 */
}
實際上，approximate（）和appliant（）都是通過使用類似GCC的__builtin_expect的定義的宏，以幫助編譯器插入預測代碼以考慮到用戶提供的信息來滿足條件。 GCC支持其他可能會更改正在運行的程序的行為或發出底層指令（例如清除緩存等）的內置插件。請參閱此文檔，其中提供了可用的GCC內置插件。
通常，這種優化主要在執行時間很重要的硬實時應用程序或嵌入式系統中找到。例如，如果您要檢查僅發生1/10000000次的錯誤情況，那麼為什麼不通知編譯器呢？這樣，默認情況下，分支預測將假定條件為假。
|
C ++中經常使用的布爾運算會在編譯程序中產生許多分支。如果這些分支位於循環內並且難以預測，則它們可能會大大降低執行速度。布爾變量存儲為8位整數，false值為0，true值為1。
在所有意義上都將布爾變量用作輸入的運算符會檢查輸入是否具有除0或1以外的任何其他值，但將布爾值作為輸出的運算符不能產生除0或1之外的其他值，因此佈爾變量被過分確定。布爾變量作為輸入的效率低於必要的效率。
考慮示例：
布爾a，b，c，d;
c = a && b;
d = a || b;
這通常由編譯器通過以下方式實現：
布爾a，b，c，d;
如果（a！= 0）{
如果（b！= 0）{
c = 1；
}
其他{
轉到CFALSE;
}
}
其他{
CFALSE：
c = 0;
}
如果（a == 0）{
如果（b == 0）{
d = 0;
}
其他{
轉到DTRUE;
}
}
其他{
DTRUE：
d = 1；
}
此代碼遠非最佳。萬一發生預測錯誤，分支機構可能會花費很長時間。如果可以肯定地知道操作數除了0和1之外沒有其他值，則可以使布爾運算的效率更高。編譯器沒有做出這種假設的原因是，如果變量未初始化，則它們可能具有其他值。或來自未知來源。如果a和b已初始化為有效值，或者它們來自產生布爾輸出的運算符，則可以優化上述代碼。優化的代碼如下所示：
char a = 0，b = 1，c，d；
c = a＆b;
d = a | b;
使用char代替bool可以使用按位運算符（＆和|）代替布爾運算符（&&和||）。按位運算符是僅佔用一個時鐘週期的單個指令。即使a和b的值不為0或1，OR運算符（|）也可以工作。如果操作數的值不為0和1，則AND運算符（＆）和EXCLUSIVE OR運算符（^）的結果可能不一致。
〜不能用於NOT。代替，您可以通過將XOR與1進行異或運算，對已知為0或1的變量進行布爾NOT運算：
布爾a，b;
b =！a;
可以優化為：
字符a = 0，b;
b = a ^ 1;
如果b是在a為假時不應該求值的表達式（&&將不求b，＆will），則a && b不能用a＆b替換。同樣，|| b不能替換為|如果b是一個表達式，則如果a為true，則不應該對其求值。
如果操作數是變量，則使用按位運算符要比比較操作數更有利：
布爾x，y，z的兩倍；
a = x> y && z <5.0;
在大多數情況下是最佳選擇（除非您期望&&表達式會產生許多分支錯誤預測）。
|
這是肯定的！...
由於代碼中發生的切換，分支預測使邏輯運行速度變慢！就像您要走在一條筆直的街道上或拐彎處很多的街道上一樣，確保筆直的街道可以更快地完成！...
如果對數組進行了排序，則第一步的條件為false：data [c]> = 128，然後在到達街道盡頭的整個過程中為真值。這樣便可以更快地到達邏輯結尾。另一方面，使用未排序的數組，您需要進行大量的翻轉和處理，這肯定會使您的代碼運行緩慢。
在下面查看我為您創建的圖像。哪條街的建成速度會更快？
因此，以編程方式，分支預測會使流程變慢。
同樣在最後，很高興知道我們有兩種分支預測，每種預測都會以不同的方式影響您的代碼：
1.靜態的
2.動態
微處理器首次使用靜態分支預測
遇到條件分支，而動態分支預測是
用於條件分支代碼的成功執行。
為了有效地編寫您的代碼以利用這些優勢
規則，在編寫if-else或switch語句時，請檢查最多
常見情況首先出現，然後逐漸減少到最不常見。
循環不一定需要任何特殊的代碼順序
靜態分支預測，僅作為循環迭代器的條件
通常使用。
|
這個問題已經被回答了好多次了。我仍然想提請小組注意另一種有趣的分析。
最近，該示例（略作修改）還用作演示如何在Windows上的程序本身中分析一段代碼的方式。在此過程中，作者還展示瞭如何使用結果來確定代碼在排序和未排序兩種情況下大部分時間都花在了哪裡。最後，這篇文章還展示瞭如何使用HAL（硬件抽象層）的一個鮮為人知的功能來確定在未排序的情況下發生了多少分支錯誤預測。
鏈接在這裡：
自我剖析的證明
|
正如其他人已經提到的那樣，神秘的背後是分支預測器。
我不是要添加任何內容，而是以另一種方式解釋該概念。
Wiki上有一個簡短的介紹，其中包含文本和圖表。
我喜歡下面的解釋，該解釋使用圖表直觀地闡述了Branch Predictor。
在計算機體系結構中，分支預測變量是
試圖猜測分支方式的數字電路（例如
if-then-else結構）將在確定之前就消失了。的
分支預測器的目的是改善
指令管道。分支預測變量在
在許多現代管道中實現高效的性能
微處理器體系結構，例如x86。
雙向分支通常通過條件跳轉來實現
指令。有條件的跳轉可以“不採取”並繼續
用緊隨其後的代碼的第一分支執行
有條件的跳轉之後，或者可以“獲取”並跳轉到
程序存儲器中代碼第二個分支所在的不同位置
存儲。不確定是否會發生條件跳轉
直到計算出條件並且
條件跳轉已通過指令的執行階段
管道（見圖1）。
基於所描述的場景，我編寫了一個動畫演示來展示如何在不同情況下在管道中執行指令。
沒有分支預測器。
如果沒有分支預測，則處理器將不得不等到
條件跳轉指令在執行之前已經通過了執行階段
下一條指令可以進入流水線中的獲取階段。
該示例包含三個指令，第一個是條件跳轉指令。後兩條指令可以進入管道，直到執行條件跳轉指令為止。
3條指令需要9個時鐘週期才能完成。
使用Branch Predictor，不要進行條件跳轉。假設預測沒有採用有條件的跳躍。
3條指令需要7個時鐘週期才能完成。
使用Branch Predictor並進行條件跳轉。讓我們假設預測沒有採取條件轉移。
3條指令需要9個時鐘週期才能完成。
在分支預測錯誤的情況下浪費的時間等於
從獲取階段到執行階段的管道中的階段數
執行階段。現代微處理器往往具有相當長的時間
流水線，以使錯誤預測延遲在10到20個時鐘之間
週期。結果，延長管道的長度增加了對管道的需求。
更高級的分支預測器。
如您所見，似乎我們沒有理由不使用Branch Predictor。
這是一個非常簡單的演示，闡明了Branch Predictor的最基本部分。如果這些gif令人討厭，請隨時將其從答案中刪除，訪問者還可以從BranchPredictorDemo獲取實時演示源代碼。
|
分支預測收益！
重要的是要了解分支預測錯誤不會降低程序速度。錯過預測的代價就像不存在分支預測一樣，您等待表達式的評估來決定要運行的代碼（下一段中的進一步說明）。
如果（表達式）
{
//運行1
}其他{
//運行2
}
每當有if-else \ switch語句時，都必須對錶達式進行求值以確定應該執行哪個塊。在編譯器生成的彙編代碼中，插入了條件分支指令。
分支指令會導致計算機開始執行不同的指令序列，從而偏離計算機按順序執行指令的默認行為（即，如果表達式為false，則程序會跳過if塊的代碼），具體取決於某些條件。是本例中的表達評估。
就是說，編譯器會在實際評估結果之前嘗試預測結果。它將從if塊中獲取指令，如果表達式被證明是正確的，那就太好了！我們獲得了評估它所花費的時間，並在代碼中取得了進步。如果不是，那麼我們運行的是錯誤的代碼，將刷新管道，並運行正確的塊。
可視化：
假設您需要選擇路線1或路線2，等待您的伴侶檢查地圖，您已經停在##並等待，或者您可以選擇路線1，如果幸運的話（路線1是正確的路線），那就太好了，您不必等待夥伴檢查地圖（您節省了他檢查地圖所需的時間），否則您只需回頭即可。
儘管沖洗管道非常快，但如今採取這種賭博是值得的。預測排序的數據或變化緩慢的數據總是比預測快速變化更容易和更好。
O路線1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
路線2 \ --------------------------------
|
在ARM上，不需要分支，因為每條指令都有一個4位條件字段，該字段測試（零成本）處理器狀態寄存器中可能出現的16種不同條件中的任何一種，並且指令中的條件是否為否，指令將被跳過。這消除了對短分支的需求，並且該算法不會對分支預測產生任何影響。因此，由於排序的額外開銷，該算法的排序版本在ARM上的運行速度將比未排序版本慢。
該算法的內部循環在ARM彙編語言中看起來類似於以下內容：
MOV R0，＃0 // R0 =總和= 0
MOV R1，＃0 // R1 = c = 0
ADR R2，數據// R2 =數據數組的地址（將此指令置於外循環之外）
.inner_loop //內部循環分支標籤
LDRB R3，[R2，R1] // R3 =數據[c]
CMP R3，＃128 //比較R3與128
添加R0，R0，R3 //如果R3> = 128，則求和+ = data [c]-無需分支！
添加R1，R1，＃1 // c ++
CMP R1，#arraySize //將c與arraySize比較
BLT inner_loop //如果c （））;
for（無符號c = 0; c  = 128
sum = sum + data1（j）;
結束
結束
結束
托克
ExeTimeWithSorting = toc-tic;
上面的MATLAB代碼的結果如下：
a：經過時間（無排序）= 3479.880861秒。
b：經過的時間（帶有排序）= 2377.873098秒。
我得到的@GManNickG中的C代碼的結果是：
a：經過時間（無排序）= 19.8761秒。
b：經過的時間（帶有排序）= 7.37778秒。
基於此，MATLAB看上去比不進行排序的C實現慢了175倍，而進行排序卻慢了350倍。換句話說，對於MATLAB實現，效果（分支預測）為1.46x，對於C實現，效果為2.7x。
|
其他答案認為需要對數據進行排序的假設是不正確的。
以下代碼不會對整個數組進行排序，而是僅對數組的200個元素進行排序，因此運行速度最快。
僅對k個元素部分進行排序即可完成線性時間O（n）的預處理，而不是對整個數組進行排序所需的O（n.log（n））時間。
#include <算法>
#include 
#include 
int main（）{
int數據[32768]; const int l =數據大小/數據大小[0];
for（無符號c = 0; c  = 128）
sum + = data [c];
}
}
std :: cout << static_cast （clock（）-start）/ CLOCKS_PER_SEC << std :: endl;
std :: cout <<“ sum =” <<總和<< std :: endl;
}
這也“證明”它與諸如排序順序之類的任何算法問題均無關，並且確實是分支預測。
|
Bjarne Stroustrup對這個問題的回答：
這聽起來像一個面試問題。是真的嗎你怎麼知道的？這是一個壞主意，關於效率答題不首先做一些測量，所以重要的是要知道如何去衡量。
因此，我嘗試使用一百萬個整數的向量，得到：
已排序32995毫秒
隨機播放125944毫秒
已排序18610毫秒
隨機播放133304毫秒
已排序17942毫秒
隨機播放107858毫秒
我跑了幾次，以確保。是的，這種現像是真實的。我的關鍵代碼是：
無效運行（vector ＆v，const string＆label）
{
自動t0 = system_clock :: now（）;
sort（v.begin（），v.end（））;
自動t1 = system_clock :: now（）;
cout <<標籤
<< duration_cast <微秒>（t1-t0）.count（）
<<“毫秒\ n”;
}
無效的tst（）
{
vector  v（1'000'000）;
iota（v.begin（），v.end（），0）;
運行（v，“已排序”）；
std :: shuffle（v.begin（），v.end（），std :: mt19937 {std :: random_device {}（）}）;
運行（v，“洗牌”）;
}
對於這種編譯器，標準庫和優化器設置，至少這種現像是真實的。不同的實現可以而且確實給出不同的答案。實際上，有人確實做了更系統的研究（可以通過快速的網絡搜索找到它），並且大多數實現都顯示出這種效果。
原因之一是分支預測：排序算法中的關鍵操作是“ if（v [i] <樞軸]）…”或等效操作。對於排序的序列，測試始終為真，而對於隨機序列，選擇的分支隨機變化。
另一個原因是，當向量已經排序時，我們不需要將元素移到正確的位置。這些小細節的影響是我們看到的五或六倍。
快速排序（通常是排序）是一項複雜的研究，吸引了計算機科學的一些最偉大的頭腦。良好的排序功能是選擇好的算法並在實現過程中註意硬件性能的結果。
如果要編寫高效的代碼，則需要了解一些有關計算機體系結構的知識。
|
這個問題源於CPU上的分支預測模型。我建議閱讀這篇文章：
通過多個分支預測和分支地址緩存提高指令提取速率
對元素進行排序後，IR不會一次又一次地獲取所有CPU指令，而是從緩存中獲取它們。
|
避免分支預測錯誤的一種方法是建立查找表，並使用數據對其進行索引。 Stefan de Bruijn在回答中對此進行了討論。
但是在這種情況下，我們知道值在[0，255]範圍內，我們只關心值> =128。這意味著我們可以輕鬆地提取單個位來告訴我們是否需要一個值：數據右邊的7位，剩下的是0位或1位，我們只想在有1位的情況下將值相加。我們將此位稱為“決策位”。
通過將決策位的0/1值用作數組的索引，無論數據是否排序，我們都可以使代碼變得同樣快。我們的代碼將始終添加一個值，但是當決策位為0時，我們會將值添加到我們不在乎的位置。這是代碼：
//測試
clock_t start = clock（）;
long long a [] = {0，0};
長久的總和
對於（無符號i = 0; i <100000; ++ i）
{
//主循環
for（無符號c = 0; c > 7）;
a [j] + = data [c];
}
}
double elapsedTime = static_cast （clock（）-start）/ CLOCKS_PER_SEC;
sum = a [1];
此代碼浪費了添加的一半，但從未發生分支預測失敗。對於隨機數據，它比帶有實際if語句的版本要快得多。
但是在我的測試中，顯式查找表的速度比此表稍快，這可能是因為索引到查找表的速度比移位略快。這顯示了我的代碼如何設置和使用查找表（在代碼中，“ LookUp Table”意為“ lut”）。這是C ++代碼：
//聲明然後填寫查詢表
int lut [256];
for（無符號c = 0; c <256; ++ c）
lut [c] =（c> = 128）？ c：0；
//構建後使用查找表
對於（無符號i = 0; i <100000; ++ i）
{
//主循環
for（無符號c = 0; c 值）
node = node-> pLeft;
其他
node = node-> pRight;
該庫將執行以下操作：
i =（x <節點->值）;
node = node-> link [i];
這是一個不錯的解決方案，也許會奏效。
|
高度活躍的問題。贏得10個聲譽才能回答這個問題。信譽要求有助於保護該問題免受垃圾郵件和非答復活動的侵害。
不是您要找的答案？瀏覽標記為Java c ++性能優化分支預測的其他問題，或者提出您自己的問題。