问题
Stack_overflow 上有这么一个帖子：为什么排序后会快很多，说是下面这段代码比较诡异，引发了比较多的回复，一起来看看。
#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;
std::sort(data, data + arraySize); //排序这行不注释掉下面的 for 循环会快得多
// 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;
}- 如果把 std::sort(data, data + arraySize);注释掉，下面那段 for 循环所花费的时间是 11.54 秒。
- 如果不注释掉，即排序后下面那段所用的时间是 1.93 秒。
相差比较大。那个 for 循环总是要执行完的，为什么排序后会快不少？
分支预测
下面的获得票数最多的回复质量非常高，很生动细致地说明了 cpu 的分支预测技术。
Black Cube Theme
看上面这情形，如果在没有通讯设备的年代，如果你是这个火车枢纽的操作人员，
是不是要让火车驾驶员把车停下来，然后告诉你他需要往哪个方向行驶，等你完成转向操作的时候再继续行驶火车呢。也许有一些更好的办法，你可以猜测火车要往哪边行驶。
- 如果你猜对了，那么节省了不少时间。
- 如果猜错了，火车停下来，等你撤销刚才的操作，再往前走，这会比较耗费时间。
同样在执行指令的时候，cpu 也能做这样类似的工作。现代 cpu 都采用 指令流水线技术，即处理器会预取下面要执行的一些指令，如果下面的指令正是需要被执行的那就节省了时间，如果在概率上大部分能猜对下面要运行的指令，那就提高了 cpu 的运行效率。更详细的图文介绍可以参考wiki。简单的说明就是 cpu 会根据前面所执行的指令的历史，归纳出相应的模式，把预测的指令预取进来，然后继续沿着预测的指令执行。如果发现预测错误，则倒过来重新初始化预测表、刷新指令管道然后继续执行。所以看上面的例子：
T = branch taken
N = branch not taken
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)后面作者又加了一条 hack，把这段代码重新改写一下：
if (data[c] >= 128) ====> int t = (data[c] - 128) >> 31;
sum += data[c]; ====> sum += ~t & data[c];
那么前面是否排序就对这段代码效率没有影响了，同样是 2 秒多。这和编译器的优化非常相关，不同的编译器的结果不一样，4.6.1 GCC 加上-O3 或者-ftree-vectorize 编译选项可以对这种情况进行优化，所以排序与否没有关系，而 VC++2010 却不能进行类似优化 (GCC 果然强大)。
一个优化例子
在 Linux kernel 里面会看到类似 likely 和 unlikely 这样的代码，从其名字就很直观的解释了其意义。看其定义为两个宏。
include/linux/compiler.h
#define likely(x) __builtin_expect (!!(x), 1)
#define unlikely(x) __builtin_expect (!!(x), 0)Linux 内核开发者使用这两个宏来通过编译器提示 cpu：某一段代码很可能会执行，应该被预测，而有的情况出现的概率比较小，不必预测。类似这样的代码：
if(likely(some_cond)) { //this is often happen!
/* Do something */
}
if (unlikely(some_cond)) { //this is rare!
/* Do something */
}关于这个方面，在这篇论文What every Programmer should know about Memory里面有更详细的讲述。分支预测在现代 cpu 上如此通用，竟然还有人利用这个来尝试破解 RSA 的，看这个On the Power of Simple Branch Prediction Analysis。
