流水线中的分支预测

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

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

400px-5_Stage_Pipeline.svg

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

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等等,有时候你要去利用它们,有时候反而要避免它们的「自作聪明」带来的成本,以后再来写写吧。

发表评论

电子邮件地址不会被公开。