什么是分支预测
现象描述
java - Why is it faster to process a sorted array than an unsorted array? - Stack Overflow
StackOverflow上的一个问题描述：
下边这段代码是用来对一大批数据求和的。
由于只是逐项求和，本来不需要排序，但是原提问者发现排序前后程序运行时间差距非常大。
import java.util.Arrays;
import java.util.Random;
public class Main
{
public static void main(String[] args)
{
// 初始化数组
int arraySize = 32768;
int data[] = new int[arraySize];
// 生成随机数
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
data[c] = rnd.nextInt() % 256;
// ！！排序，这里是否排序对运行时间影响很大
// Arrays.sort(data);
// 开始测试，使用nanoTime计时
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int c = 0; c < arraySize; ++c)
{
// 这里有个if判断值是否大于等于128
if (data[c] >= 128)
sum += data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}
原提问者使用C++版本的这段代码测试，排序前耗时11.54秒，排序后耗时1.93秒，排序后耗时仅为排序前的1/6，很夸张。
原提问者使用Java版本的代码测试，耗时差距同样存在，但没有C++代码中差距那么夸张。（我在自己电脑上跑这段Java代码，排序前耗时11.086969378，排序后耗时4.948412084）
现象解释
高票回答内容简述：
假设你是铁轨分支的操作员，一辆火车开过来了，但你不知道它应该往哪边走，也无法远距离跟列车长交流，这时候你有两个选项：
1.让列车长停车，告诉你他去哪，然后你把铁轨切换到正确的分支
首先明确一点，火车很重，启动和制动都需要花费很长的时间。
少数几次停车问路也许看起来对火车运行效率没有太大影响，但如果有一万辆火车要经过呢，如果像上述代码里有10w*arraySize次呢？有没有更好的方法能够减少停车次数呢？
2.你猜测火车应该向哪个分支前进，如果猜对了火车就开走了，如果猜错了火车只好倒回来，切换轨道后继续前进
如果猜对了，上述停车、启动消耗的时间都消失了，火车奔驰而过，大家省时省力，其乐融融。
不过一旦猜错了，付出的代价会比停车问路更大，因为火车得花更多时间倒回来，再重新启动。
回到原问题，在处理器中，程序运行到分支语句时，同样需要面临这样的选择——停车问路或预测分支。
同样，如果选择预测分支，“也许”可以节省非常多的处理器时间，这取决于预测的准确性：
- 如果每次都预测正确，程序执行就可以完全不用中途停下
- 如果频繁预测错误，那就需要花很多时间在回滚、重启上
在现实中，如果一辆火车能通过转向灯通知铁轨分支操作员该往哪边转，那么分支显然很容易“预测”。
然而处理器是不可能提前知道分支方向的，那怎么办？只好靠历史路线来判断：
- 如果这辆车在过去99%次都走左边，那就猜这次还是走左边
- 如果左右交替，那就猜左右交替
- 如果每三次有一次走左边，就每三次猜一次左边
- ......
一旦程序运行逻辑有较明确的规律，就可以很好地进行分支预测，比如：
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
回到原程序，排序后的数组前半段都不会命中if分支，后半段都会命中if分支，这时候如果分支预测起作用，那么可以节约很多时间。
如果规律不明确，那么很难进行预测，每次都需要等待分支条件计算完毕：
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
补充
CPU如何通过分支预测提高效率
在遭遇分支时，CPU的分支预测器根据历史模式（Pattern）预测可能性最高的分支，然后依靠指令流水线实现一边计算分支中的判断条件，一边已经进入最有可能的分支开始了接下来的“投机性计算”。
如果最后预测错误，那么投机性计算结果将被抛弃，重新进入正确的分支进行计算。在现代处理器中，流水线级数很长，一次分支预测失败可能损失20个左右的时钟周期。
如何优化大循环
高票回答中提到，在量级非常大的循环中，应该尽量减少强数据依赖的分支判断，比如上文中的无序数组元素的大小判断。
他还提到可以去掉原代码中的if判断而改为位操作：
// if (data[c] >= 128)
// sum += data[c];
// 替换为位操作
int t = (data[c] - 128) >> 31; // 通过符号计算来判断是否大于等于128
sum += ~t & data[c];
将if判断改为位操作后，是否排序对计算效率就没有影响了，运行时间与原本有排序、带if判断的代码基本一样。（我的位操作版Java代码实际运行时间大约2.795012342，甚至比原本带if带排序的4.948412084还快，个人猜测是由于完全规避了分支语句）
关于switch语句的预测
编译器对于switch语句的实现可能有三种：逐条件判断、跳转表、二分查找，本质是根据索引找到相应的代码地址并跳转，对于CPU分支预测不友好，因此如果能人为凭经验判断概率高的分支，可以将这个分支提到switch语句外，使用if语句判断，帮助分支预测器更好地工作。
参考资料
java - Why is it faster to process a sorted array than an unsorted array? - Stack Overflow
【Java深入学习系列】之CPU的分支预测(Branch Prediction)模型 - 个人文章 - SegmentFault 思否
优化技巧：提前if判断帮助CPU分支预测 - 横云断岭的专栏 - CSDN博客
C++性能榨汁机之switch语句的背后 - I'm Root lee !
本文搬自我的博客，欢迎参观！
