java - 為什麼處理排序數組比處理未排序數組更快？
您是分支預測失敗的受害者。
什麼是分支預測？
考慮一個鐵路交界處：
來自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利用測試循環來擊敗基準......
如果你給英特爾編譯器提供無分支代碼，那麼它就是向右矢量化它......並且與分支一樣快（使用循環交換）。
這表明即使是成熟的現代編譯器在優化代碼的能力方面也會有很大差異......
這是一段看似非常特殊的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 (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的本機編譯器）。 在不可預測的情況下了解分支和條件移動之間的性能差異可以幫助我們在場景變得如此復雜以至於編譯器無法自動優化它們時編寫具有更好性能的代碼。
毫無疑問，我們中的一些人會對識別對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)
...
有關詳細信息，請參閱性能教程 。
當數組排序時，數據在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語句比“ 好 ”模式慢六倍！當然，哪種模式好，哪種模式不好取決於編譯器和特定處理器生成的確切指令。
因此，分支預測對性能的影響毫無疑問！
在排序的情況下，您可以做得比依賴成功的分支預測或任何無分支比較技巧更好：完全刪除分支。
實際上，陣列被分隔在一個連續的區域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()。
另一方面，一旦它被排序，預測器將首先進入強烈未被採用的狀態，並且當值變為高值時，預測器將在三次運行中通過從強烈不採取到強烈採取的一直改變。
在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;
在大多數情況下是最佳的（除非您希望&&表達式生成許多分支錯誤預測）。
這個問題已經多次得到了很好的回答。我仍然希望將該小組的注意力吸引到另一個有趣的分析上。
最近這個例子（稍微修改過）也被用來演示如何在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
正如其他人已經提到的那樣，神秘的背後是分支預測器。
我不是想添加一些東西，而是以另一種方式解釋這個概念。維基上有一個簡明的介紹，其中包含文本和圖表。我喜歡下面的解釋，它使用圖表直觀地闡述了分支預測器。
在計算機體系結構中，分支預測器是一種數字電路，它試圖猜測分支（例如if-then-else結構）在確定之前會走哪條路。分支預測器的目的是改善指令流水線中的流程。分支預測器在許多現代流水線微處理器架構（如x86）中實現高效性能方面發揮著關鍵作用。
雙向分支通常使用條件跳轉指令來實現。條件跳轉可以是“未採用”並繼續執行第一個代碼分支，緊接在條件跳轉之後，或者可以“採取”並跳轉到程序存儲器中的不同位置，其中第二個代碼分支是存儲。在計算條件並且條件跳轉已經過指令流水線中的執行階段之前，不確定是否採取條件跳轉是未知的（見圖1）。
基於所描述的場景，我編寫了一個動畫演示，以顯示在不同情況下如何在管道中執行指令。
- 沒有分支預測器。
在沒有分支預測的情況下，處理器必須等到條件跳轉指令已經通過執行階段，然後下一條指令才能進入流水線中的獲取階段。
該示例包含三條指令，第一條是條件跳轉指令。後兩條指令可以進入流水線，直到執行條件跳轉指令。
完成3條指令需要9個時鐘週期。
- 使用分支預測器，不要進行條件跳轉。讓我們假設預測沒有採取條件跳躍。
完成3條指令需要7個時鐘週期。
- 使用分支預測器並進行條件跳轉。讓我們假設預測沒有採取條件跳躍。
完成3條指令需要9個時鐘週期。
在分支錯誤預測的情況下浪費的時間等於從提取階段到執行階段的管道中的階段的數量。現代微處理器往往具有相當長的流水線，因此誤預測延遲在10到20個時鐘週期之間。因此，使管道更長時間增加了對更高級分支預測器的需求。
如您所見，似乎我們沒有理由不使用Branch Predictor。
這是一個非常簡單的演示，闡明了Branch Predictor的基本部分。如果這些GIF很煩人，請隨時將它們從答案中刪除，訪問者也可以從git獲取演示git
在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
由於稱為分支預測的現象，排序的陣列比未排序的陣列處理得更快。
分支預測器是一種數字電路（在計算機體系結構中），試圖預測分支將採用哪種方式，從而改善指令流水線中的流量。電路/計算機預測下一步並執行它。
做出錯誤的預測會導致返回上一步，並執行另一個預測。假設預測正確，代碼將繼續下一步。錯誤的預測導致重複相同的步驟，直到發生正確的預測。
你的問題的答案很簡單。
在未排序的數組中，計算機會進行多次預測，從而導致出錯的可能性增加。然而，在排序中，計算機進行的預測更少，從而減少了出錯的可能性。進行更多預測需要更多時間。
分類陣列：直道
____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
未排序的陣列：彎曲的道路
______ ________
| |__|
分支預測：猜測/預測哪條道路是直的並且在沒有檢查的情況下跟隨它
___________________________________________ Straight road
|_________________________________________|Longer road
雖然兩條道路都到達同一目的地，但直道較短，而另一條道路較長。如果那時你錯誤地選擇了另一個，那麼就沒有回頭了，所以如果你選擇更長的路，你會浪費一些額外的時間。這與計算機上發生的情況類似，我希望這有助於您更好地理解。
更新：在@Simon_Weaver所說的之後，我想添加另一個事實......“它不會做出更少的預測 - 它會減少不正確的預測。它仍然需要預測每次循環。”