为什么排好序的数据在遍历时会更快？（来源*）
参看如下C/C++的代码：
|
1
2
3
4
5
6
7
|
for
(unsigned i = 0; i < 100000; ++i) {
// primary loop
for
(unsigned j = 0; j < arraySize; ++j) {
if
(data[j] >= 128)
sum += data[j];
}
}
|
如果你的data数组是排好序的，那么性能是1.93s，如果没有排序，性能为11.54秒。差5倍多。无论是C/C++/Java，或是别的什么语言都基本上一样。
这个问题的原因是—— branch prediction （分支预判）伟大的*给了一个非常不错的解释。
考虑我们一个铁路分叉，当我们的列车来的时候， 扳道员知道分个分叉通往哪，但不知道这个列车要去哪儿，司机知道要去哪，但是不知道走哪条分叉。所以，我们需要让列车停下来，然后司机和扳道员沟通一下。这样的性能太差了。
所以，我们可以优化一下，那就是猜，我们至少有50%的概率猜对，如果猜对了，火车行驶性能巨高，猜错了，就得让火车退回来。如果我猜对的概率高，那么，我们的性能就会高，否则老是猜错了，性能就很差。
我们的if-else 就像这个铁路分叉一样，下面红箭头所指的就是搬道器。
那么，我们的搬道器是怎么预判的呢？就是使用过去的历史数据，如果历史数据有90%以上的走左边，那么就走左边。所以，我们排好序的数据就更容易猜得对。
|
1
2
3
4
5
6
7
|
T = 走分支（条件表达式为
true
）
N = 不走分支(条件表达式为
false
)
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
|
|
1
2
3
4
|
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completely random - hard to predict)
|
从上面我们可以看到，排好序的数据更容易预测分支。
对此，那我们怎么办？我们需要在这种循环中除去if-else语句。比如：
我们把条件语句：
|
1
2
|
if
(data[j] >= 128)
sum += data[j];
|
变成：
|
1
2
|
int
t = (data[j] - 128) >> 31;
sum += ~t & data[j];
|
“没有分叉”的性能基本上和“排好序有分支”一个样，无论是C/C++，还是Java。
注：在GCC下，如果你使用
转自酷壳-O3or-ftree-vectorize编译参数，GCC会帮你优化分叉语句为无分叉语句。VC++2010没有这个功能。