在现代CPU中，为了提高执行的性能，CPU的多个单元会同时执行多条指令。例如当取址单元正在寻找下一条指令前，上一条指令的译码和执行已经在进行中了，这一套机制被称作CPU流水线（pipeline）。

CPU流水线架构把指令的执行分为了多个阶段，每个单元只负责完成指令执行过程中的一个阶段，而中间结果由专门的流水线寄存器暂存。这样理论上，一条指令的执行假设被分为5个阶段，那么当5个单元同时运行一段时间后，理论上相同时间可以同时执行5条指令，当然这只是最简单的情况，实际的情况要复杂得多。

流水线的引入相当于程序中引入了并发，相应的，会带来很多额外的问题。例如为了更好地让指令流水般地执行，不涉及顺序一致性的指令会被重排序。这里不详细讨论太多流水线的技术细节，只要知道指令并不是一条一条顺序执行的，那样会严重阻碍处理器的性能。

CPU流水线引入的目的在于，希望能够在每个CPU的时钟周期都发射一条新的指令，这样理论上可以达到最高效率。但这有一个前提：如果指令的执行是每个时钟周期一条，那么指令的取值也必须达到每个时钟周期一条，如此，当你在取址阶段拿到要执行的指令时，下一条指令的地址必须被确定了，否则下一个时钟周期便无法取出对应的指令。

这将引发一个问题：

对于条件跳转指令（汇编层面是JMP等，代码层面例如if），需要等当前的指令执行完才知道结果是true还是false，也就是说，要等待若干个时钟周期后，CPU才可以确定下一条要执行的指令究竟是哪个分支的。

难道这段时间就只能干等着吗？当然不是，这里CPU就会采取「分支预测」的方式，预测下一条要执行的分支指令，并预先执行，如果if执行完后发现和预测的分支一致，那就中大奖了，整个执行阶段一点都没有暂停。但如果悲剧地预测错误，那么这时候必须从取址开始，重新执行另一个分支的指令。

从中显然可以看出，预测错误消耗的代价要比干等着更大。

为了提高CPU预测的正确性，有多种算法，但是我们可以先思考一下最简单的方案。

首先，从常理上来考虑，如果遇到一个if分支，那么很有可能某一个分支的执行概率要大于另一个。这跟我们的编码风格有关，例如在校验参数是否合法的过程中，有的人喜欢嵌套if一直到满足一个最严格的条件，然后执行，这种情况对应了if为true的情况；另一种人喜欢先把其它条件都排除掉，例如null判断等，等不合法的都被排除后，这时候再执行，这种情况对应if为false的情况。

分支预测算法也类似，如果一个程序在80%的时间里总是选择了true的分支，那么下一次预测就更偏向于true的那个分支，分支预测的关键在于找到一种下一次分支选择的「模式」。事实上，有人试验过一种最简单的分支预测算法：总是选择true的分支，这种情况下分支预测的正确率在60%左右。

那么分支预测对于我们写代码有什么启示吗？这里让我想到了数据的局部性原理，也就是说刚刚被使用的数据，有可能被马上再次使用，回想一下，LRU Cache算法也是基于这个前提，分支预测的思想也差不多。

我们不妨来看一个简单的程序：

import java.util.Arrays;
import java.util.Random;

public class BranchPrediction {
        public static void main(String[] args) {
                Random random = new Random();
                int[] array = new int[1024 * 1024 * 20];
                for (int i = 0; i < array.length; i++) {
                        array[i] = random.nextInt();
                }
                sum(array);// warm up

                long start = System.nanoTime();
                sum(array);// Not Sorted
                System.out.println(System.nanoTime() - start);

                Arrays.sort(array);
                start = System.nanoTime();
                sum(array);// Sorted
                System.out.println(System.nanoTime() - start);
        }

        private static long sum(int[] array) {
                long sum = 0L;
                for (int i = 0; i < array.length; i++) {
                        if (array[i] < 128) {
                                sum += array[i];
                        }
                }
                return sum;
        }
}

代码的意图很简单，对一个随机数构成的数组，求小于128的数字之和。

那么数组排序与否，对累加的性能有什么影响吗？这段代码在我的电脑上执行的结果是：

未排序的数组：85612910ns

排序过的数组：20390006ns

性能差了4倍多，原因经过上面的论述也很明确了，关键在于这一句：

if (array[i] < 128)

当数组没有被排序时，这个if会随机地导向不同的分支，可以想见，CPU的分支预测将会连连受挫。

而数组被排序后，数组前半部分都走到true的分支，后半部分都走到false的分支，分支预测的效果将会相当好。

类似的CPU优化还有很多，例如cacheline、多级cache等等，有时候你要去利用它们，有时候反而要避免它们的「自作聪明」带来的成本，以后再来写写吧。