经典问题之「分支预测」-白红宇

问题

来源：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），这种技术叫做 流水线停顿。

分支预测器就是猜测条件判断会走哪一路，如果猜对，就避免流水线停顿造成的时间浪费。如果猜错，那么流水线中推测执行的那些中间结果全部放弃，重新获取正确的分支路线上的指令开始执行，这导致了程序执行的延迟。