JAVA分支预测

指令管道

代码最终都会转化为CPU可识别的指令，也就是机器码。

CPU跑代码原始的做法是单个processer串行处理指令，一个指令处理完了再加载下一个进行处理。

这里一个可以优化的点在于：

执行一条指令有四个步骤，fetch、decode、execute、encode。这四个步骤由不同的处理器单元执行，比如decode由指令解码器执行。让多个处理单元一起忙碌起来就可以实现“指令集并行”。

指令管道就是基于这个点进行优化，它让processer在执行一个命令的同时就加载好下一条命令。

比如：

int a = 0;
a += 1;
a += 2;
a += 3;			

相比串行执行，它只要7个时钟周期：

	1	2	3	4	5	6	7
a = 0	F	D	E	S
a += 1		F	D	E	S
a += 2			F	D	E	S
a += 3				F	D	E	S

可以看出，在第4个时钟周期，所有用到的处理器单元全都执行了起来，效率拉满。

指令管道的缺点

如果出现某些指令的执行需要依赖之前指令的时候，就会出现问题，比如最经典的 if 语句，CPU无法判断下面指令到底是哪部分。

假设代码：

int a = 0;
a += 1;
if (a < 10) {
  a += 2;
}
a += 3;

因为CPU无法判断后续代码，所以指令管道所做的指令集并发优化在if语句这里失效了。

	1	2	3	4	5	6	7	8	9	10	11
a = 0	F	D	E	S
a += 1		F	D	E	S
if(a < 10)			F	D	E	S
a += 2							F	D	E	S
a += 3								F	D	E	S

分支预测

碰见 if 就串行也不是办法，如果现在有一个排序好的数组，里面有1~100，遍历1~90，不考虑直接遍历1~90的写法，会写成：

for(int i = 0; i < 100; i++){
    if(i < 90){
		//todo
	}
}

那CPU可以大胆的先预测 if(i < 90) 这条执行后面一定是if代码块内的指令。

继续上面的例子，用了分支预测后，如果预测正确，指令流图可以变为：

	1	2	3	4	5	6	7	8	9
a = 0	F	D	E	S
a += 1		F	D	E	S
if(a < 10)			F	D	E	S
a += 2				F	D		E	S
a += 3					F	D		E	S

可以发现同样的代码，快了两个时钟周期，也就是19%。

如果把 a < 10，改成 a >10，预测错误的话，指令流图就变为：

	1	2	3	4	5	6	7	8	9	10
a = 0	F	D	E	S
a += 1		F	D	E	S
if(a > 10)			F	D	E	S
a += 2				F	D
a += 3							F	D	E	S

当if指令执行结束，发现自己加载了错误的后续指令，则要将之抛弃然后重新执行，这里退化为串行。

可以发现，如果预测错误的话，虽然从人的角度看，a+=2这块没执行，CPU做了更少的工作，但是从执行的时钟周期看，消耗的时间更久了。

JAVA中的实际应用

遍历存储了一到一千万的链表，如果当前值小于五百万，则把cnt++。链表分为有序和无序。

        int len = 10000000;
        List<Long> numbers = LongStream.range(0, len).boxed().collect(Collectors.toList());
        Collections.shuffle(numbers);
        long time = System.currentTimeMillis();
        int size = len / 2, cnt = 0;
        for (Long num : numbers) {
            if (num < size) {
                cnt++;
            }
        }
        System.out.println(System.currentTimeMillis() - time);

Sorted : 41ms Shuffle: 197ms

快了大约五倍。

虽然这里场景很理想化，但是实际运用中还是有一些场景可以使用它来优化CPU。

比如一个存了10e个long值的大文件，每个long用换行隔开，现在去读10e个long。那么每读到一个字节，就要判断这是数字还是换行符，这里的分支预测，不管预测到的是数量众多（约为10e*20）的数字，还是10e个换行符，都要进行大量的discard、start over操作。这里可以考虑直接用do while干掉 if 判断，实测IO可以加速一倍左右。

分支顺序

我们往往会理想化的认为，多个if else要把概率最大的放在前面，比如：

if(mostLikely){
	//todo
}else if (lessLikeLy){
	//todo
}else if(leastLikely){
	//tod
}

其实大可不必，CPU的分支预测用了分支预测缓存，顺序对代码效率影响不大。

举例：

    int len = 10000000;
    List<Long> numbers = LongStream.range(0, len).boxed().collect(Collectors.toList());
    Collections.shuffle(numbers);
    long time = System.currentTimeMillis();
    int size = (int) (len * 0.90), low = 0, high = 0;
    for (Long num : numbers) {
        if (num > size) { //改成小于号执行时间依然无变动
            low++;
        }else{
            high++;
        }
    }
    System.out.println(System.currentTimeMillis() - time);

多重条件判断

直接下结论，速度随着条件数增长而增长。

假设两个长度为一千万的数组，里面随机部分的数是0，现在我们要遍历判断两个数组同样位置都是0的个数。

直接写法，用时80ms：

        int len = 10000000;
        long[] arr0 = LongStream.range(0, len).map(n -> Math.random() < 0.5 ? 0 : n).toArray();
        long[] arr1 = LongStream.range(0, len).map(n -> Math.random() < 0.5 ? 0 : n).toArray();

        long time = System.currentTimeMillis();
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            if(arr0[i] == 0 && arr1[i] == 0){
                cnt++;
            }
        }
        System.out.println(System.currentTimeMillis() - time);
    }

多重条件优化成一个条件，用时20ms：

        int len = 10000000;
        long[] arr0 = LongStream.range(0, len).map(n -> Math.random() < 0.5 ? 0 : n).toArray();
        long[] arr1 = LongStream.range(0, len).map(n -> Math.random() < 0.5 ? 0 : n).toArray();

        long time = System.currentTimeMillis();
        int cnt = 0;
        for (int i = 0; i < len; i++) {
            if(arr0[i] * arr1[i] == 0){
                cnt++;
            }
        }
        System.out.println(System.currentTimeMillis() - time);
    }

总结

大循环的情况，可以尝试不用分支。
不用考虑if else 先后问题，不影响性能。
判断条件个数尽可能的少。

CPU经典优化手段之一