在StackOverflow上有这么一个问题 Why is processing a sorted array faster than an unsorted array? 。例子中，对一个数组进行条件求和，在排序前和排序后，性能有很大的差别。原始的例子是C++和Java的，这里将其换成了C# ：static void Main(string[] args){// Generate dataint arraySize;int[] data;Random rnd;arraySize = 32768;data = new int[arraySize];rnd = new Random(0);for (int c = 0; c < arraySize; ++c)data[c] = rnd.Next(256);// Testlong sum = 0;CodeTimer.Time("unsorted array", 100000, () =>{for (int c = 0; c < arraySize; ++c){if (data[c] >= 128)sum += data[c];}});Array.Sort(data);sum = 0;CodeTimer.Time("sorted array", 100000, () =>{for (int c = 0; c < arraySize; ++c){if (data[c] >= 128)sum += data[c];}});Console.ReadKey();}
代码中首先初始化了一个 32768大小的int型数组，给这个数组的每个元素随机赋予0-256之间的值，然后对该数组中大于128部分的数据进行求和，并将这个过程累加100000次。然后分别测量数组在排序前和排序后的 耗时。 这里使用了老赵的CodeTimer工具来，本人机器Xeon E3-1230v3@3.30GHz，在debug条件下，结果如下：
在release条件下，结果如下：
然后作者提出了问题，为什么仅仅对数据进行了排序，处理速度就快了将近一倍还要多呢？
排名第一的回答，解释到是由于分支预测错误导致的性能惩罚，所以会产生性能的差别。要解释分支预测的惩罚，首先来看什么是分支预测，以及为什么预测错误会导致惩罚。
二 分支预测
什么是分支预测? 直接说计算机概念或许不太好理解，答案以一个铁路分支路口的例子来说明了什么是分支预测。
考虑下面的铁轨分支:
假设在还没有远距离信号通讯的时代。你是一个铁路分支路口的操作人员，当听到火车要来了，你根本不知道即将到来的这辆火车要开往哪个方向。于是，你让这辆或者停下来，问列车长这辆车要开往那个方向，然后将铁轨扳到对应的方向上。
火车是一个很笨重的东西，因此具有很大的惯性，需要花很多时间启动和停止。
那么，有没有更好的办法呢？那就是，，由你来猜这辆火车要往那个方向走！
如果猜对了，火车可以直接开往要去的方向如果猜错了，火车要停下来，然后倒车，然后将车轨扳到正确的方向，然后火车重新开往正确的方向。
如果你的猜测总是正确的，那么火车就不用停下来了
如果你经常猜错，那么火车就要花很多的时间停下来，后退，然后重新开动。
现在，考虑一个if语句。if 语句编译为一个分支判断指令：
如果你是处理器，你看到了这个分支，你事先完全没没有办法知道将从那个分支走。那么怎么办呢？你可以让指令暂停，等待直到之前的指令执行完成，然后比较结果，然后往正确的那个方向走。
现代处理器很复杂，并且有很长的流水线，因此如果是这样的话，就需要很多时间来预热启动和停止。
那么，有没有更好一点儿的办法呢？你来猜这个指令将往那个方向走:
如果猜对了，语句可以继续执行如果猜错了，处理器会放弃整个流水线，然后回退到分支地方，继续朝正确的分支执行。
如果每次都猜对，那么处理器不需要暂停可以一直执行
如果经常猜错，那么处理器就要话很多时间来暂停，回退，然后重新启动。
这就是分支预测，虽然用火车铁轨的方式来解释可能不太恰当，因为通过旗帜或者信号可以提前通知要往那个方向。 但是对于计算机来说，处理器提前是不知道将要执行那个分支的，只有等到执行到分支判断的那一刻，值求出来之后才可以确定。
因此如何采用一种策略来减少出错的次数，减少类似火车停车，倒车，再启动的问题呢？很自然的，可以根据以往的情形来推断！如果这个火车以前有99%的情况走左边，那么就可以在火车来之前猜测他走左边。如果行为发生变化，可以做相应的调整。如果发现每3次调整一次方向，那么总结出这个规律后就可以做出适当的调整。
换句话说，我们需要总结出一些模式，然后遵循。这或多或少就是分支预测器的工作。
大多数的应用都有行为良好的分支。因此现代的分支预测器能到达到90%以上的预测正确率。但是面对一些不可预见的分支和不可知的模式，分支预测器就没有多大用了。
通过上面的描述，出现性能差别的问题关键在于这个if语句：
if (data[c] >= 128)sum += data[c];
注意到data这个数组里面的值是平均分布于0-255之间的。当数据排好序之后，前半部分的数据都会小于128，所以不会进到if语句里面，后半部分的值都大于128，所以会进到循环语句。
一个人身边的位置只有这么多，
