说明：本文基于Whyisitfastertoprocessasortedarraythananunsortedarray?在stackoverflow上，翻译了问题和高票答案，并添加了很多补充说明，方便读者理解。背景让我们先看一下c++代码。我们随机填充一个模数为256的固定大小的大数组，然后对数组中的一半元素求和：#include#include#includeintmain(){//随机生成整数并用分区函数填充它们以避免不均匀的分桶constunsignedarraySize=32768;intdata[arraySize];for(unsignedc=0;c=128)sum+=data[c];}}doubleelapsedTime=static_cast(clock()-start)/CLOCKS_PER_SEC;std::cout<=128)sum+=data[c];}}System.out.println((System.nanoTime()-start)/1000000000.0);System.out.println("sum="+sum);}}在intellijidea中运行的结果：#1。先排序再计算5.549553sum=155184200000#2。不排序直接结算15.527867sum=155184200000也有三倍左右的差距。而且Java版的速度几乎是C++版的两倍？这应该是编译时使用默认选项，gcc优化不够的原因。我们稍后会调查这个问题。问题的提出上面的代码在数组填充的时候加入了分区函数，充分保证了填充值的随机性，并且按照元素的一半计算和，所以不存在特例。而且计算完全不涉及数据的顺序，即数组是否有序理论上对计算没有影响。在这样的前提下，为什么有序数组的运行速度比无序数组快3倍以上呢？分析想象一个铁路岔路口。为了论证这个问题，让我们回到19世纪，那个远距离无线通讯还没有普及的时代。你是铁路道口的扳道工。当您听到火车驶近时，您无法猜测它应该开往哪个方向。于是你停下火车，上去问火车司机应该往哪个方向走，这样你才能正确地换轨。要知道，火车是非常庞大的，在高速行驶的时候，惯性很大。为了完成上述停车-查询-切轨这一系列动作，列车需要花费大量的时间进行减速、停车、再启动。由于上述传递非常耗时，有没有更好的方法呢？当然有！当火车要来的时候，你可以猜出火车应该开往哪个方向。如果它猜对了，它会直接通过并继续前进。如果你猜错了，车头会停下来，倒车，你把轨道转向相反的方向，火车会重新启动，驶过道口。如果你运气不好，每次都猜错了，火车会花很多时间停下来——倒车——再出发。如果你很幸运并且每次都猜对了怎么办？火车永远不会停下来，一直开下去！上面的类比可以应用于处理器级别的分支跳转指令：原程序：if(data[c]>=128)sum+=data[c];汇编代码：cmpedx,128jlSHORT$LN3@mainaddrbx,rdx$LN3@main：让我们回到文章开头的问题。现在假设你是一个处理器。当你看到上面的树枝，当你拿不定主意怎么往下走的时候，怎么办？只能暂停操作，等待前面的指令执行完毕。然后你就可以沿着正确的路径继续下去了。请注意，现代编译器非常复杂并且在运行时有很长的管道，减速和热启动可能会花费大量时间。那么，有没有什么好的方法可以节省这些状态切换的时间呢？你可以猜出下一步的分支！如果猜错了，处理器会flushpipelines，回滚到之前的分支，然后重新热启动，选择另一条路径。如果猜测正确，处理器不需要暂停，继续执行。如果每次都猜错，处理器会在停止-回滚-热启动的循环中耗费大量时间。如果运气好，它每次都猜对了，处理器将永远不会停止并运行完成。以上过程就是分支预测（branchprediction）。虽然在实际的过轨切换中，可以通过一个小标志作为判断列车方向的信号，但是处理器无法像列车一样预测支路的方向——除非最后一条指令被执行。那么处理器应该采用什么样的策略来使用最少的次数来尝试猜测指令分支的下一步呢？答案是分析历史运行记录：如果火车过去90%的时间都在左轨道上，这个轨道开关，可以猜出方向是左，反之就是右。如果它已经朝某个方向行驶了3次，那么你也可以猜测火车会继续朝那个方向行驶……换句话说，你正在尝试穿越历史，找出一个隐含的模式并尝试它会继续用于后续的铁路转换决策。这或多或少类似于处理器的分支预测原理。大多数应用程序都有行为良好的分支，因此现代分支预测器的命中率通常超过90%。但是当面对不可预测的分支并且没有确定适用的模式时，分支预测器是无用的。关于分支预测周期，请参考维基百科上的“Branchpredictor”一文。文章开头的罪魁祸首是if逻辑：if(data[c]>=128)sum+=data[c];注意data数组中的元素是按照0-255的取值均匀存储的（类似于uniformbucketing）。数组数据排序时，前半部分元素的迭代不会进入if语句，超过一半的元素迭代都会进入if语句。这种继续向同一方向切换的迭代对于分支预测器来说非常重要。友情提示，前半部分元素迭代完成后，后续迭代分支预测器对分支方向切换的预测全部正确。简单分析一下：有序数组的分支预测过程：T=branchhitN=branchnothitdata[]=0,1,2,3,4,...126,127,128,129,130??,...250,251,252,...branch=NNNNN...NNTTT...TTT...=NNNNNNNNNNNNNN...NNNNNNNTTTTTTTTT...TTTTTTTTTT（非常容易预测）无序数组的分支预测过程：data[]=226,185,125,158,198,144,217,79,202,118,14,150,177,182,133,...branch=T,T,N,T,T,T,T,T,N,T,N,N,T,T,T,N...=TTNTTTTTNTNNTTTN...（完全随机-不可预测）在此示例中，由于数据数组元素填充的特殊性，确定分支预测器在unsorted数组的迭代过程中会有50%的误命中率，因此执行整个sum操作会花费更多的时间。优化使用位操作来取消分支跳转。基础知识：|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作为掩码和任意数求和，如果值不变，分支判断可以优化为：intt=(data[c]-128)>>31;#statement1sum+=~t&data[c];#statement2analysis:data[c]<128，则语句1的值为：0xffff=-1，语句2等号右边的值为：0&data[c]==0；data[c]>=128，则语句1的值：0，语句2等号右边的值：~0&data[c]==-1&data[c]==0xffff&数据[c]==数据[c];所以上面位运算实现的求和逻辑完全等同于if语句，更多的位运算hack操作可以参考bithacks。如果想避免移位操作，可以使用如下方法：intt=-((data[c]>=128));#generatethemasksum+=~t&data[c];#bitwiseAND结论使用分支预测：排序是否严重影响performance使用bithack：排序是否对性能没有太大影响这个例子给我们的启示是：在大规模的循环逻辑中，尽量避免依赖数据的分支。补充知识流水线先简单介绍一下CPU的指令流水线（instructionpipeline），以下简称流水线。流水线假设程序运行时有一系列指令要执行，将程序分成若干个阶段，按照一定顺序并行处理，可以加快指令的传递速度。大多数流水线由时钟频率控制。在数字电路中，时钟控制着逻辑电路和触发器。当被时钟频率触发时，触发器得到一个新值，逻辑门需要一段时间来解析新值，触发器在被下一个时钟频率触发时得到新值，以此类推.通过将逻辑门分散成许多小块，然后将这些小块组用触发器连接起来，可以减少逻辑门输出正确值的时间延迟，从而减少指令执行所需的周期。这对应于管道中的每个阶段。一般流水线有四个执行阶段（execuatestage）：读指令（Fetch）->指令译码（Decode）->运行指令（Execute）->写回操作结果（Write-back）。Branchpredictor分支预测寄存器是一种数字电路，它在执行分支指令之前猜测将执行哪个分支，可以显着提高流水线的性能。条件分支通常有两个后续执行分支。当没有token时，跳过下一条JMP指令继续执行。token时，执行JMP指令，跳转到另一块程序存储器执行。为了说明这个问题，我们首先考虑以下问题。没有分支预测器会发生什么？不添加分支预测器，处理器将等待分支指令通过流水线的执行阶段，然后再将下一条指令发送到流水线的获取阶段。这会导致流水线停滞（stalled）或流水线冒泡（bubbling）或流水线打嗝（hiccup），即在流水线中产生一个没有作用的气泡，如下图所示：图中的一个气泡是在编号为3的恒定频率下产生的，指令执行被延迟。Streamhiccup现象在早期的RISC架构处理器中很常见。具有分支预测周期的流水线我们来看看分支预测器在条件分支跳转中的应用。条件分支通常有两个后续执行分支。当没有token时，跳过下一条JMP指令继续执行。token时，执行JMP指令，跳转到另一块程序存储器执行。添加分支预测器后，为了避免流水线停顿（streamstalled），它会猜测两个分支中的哪一个最有可能被执行，然后推测性地执行。如果猜测错误，管道中所有推测执行的中间结果将被丢弃，重新获得正确的分支。执行路线上的指令。可见，错误的预测会造成程序执行的延迟。从上面可以看出，流水线执行主要涉及Fetch、Decode、Execute、Write-back几个阶段，分支预测失败会浪费Write-back之前的流水线阶段数。现代CPU的流水线级数很长，分支预测失败可能会损失大约20个时钟周期，所以对于复杂的流水线，一个好的分支预测器非常重要。公共分支预测器静态分支预测器静态分支预测器有两个解码周期，一个用于分支评估，一个用于解码。也就是说，分支指令执行前一共经历了3个时钟周期。详情见图：双峰预测器，也称为饱和计数器，是一个四态状态机。四种状态分别对应两个选项：token，nottoken，每个选项都有两个状态来区分强弱：strongly，weakly。它们强烈不被接受，弱不被接受，弱被接受，强烈被接受。状态机的工作原理图如下：图中左边两个状态不接受（nottoken），右边两个状态采用（token）。从nottoken到token有两种转换状态。从红色翻转到绿色需要两个连续的分支选择。在技??术实现上，可以用两个二进制数字来表示，00、01、10、11分别对应强不令牌、弱不令牌、弱令牌、强令牌。判断两个分支预测规则是否发生变化的一种简单方法是判断二进制状态的高位是否翻转。高位由0变为1，强态翻转，则下一条分支指令的预测由nottoken变为token，反之亦然。根据评估，双峰预测器的正确率可达93.5%。预测通常在分支指令被解码之前发挥作用。其他常见的分支预测器如两阶段自适应预测器、局部/全局分支预测器、融合分支预测器、同意预测周期、神经分支预测器等。
