分支与switch

通过使用流水线，在执行指令之前的几个阶段中获取并解码指令，现代微处理器获得了高速。不过，流水线结构有一个大问题。一旦代码有一个分支（比如一个if-else结构），微处理器预先不知道向流水线输入哪个分支。如果错误的分支输入流水线，那么直到10 ~ 20时钟周期后，这个错误才被检测到，而在这期间完成的获取、解码以及指令预测工作纯就是无用功。结论是，一旦微处理器把错误分支输入流水线，结果是浪费了几个时钟周期。

微处理器设计者为减少这个问题，付出了很大的努力。最重要的方法是分支预测。基于该分支以及其他附近分支的历史，现代微处理器使用先进的算法来预测分支的方向。对每种微处理器，这些用于分支预测的算法是不相同的。这些算法在《Intel，AMD与VIA CPU微架构》中详细描述。

在微处理器做出了正确的预测时，分支指令通常需要0 ~ 2时钟周期。从分支误预测恢复的时间大约是12 ~ 25时钟周期，依赖于处理器。这称为分支误预测惩罚。

如果在大多数时间里都被预测到，分支的代价相对不高，但如果经常误预测，代价就高昂了。当然，总是去往相同方向的分支能良好预测。一个大多数时间去往一个方向，很少去另一个分析的分支，仅在它去往另一个方向时被误预测。一个去往一个方向许多次，然后去往另一个方向许多次的分支，仅在改变方向时被误预测。遵循一个简单周期性模式的分支也可以被相当好地预测，如果它在一个具有很少或没有其他分支的循环里。例如，一个简单周期性模式可以去往一个方向两次，另一个方向三次。然后再两次第一个方向，三次另一个方向，以此类推。最坏的情形是，分支随机去往一个方向，每个方向都有50%的机会。这样的分支将在50%时间里被误预测。

一个for循环或while循环也是一种分支。在每次迭代后，决定是重复还是退出循环。循环分支通常预测良好，如果重复计数小且总是相同。根据处理器的不同，在9到64之间变化的最大循环计数可以被完美预测。嵌套循环仅在某些处理器上被良好预测。在许多处理器上，一个包含几个分支的循环不能被良好预测。

swtich语句是一种去往超过2个方向的分支。switch语句是最高效的，如果case标签遵循一个序列，其中每个标签等于前面标签加一，因为它可以被实现为一个目标跳转表。带有许多彼此远离case值的switch语句是低效的，因为编译器必须将它转换为一棵分支树。

在较旧的处理器上，带有连续标签的switch语句只是被预测去往上次执行方向。因此，一旦它去往不同于上次的方向，就肯定被误预测。较新的处理器有时能够预测switch语句，如果它遵循一个简单周期性的模式，或者如果它与前面的分支相关且不同目标的数量少。

在程序的关键部分，最好将分支与switch语句保持在小的数量，特别在分支预测不好时。如果可以消除分支，展开一个循环是有益的。

分支与函数调用的目标被保存在一个特殊的称为分支目标缓冲的缓存里。如果程序有许多分支或函数调用，会出现分支目标缓冲冲突。这样冲突的结果是，分支会被误预测，即使它们本来可以被良好预测。甚至直接的函数调用也会因为这个原因被误预测。因此，在代码关键部分带有许多分支与函数调用的程序会因误预测而性能降低。

在某些情形里，使用查找表替换一个可预测性不好的分支是可能的。例如：

// Example 7.29a
float a; bool b;
a = b ? 1.5f : 2.6f;

这里 ?:操作符是一个分支。如果它的可预测性不好，使用一个查找表替换它。

// Example 7.29b
float a; bool b = 0;
const float lookup[2] = {2.6f, 1.5f};
a = lookup[b];

如果 bool 被用作一个数组索引，确保它被初始化或来自一个可靠的来源以使它不会有0或1以外的值是非常重要的。

在某些情形里，编译器可以自动使用一个条件移动替换一个分支。

后续会举例说明减少分支数的各种方法。《Intel，AMD与VIA CPU的微架构》给出了不同微处理器中分支预测的更多细节。

《optimizing cpp》