CPU 分支预测

在JAVA数组遍历过程中，排序过后的数组处理起来更快，stackoverflow上有个问题——为什么已排序数组比未排序数组处理起来更快？，本文将对此问题和mysticial的回答翻译，并以此为基础稍微补充展开。

问题：为什么排序后的数组处理起来更快

下面是原问题，仅保留Java的问题实现部分，关于C++的请自行查看原文。

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;

        // !!!添加以下排序，程序会快很多
        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);
    }
}

我自己用Eclipse跑一下结果，结果耗时：#1 排序：2.712352148；#2 未排序：14.459905408

答案：分支预测（Branch Prediction）

什么是分支预测

想象一下铁路分叉口：

Image by Mecanismo, via Wikimedia Commons. Used under the CC-By-SA 3.0 license.

现在为了方便讨论，假设这是回到19世纪 – 在远距离或无线电通信尚未普及之前。你是一个交汇处的扳道工，听到火车来，但你不知道它该走哪条路。你叫停火车，问清司机行驶方向，然后设置轨道。

火车很重，有很大的惯性，所以一路上一直加速和减速。

有更好的方法吗？ 你猜火车哪个方向去！

• 如果猜到，继续。
• 如果猜错，停下来并后退，然后重设轨道。 火车重新启动驶入路径。

对于一个if条件语句，在处理器级别，它是一个分支指令：

如果你是一个处理器，看到一个分支时并不知道选哪一个。 于是暂停执行并等待，直到前面的选择指令完成，然后继续执行正确的路径。

但是，现代处理器复杂且具有长流水线（pipelines），所以会一直“减速”“加速”，很浪费时间。分支预测器让使用指令流水线处理器的性能提高。

分支预测器猜测两路分支中哪一路最可能发生，然后投机执行这一路的指令，来避免流水线停顿造成的时间浪费。如果后来发现分支预测错误，那么流水线中投机执行的那些中间结果全部放弃，重新获取正确的分支路线上的指令开始执行，这招致了程序执行的延迟。

现代处理器的分支预测方法依赖于代码执行的动态历史信息。大多数应用程序具有良好的分支， 因此，分支预测器通常会实现> 90%的命中率。 但是当面对不可预知的分支，没有可识别的模式，分支预测器实际上是无用的。

更多参见维基百科分支预测器词条，介绍了多种分支预测的实现方法。

原因是if条件语句

综上所述，罪魁祸首是这个if条件语句：

if (data[c] >= 128)
    sum += data[c];

注意，数据均匀分布在0和255之间。当数据排序后，大致上半个迭代将不会进入if语句； 之后，数据均将进入if语句。

这对分支预测器非常友好，因为分支连续地沿着相同的方向多次行进。除了在切换方向之后的几个迭代， 一个简单的饱和计数器都能正确地预测分支结果。

简要分析一下：

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3 ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (很容易预测)

然而，当数据完全随机时，分支预测器毫无用处，因为它不能预测随机数据。 结果是可能会有大约50%的误预测，不比随机猜测更好。

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14 ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N ...

       = TTNTTTTNTNN ...   (完全随机，无法预测)

优化方案

通过位运算来避免分支预测，用下面代码来提换if条件语句：

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

介绍相关的按位操作符和移位操作符，均在二进制中进行：

结果大家可以自行测试。

在大数据处理过程中，要尽量避免使用if条件语句产生分支。