Chapter 5.5 Branch Predictions

现代处理器的工作远超前于当前正在执行的工作，从内存读指令，译码指令，以确定在什么操作数上执行什么操作。只要指令遵循的是一种简单的顺序，那么这种指令流水线化就能很好地工作。当遇到分支时，处理器必须猜测分支该往哪个方向走。我们这里主要讨论条件分支，即预测是否会选择分支。

分支预测错误处罚的代价很高，因此要求预测的准确率要尽可能高。事实上，现代处理器采用一种简单的预测方式，它的准确度可以达到95%：

当然，仅仅依靠机器的分支预测并不能保证程序性能良好，程序员本身也要尽量写分支较少或有利于分支预测准确性的代码。

Transform Branches

有时分支可以通过一些巧妙的运算变换为顺序执行的代码，例如：

for (int c=0; c < size; ++c) 
{
    if (data[c] >= 128)
        sum += data[c];
}

通过位运算等技巧，分支完全可以消除：

 int t = (data[c] -128) >> 31;
 sum += ~t & data[c];

同时，针对上例，如果不采用分支转化的方法，我们也要尽量依循处理器的分支预测方法，设置更易预测的读取数据。例如：

我们可以把输入数据从这样的

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, ...（完全乱序，毫无规律可循🥲）

改成这样的

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, ...（增序序列，预测轻松多了~）

编译器也会对分支进行一些优化，典型的操作是用cmov条件传送指令替换分支。例如：

 int absdiff(int x, int y) 
 {
    int result;
    if (x > y) 
       result = x -y;
    else 
       result = y -x;
    return result;
 }

其优化后的汇编代码如下：

absdiff:
 mov    edx, edi
 sub    edx, esi
 mov    eax, esi
 sub    eax, edi
 cmp    edi, esi
 cmovg  eax, edx

但是，这种方式并不一定都有效，因为条件传送指令需要一开始就将两种情况的结果计算出来，当不需要被执行的分支计算量很大时，这样做显然是不划算的。

这一章的内容到这里就结束了，相信大家现在对于程序性能优化有了更深刻的认识！🎉