为了便于讨论，假设现在是1800年，这时候还没有出现远程或广播通讯工具。 你是一个铁路枢纽的工人。当你听到火车开来时，你不知道这个火车要走哪一条路，只有让火车停下来询问列车长火车要开往哪，最后你将轨道切换到相应的方向。 火车的质量非常大，固惯性很大，因此火车需要经常性的加速减速。 有没有更好的方法喃？可以猜火车将行驶的方向应该是可行的！
考虑一个if语句：在处理器级别上，他是一个分支指令： 你来扮演处理器，当你遇到一个分支，你不知道它要走哪条路，该怎么办？你可以停止执行并等待直到之前的指令执行完。然后继续执行正确路径的指令。 有没有更好的方法喃？可以猜测哪个分支将要被执行！
如果每次都能猜对，整个执行过程就不会停止。 如果经常猜错，就需要在停止、回退、重新执行上花费非常多的时间。 这就是分支预测。不得不承认这不是一个最好的比喻因为火车可以仅仅使用一个标志表示其前进的方向。但是对于计算机，直到最后时刻，处理器是不知道哪条分支被执行。 想想可以使用什么预测策略使得火车回退的次数最少？哈哈，可以利用历史数据！如果火车100次有99次都是向左，那么下次预测结果仍向左。如果过去数据是交替的，那么预测结果也是交替的。如果它每3次都换一个方向，那么预测也采用相同的方法。 简而言之，你需要尝试寻找出一个规则(模式)然后按照它进行预测就可以了。分支预测基本上就是这样工作的。 关于分支预测更多详细的内容可参阅：维基百科 从上面可以得到启发，这个问题的“罪魁祸首”就是 if 语句
注意到数据是在0到255均匀分布的。当排好序后，小于等于128的前半部分是不会执行if语句的，大于128的后半部分都会进入if语句。 这是非常有好的分支预测因为分支会连续多次执行相同的分支。即使是一个简单的饱和计数器也会预测正确除去当变换方向后的少数几个。 快速可视化
然而，如果数据是完全随机的，分支预测则毫无用处因为它不能预测随机数据。这种情况下可能会有50%的错误预测。
那这种情况下该怎么做呢？ 如果编译器不能将分支优化为有条件的移动，这时候可以尝试一些 Hacks ，如果能够可以牺牲可读性的表现。 将下面代码
替换为：
用一些按位操作取代分支判断，这样就去除了分支。（注意：这个 hacks 并不是和if语句严格相等，但是在我们这个例子里，对输入数组data的所有值都是正确的） Benchmarks: Core i7 920 @ 3.5 GHz
Java – Netbeans 7.1.1 JDK 7 – x64
观察可得：
一般的经验法则是避免数据依赖分支在一些特殊的循环中。 64位机器下，GCC 4.6.1附带选项-O3或者-ftree-vectorize可以产生一个条件移动。因此对于有序和乱序数据都是一样快。 VC++2010不能够产生条件移动对于这样的分支。 英特尔编译器11同样可以做一些神奇的事。它通过互换两个循环，从而提升了不可预测的分支外循环。因此，它不但能够避免误预测，而且速度上可以达到VC++和GCC的两个快。换句话说，ICC利用了测试回路打破了benchmark。 如果用英特尔编译器执行没有分支的代码，它仅仅出右向量化(out-right vectorizes it)，并且和带分支同样快。 通过上面说明，即使比较成熟的现代编译器在优化代码的上可以有很大的不同。 原文链接： stackoverflow 翻译： 伯乐在线 - Jerry |
