请看这样一段代码
#include <algorithm>
#include <chrono>
#include <iostream>
constexpr size_t RANGESZ = 10000;
int main() {
const unsigned arraySize = 32768;
int data[arraySize];
for (int &c : data) {
c = std::rand() % 256;
}
std::sort(data, data + arraySize); // 560ms
// std::sort(data, data + arraySize); // 1875ms
long long sum = 0;
auto start = std::chrono::steady_clock::now();
for (unsigned i = 0; i < RANGESZ; ++i) {
for (unsigned c = 0; c < arraySize; ++c) {
if (data[c] >= 128)
sum += data[c];
}
}
auto end = std::chrono::steady_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "time = " << elapsed.count() << "ms" << std::endl;
std::cout << "sum = " << sum << std::endl;
}我们用 256 的模数随机填充一个固定大小的大数组，然后对数组的一半元素求和。
先排序后计算，运行效率有进3倍的提高。
为什么呢？
为了论证此问题，让我们回到19世纪，那个远距离无线通信还未普及的年代。你是铁路交叉口的扳道工。当听到火车快来了的时候，你无法猜测它应该朝哪个方向走。于是你叫停了火车，上前去问火车司机该朝哪个方向走，以便你能正确地切换铁轨。
要知道，火车是非常庞大的，切急速行驶时有巨大的惯性。为了完成上述停车-问询-切轨的一系列动作，火车需耗费大量时间减速，停车，重新开启。
既然上述过车非常耗时，那是否有更好的方法？当然有！当火车即将行驶过来前，你可以猜测火车该朝哪个方向走。
- 如果猜对了，它直接通过，继续前行。
- 如果猜错了，车头将停止，倒回去，你将铁轨扳至反方向，火车重新启动，驶过道口。
如果你不幸每次都猜错了，那么火车将耗费大量时间停车-倒回-重启。如果你很幸运，每次都猜对了呢？火车将从不停车，持续前行！
上述比喻可应用于处理器级别的分支跳转指令里：
原程序：
if (data[c] >= 128)
sum += data[c]; 汇编码：
cmp edx, 128
jl SHORT $LN3@main
add rbx, rdx
$LN3@main:让我们回到文章开头的问题。现在假设你是处理器，当看到上述分支时，当你并不能决定该如何往下走，该如何做？只能暂停运行，等待之前的指令运行结束。然后才能继续沿着正确地路径往下走。
要知道，现代编译器是非常复杂的，运行时有着非常长的pipelines， 减速和热启动将耗费巨量的时间。
那么，有没有好的办法可以节省这些状态切换的时间呢？你可以猜测分支的下一步走向！
- 如果猜错了，处理器要flush掉pipelines, 回滚到之前的分支，然后重新热启动，选择另一条路径。
- 如果猜对了，处理器不需要暂停，继续往下执行。
如果每次都猜错了，处理器将耗费大量时间在停止-回滚-热启动这一周期性过程里。如果侥幸每次都猜对了，那么处理器将从不暂停，一直运行至结束。
上述过程就是分支预测(branch prediction)。虽然在现实的道口铁轨切换中，可以通过一个小旗子作为信号来判断火车的走向，但是处理器却无法像火车那样去预知分支的走向--除非最后一次指令运行完毕。
那么处理器该采用怎样的策略来用最小的次数来尽量猜对指令分支的下一步走向呢？答案就是分析历史运行记录： 如果火车过去90%的时间都是走左边的铁轨，本次轨道切换，你就可以猜测方向为左，反之，则为右。如果在某个方向上走过了3次，接下来你也可以猜测火车将继续在这个方向上运行...
换句话说，你试图通过历史记录，识别出一种隐含的模式并尝试在后续铁道切换的抉择中继续应用它。这和处理器的分支预测原理或多或少有点相似。
大多数应用都具有状态良好的(well-behaved)分支，所以现代化的分支预测器一般具有超过90%的命中率。但是面对无法预测的分支，且没有识别出可应用的的模式时，分支预测器就无用武之地了。
优化
利用位运算取消分支跳转。基本知识：
|x| >> 31 = 0 # 非负数右移31为一定为0
~(|x| >> 31) = -1 # 0取反为-1
-|x| >> 31 = -1 # 负数右移31为一定为0xffff = -1
~(-|x| >> 31) = 0 # -1取反为0
-1 = 0xffff
-1 & x = x # 以-1为mask和任何数求与，值不变故分支判断可优化为：
int t = (data[c] - 128) >> 31; # statement 1
sum += ~t & data[c]; # statement 2分析：
- data[c] < 128, 则statement 1值为: 0xffff = -1, statement 2等号右侧值为: 0 & data[c] == 0;
- data[c] >= 128, 则statement 1值为: 0, statement 2等号右侧值为: ~0 & data[c] == -1 & data[c] == 0xffff & data[c] == data[c];
故上述位运算实现的sum逻辑完全等价于if-statement, 更多的位运算hack操作请参见bithacks.
若想避免移位操作，可以使用如下方式：
int t=-((data[c]>=128)); # generate the mask
sum += ~t & data[c]; # bitwise AND结论
- 使用分支预测: 是否排序严重影响performance
- 使用bithack: 是否排序对performance无显著影响
这个例子告诉给我们启示: 在大规模循环逻辑中要尽量避免数据强依赖的分支(data-dependent branching).
补充知识
Pipeline
先简单说明一下CPU的instruction pipeline(指令流水线)，以下简称pipeline。 Pipieline假设程序运行时有一连串指令要被运行，将程序运行划分成几个阶段，按照一定的顺序并行处理之，这样便能够加速指令的通过速度。
绝大多数pipeline都由时钟频率(clock)控制，在数字电路中，clock控制逻辑门电路(logical cicuit)和触发器(trigger), 当受到时钟频率触发时，触发器得到新的数值，并且逻辑门需要一段时间来解析出新的数值，而当受到下一个时钟频率触发时触发器又得到新的数值，以此类推。
而借由逻辑门分散成很多小区块，再让触发器链接这些小区块组，使逻辑门输出正确数值的时间延迟得以减少，这样一来就可以减少指令运行所需要的周期。 这对应Pipeline中的各个stages。
一般的pipeline有四个执行阶段(execuate stage): 读取指令(Fetch) -> 指令解码(Decode) -> 运行指令(Execute) -> 写回运行结果(Write-back).
分支预测器
分支预测器是一种数字电路，在分支指令执行前，猜测哪一个分支会被执行，能显著提高pipelines的性能。
条件分支通常有两路后续执行分支，not token时,跳过接下来的JMP指令，继续执行， token时，执行JMP指令，跳转到另一块程序内存去执行。
为了说明这个问题，我们先考虑如下问题。
没有分支预测器会怎样？
加入没有分支预测器，处理器会等待分支指令通过了pipeline的执行阶段(execuate stage)才能把下一条指令送入pipeline的fetch stage。
这会造成流水线停顿(stalled)或流水线冒泡(bubbling)或流水线打嗝(hiccup)，即在流水线中生成一个没有实效的气泡。
常见的分支预测器
- 静态分支预测器
- 双模态预测器(bimodal predictor) 也叫饱和计数器，是一个四状态状态机. 四个状态对应两个选择: token, not token， 每个选择有两个状态区分强弱：strongly,weakly。分别是Strongly not taken，Weakly not taken, Weakly taken, Strongly taken。
位运算 Hack
http://graphics.stanford.edu/~seander/bithacks.html
