问题
来源 ：stackoverflow
为什么下面代码排序后累加比不排序快？
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);
}
在我电脑上没有排序耗时：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），这种技术叫做 流水线停顿。
分支预测器就是猜测条件判断会走哪一路，如果猜对，就避免流水线停顿造成的时间浪费。如果猜错，那么流水线中推测执行的那些中间结果全部放弃，重新获取正确的分支路线上的指令开始执行，这导致了程序执行的延迟。
