17.CPU与分支预测

一段有趣的代码

有这样一段代码：

这段代码非常简单，给定一个数组，计算所有大于256 的元素之和，重复计算 10000 遍。

这段代码本身平淡无奇，但有趣的是：如果这个数组是有序的，那么这段代码的运行速度会比处理无序数组快将近 10 倍(不同的机器、CPU架构可能会稍有差异)。

可这是为什么呢？这和制造业使用的流水线又有什么关系呢？且听我慢慢道来。

1769年，英国人乔赛亚·韦奇伍德开办了一家陶瓷工厂，这家工厂生产的陶瓷乏善可陈，但其内部的管理方式极具创新性，传统的方法都是由制陶工专人来完成，但韦奇伍德研究后将整个制陶工艺流程分成了几十道工序，每一道工序都交给专人完成，这样传统的制陶人不复存在，这便是工业流水线最早的雏形。

发扬光大

虽然流水线技术可以说是英国人发明的，但发扬光大的却是美国人，这便是福特与T型车。

20世纪初，福特将流水线技术应用到汽车的批量生产，效率得到千倍提高，使得汽车这种奢侈品开始能够为大众消费，深刻影响了现代社会的方方面面，注意上图中一辆车的价格。。。

100 年后又一个美国人携带他的时尚电动车再一次席卷全球，这就是特斯拉。

接下来我们仔细看一下流水线技术。

特斯拉与流水线

假设组装一辆特斯拉需要经过：组装车架、安装引擎、安装电池、检验四道工序，同时假设每个步骤需要 20 分钟，因此如果所有工序都由一个组装站点来完成，那么组装一辆特斯拉需要80分钟。

但如果每个步骤都交给一个特定站点来组装的话就不一样了，此时生产一辆车的时间依然是80分钟，但这只是第一辆车所需要的时间，此后工厂可以每20分钟就交付一辆特斯拉。

注意，流水线并没有减少组装一辆车的时间，只是增加了工厂的吞吐能力。

流水线技术的使用极大增加了工厂交付车辆的效率。

其实 CPU 本身也是一座超级工厂。

只不过CPU这座工厂生产的不是特斯拉，而是机器指令。

工厂内部有流水线极大提高了生产效率，CPU 没有理由不拥有。

你可以想象一下，不管你现在看这篇文章用的是PC 还是智能手机，其内部的 CPU 都有一条复杂度不亚于特斯拉超级工厂的流水生产线。

如果特斯拉超级工厂也如 CPU 一般高效的话，特斯拉可能比现在的自行车都要便宜，地球人民人手一辆特斯拉不成问题，算上外星人也不成问题。

机器指令与流水线

实际上说 CPU 生产机器指令是不正确的，CPU 其实不是在生产机器指令而是在处理机器指令，生产机器指令的是编译器，CPU需要处理机器指令以此来指挥整个计算机系统工作。

同生产一辆特斯拉需要四道工序一样，处理一条机器指令大体上也可以分为四个步骤：取指、译码、执行、回写，这几个阶段分别由特定的硬件来完成 (注意，真实 CPU 内部可能会将执行一条指令分解为数十个阶段)。

怎么样，是不是和超级工厂生产特斯拉没什么区别，当今CPU用每秒处理数十亿机器指令的能力驱动着智能手机好让你流畅的刷公众号、短视频、刷微博、刷知乎，这里，流水线技术功不可没。

实际上 CPU 内部的流水线和现实中的并不完全一样。

程序员在代码中编写的 if 语句一般会被编译器翻译成一条跳转指令， if 语句其实起到一种分支的作用，如果条件成立则需要执行if内部的逻辑，否则不执行；因此跳转指令会依赖自身的执行结果来决定到底要不要跳转，这会对流水线产生影响。

有的同学可能不明白，这能产生什么影响呢？

现在，让我们仔细观察一下特斯拉流水线，你会发现当前一辆车还没有完全制造完成时后一辆车就已经进入到流水线了。

对于CPU来说道理是一样的，当一条跳转指令还没有完成时后面的指令就需要进入到流水线，因此问题来了：

跳转指令需要依赖自身的执行结果来决定到底要不要跳转，那么在跳转指令没有执行完的情况下 CPU 怎么知道后面哪个分支的指令能进入到流水线呢？

CPU 能预测未来吗？

预测未来

对此 CPU 当然是不知道的。

那么该怎么办呢？

很简单，一个字，猜。

你没有看错，CPU 会猜一下 if 语句可能会走哪个分支，如果猜对了流水线照常继续，如果猜错了，对不起，流水线上已经执行的后续指令全部作废，因此我们可以看到如果CPU猜错了会有性能损耗。

现代 CPU 将“猜”的这个过程称为分支预测。

当然，CPU 中的分支预测并不是简单的抛硬币式的随机瞎猜，而且有特定策略，比如可能会基于执行跳转指令的历史去进行预测等等。

知道了分支预测就可以解释文章开头的问题了。

CPU 在执行完跳转指令之前必须决定后续哪个分支的指令会进入到流水线，猜对了流水线照常进行，猜错了有性能损耗。

那么如果一个数组是有序的：

而如果一个数组是无序的：

你觉得哪种更好猜一些？

如果你给CPU一个无序数组，那么 Arr[i] 是否大于256 基本上就是随机的，对于随机事件，不要说 CPU的分支预测，任何其它预测手段都将无效，否则这就不是随机事件了。

如果 CPU 猜的不对，那么流水线上的后续指令将作废，这就解释了为什么处理有序数组要比处理无序数组性能好了，因为在数组有序的情况下，CPU 的分支预测几乎不会猜错，流水线上的指令不会被频繁作废。

这对程序员的启示就是：如果你编写了 if 语句，那么你最好让 CPU 大概率能猜对。

有的同学看到这里，可能会觉得每一条 if 语句都性能低下，恨不得从此不再写if else，真的是这样吗？

编写 If else时需要注意什么

实际上如果你编写的if语句没有位于对性能要求很高的核心代码部分，那么分支预测失败这种问题无需关心。

实际上现代 CPU 的分支预测是很聪明的，对于非核心部分的if 语句分支预测失败带来的性能损失可以忽略不计。

但是对于文章开头提到的代码，程序的大部分时间都用在了 for 循环中，这时你就要注意了，当然前提还是这段代码对时间要求非常严苛，否则你也没必要为了这点性能去优化。

好奇的同学可能会问，如果给定的数组是无序的，那么上面提到的这段该怎么优化呢？

性能优化

实际上非常简单，只需要移除 if 语句就可以，该怎么移除呢？

没有 if 语句的话，那么 sum 每次都必须加上一个数，如果arr[i]比256大，那么 sum 加上差值，否则sum 加 0即可，这样就消除了if 判断。

我们计算arr[i] - 256的值，并将其向右移动31位:

这样得到的数不是0 (0x00000000)，就是 -1 (0xffffffff)，然后我们对其取反，再次与上 arr[i] 即可：

也就是说如果arr[i] - 256 大于0 的话那么差值会与上 0xffffffff，其结果就是保持不变，否则会与上0，其结果就是sum会加上0，这样就不需要 if 判断了。

利用位运算，即使数组是无序的也不会有性能问题，代价就是代码可读性会降低很多，这里，我们再一次看到天下没有免费的午餐。

虽然 CPU 体积很小，只有指甲那么大，但 CPU 可能是人类有史以来建造过的最复杂的东西，在这里 实现了很多有趣的功能，程序员只有彻底理解 CPU 才能更好的利用这些功能编写性能优异的程序。