問題

來源 ：stackoverflow
為什么下面代碼排序后累加比不排序快？

public static void main(String[] args) {// Generate dataint 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 fasterArrays.sort(data);// Testlong start = System.nanoTime();long sum = 0;for (int i = 0; i < 100000; ++i){// Primary loopfor (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);}
復制代碼

在我電腦上沒有排序耗時：10.78390589
排序后耗時：4.552145206

出現上面這個時長差異的罪魁禍首就是這段代碼 ：

if (data[c] >= 128)sum += data[c];
復制代碼

排序后數據的示例：

T = 表示進入分支
N = 表示未進入分支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  (容易去預測)
復制代碼

沒有排序數據的示例：

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 ...   (全是隨機數據 - 很難去預測)
復制代碼

假如我們把代碼里條件判斷換成下面代碼：

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
復制代碼

沒有排序耗時：2.698193263
排序后耗時 ：2.753661927
說明沒有用到條件判斷語句沒有排序和排好序的耗時很相近。
在現代處理器中，都引入了分支預測來提高指令流水線的性能。所以就導致排序后比沒有排序快。

分支預測

條件分支指令通常具有兩路后續執行分支。即不采取（not taken）跳轉，順序執行后面緊挨JMP的指令；以及采取（taken）跳轉到另一塊程序內存去執行那里的指令。
是否需要跳轉，只有到真正執行時才能確定。如果沒有分支預測器，處理器將會等待分支指令通過了指令流水線的執行階段，才把下一條指令送入流水線的第一個階段—取指令階段（fetch stage），這種技術叫做 流水線停頓。
分支預測器就是猜測條件判斷會走哪一路，如果猜對，就避免流水線停頓造成的時間浪費。如果猜錯，那么流水線中推測執行的那些中間結果全部放棄，重新獲取正確的分支路線上的指令開始執行，這導致了程序執行的延遲。