首先有这样一段简单的程序：
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster
std::sort(data, data + arraySize);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
原文说运行时间1.93s，我试了一下
可能是CPU差距有点大吧。。
然后去掉排序那一句：
原文是11.54s
原文作者用JAVA也试了，但是时间差距没C++这么大。
为什么处理排过序的数组更快呢？
我要开始搬运了，纯属意译，不准确的请指出：）
如果有一个铁路分叉口，你在那里给铁路指向，但是你不知道火车要去的地方在哪个方向，你只能猜啊，如果你猜对了火车就顺利跑过去了，但是如果你猜错了，你要知道，火车质量那么大，启动和停下来都很耗时间！
So they take forever to start up and slow down(哈哈，forever)
再来看计算机：
if (data[c] >= 128)
sum += data[c];
计算机运行到这一步怎么办啊，它哪里知道是不是该执行这一句啊！它得停下来执行这个判断语句了才知道。判断完成了你才能继续之前的计算。
然而现代的计算机处理器都使用的是流水线技术，（把复杂的运算分成一步一步，增加处理效率）
Modern processors are complicated and have long pipelines. So they take forever to "warm up" and "slow down".
和火车一样你让快速运行并且复杂的流水线停下来是非常耗时间的事情。
（这里我猜测一下是不是会在判断的时候预执行一条分支？）
所以电脑也靠猜，猜对了就很流畅，但是猜错了也是非常耗时间的。
所以就是怎么样猜的更准了，电脑会试图找到一条规律。
Most applications have well-behaved branches. So modern branch predictors will typically achieve >90% hit rates. But when faced with unpredictable branches with no recognizable patterns, branch predictors are virtually useless.
也就是说电脑会根据之前的结果，选择概率更大的，如果之前有很多都是往右的，电脑会猜测下一次也往右。
wiki上Branch predictor的解释
如果是排过序的，那么规律很明显，电脑判断成功的几率就高很多
未经排序的数据很乱，判断成功的几率很低：
So what can be done?
If the compiler isn't able to optimize the branch into a conditional move, you can try some hacks if you are willing to sacrifice readability for performance.
Replace:
if (data[c] >= 128) sum += data[c];
with:
int t = (data[c] - 128) >> 31; sum += ~t & data[c];
This eliminates the branch and replaces it with some bitwise operations.
(Note that this hack is not strictly equivalent to the original if-statement. But in this case, it's valid for all the input values of data[]
.)
最高赞回答者这样替换了一下代码，这样看起来多了一些运算。
