为什么处理已排序的数组比处理未排序的数组要快？
为什么处理已排序的数组比处理未排序的数组要快？
这里有一段C++代码，展示了一些非常奇特的行为。
由于某种原因，在定时区域之前对数据进行排序，竟然使得主循环快了近6倍：
#include
#include
#include
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)
{
for (unsigned c = 0; c < arraySize; ++c) { // Primary loop. if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '
';
std::cout << "sum = " << sum << '
';
}
- 如果没有
std::sort(data, data + arraySize);，那么代码运行时间为11.54秒。 - 使用排序后的数据，代码运行时间为1.93秒。
（排序本身需要更多的时间，比这个数组的一次遍历还要长，所以如果我们需要对一个未知数组进行计算，实际上不值得这样做。）
起初，我以为这可能只是一种语言或编译器的异常，所以我尝试了Java：
import java.util.Arrays;
import java.util.Random;
public class Main
{
public static void main(String[] args)
{
// Generate data
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
data[c] = rnd.nextInt() % 256;
// !!! With this, the next loop runs faster
Arrays.sort(data);
// Test
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
for (int c = 0; c < arraySize; ++c) { // Primary loop. if (data[c] >= 128)
sum += data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}
得到了类似但不如此极端的结果。
我的第一个想法是排序将数据带入了缓存，但这是愚蠢的，因为数组刚刚生成。
- 到底发生了什么？
- 为什么处理排序后的数组比处理未排序的数组更快？
代码正在求一些独立的项的和，因此顺序不应该有任何影响。
相关/后续问答，关于使用不同/更新的编译器和选项出现相同效果的问题：
你是分支预测失败的受害者。
什么是分支预测？
考虑一个铁路交叉口：
图片由Mecanismo通过Wikimedia Commons发布。在CC-By-SA 3.0许可下使用。
现在为了论证，假设这是在 19 世纪 - 在远距离或无线电通信之前。
你是一个盲目的交叉口操作员，听到火车的声音，却不知道它应该朝哪个方向行驶。你停下火车询问司机他们想要走哪个方向，然后再设置转换器。
火车很重，惯性很大，因此启动和减速需要很长时间。
有没有更好的方法？你可以猜测火车会走哪个方向！
- 如果你猜对了，火车就会继续前进。
- 如果你猜错了，司机会停下车，倒车并责骂你要翻转开关。然后火车可以重新走另一条路。
如果你每次都猜对，火车就永远不必停下。
如果你猜错太多，火车将花费大量时间停下、倒车和重新启动。
考虑一个if语句：在处理器层面上，它是一个分支指令：
你是一个处理器，看到一个分支指令。你不知道它会走哪条路。你该怎么办？你停止执行，等待前面的指令完成。然后你沿着正确的路径继续执行。
现代处理器非常复杂，有很长的流水线。这意味着它们需要很长时间才能“热身”和“减速”。
有没有更好的方法？你可以猜测分支指令会走哪个方向！
- 如果你猜对了，你就继续执行。
- 如果你猜错了，你需要清空流水线并回到分支指令。然后你可以重新沿着另一条路径开始执行。
如果你每次都猜对，执行就永远不必停止。
如果你猜错太多，你会花费大量时间停滞、回滚和重新开始执行。
这就是分支预测。我承认这不是最好的类比，因为火车可以用旗子来表示方向。但是在计算机中，处理器在最后一刻之前不知道分支会走向哪个方向。
如果要最小化火车必须返回并走另一条路径的次数，你会如何进行战略猜测？你会查看过去的历史记录！如果火车99%的时间都往左边走，那么你就猜左边。如果火车交替行驶，那么你就交替猜测。如果火车每三次走一次特定的方向，那么你就猜同样的方向......
换句话说，你尝试识别模式并遵循它。 这或多或少就是分支预测的工作原理。
大多数应用程序的分支都表现良好。因此，现代分支预测器通常可以实现>90%的命中率。但是，当面对没有可识别模式的不可预测的分支时，分支预测器几乎毫无用处。
进一步阅读：维基百科上的“分支预测器”文章。
正如上面所暗示的，罪魁祸首就是这个if语句：
if (data[c] >= 128)
sum += data[c];
请注意，数据在0到255之间均匀分布。当数据排序后，大约前一半的迭代不会进入if语句。之后，它们将全部进入if语句。
这对分支预测器非常友好，因为分支连续地按相同方向多次进行。即使是简单的饱和计数器也可以正确地预测分支，除了在它切换方向后的几次迭代。
快速可视化：
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)
然而，当数据完全随机时，分支预测器变得无用，因为它无法预测随机数据。因此，可能会出现约50%的错误预测（不比随机猜测更好）。
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T ...
= TTNTTTTNTNNTTT ... (completely random - impossible to predict)
可以做些什么？
如果编译器无法将分支优化为条件移动，您可以尝试一些技巧，如果您愿意为性能而牺牲可读性。
替换：
if (data[c] >= 128)
sum += data[c];
用：
int t = (data[c] - 128) >> 31; sum += ~t & data[c];
这将消除分支并将其替换为一些位运算。
（请注意，这个技巧与原始 if 语句并不完全等效。但在这种情况下，它对于 data[] 的所有输入值都是有效的。）
基准测试：Core i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 Release
| 场景 | 时间（秒） |
|---|---|
| 分支 - 随机数据 | 11.777 |
| 分支 - 排序后的数据 | 2.352 |
| 无分支 - 随机数据 | 2.564 |
| 无分支 - 排序后的数据 | 2.587 |
Java - NetBeans 7.1.1 JDK 7 - x64
| 场景 | 时间（秒） |
|---|---|
| 有分支 - 随机数据 | 10.93293813 |
| 有分支 - 排序数据 | 5.643797077 |
| 无分支 - 随机数据 | 3.113581453 |
| 无分支 - 排序数据 | 3.186068823 |
观察结果:
- 有分支：排序数据和未排序数据之间存在巨大差异。
- 使用hack：排序数据和未排序数据之间没有差异。
- 在C++中，当数据排序时，使用hack比使用分支略慢。
一个经验法则是在关键循环中避免依赖于数据的分支（如本例中所示）。
更新：
-
使用 GCC 4.6.1 并启用
-O3或-ftree-vectorize选项，可以生成一个条件移动指令，因此排序数据和未排序数据没有差别，都非常快。（或者比较快：对于已排序的情况，
cmov可能会比较慢，特别是如果 GCC 将其放在关键路径上而不是只有add，特别是在 Broadwell 之前的 Intel 处理器上，cmov的延迟为 2 个时钟周期：gcc optimization flag -O3 makes code slower than -O2） -
VC++ 2010 甚至在启用
/Ox选项的情况下也无法为这个分支生成条件移动指令。 -
英特尔 C++ 编译器 (ICC) 11 实现了奇妙的优化。它交换了两个循环的顺序，从而将不可预测的分支移动到了外层循环。不仅对错误预测免疫，而且比 VC++ 和 GCC 生成的代码快两倍！换句话说，ICC 利用了测试循环来击败基准测试。
更新:
-
使用 GCC 4.6.1 的 x64 架构并加上
-O3或-ftree-vectorize选项可以生成条件移动指令，所以排序和未排序的数据之间没有任何区别 - 两者都很快。(或者有些快：对于已排序的情况，
cmov可能会慢一些，尤其是在 Intel 的 Broadwell 之前，cmov的延迟为 2 个时钟周期，如果 GCC 将其放在关键路径上而不仅仅是add，可能会更慢: gcc optimization flag -O3 makes code slower than -O2) -
即使使用
/Ox选项，VC++ 2010 也无法为此分支生成条件移动指令。 -
Intel C++ 编译器（ICC）11 做了一些神奇的事情。它会 交换两个循环，将不可预测的分支移到外部循环。它不仅免疫于误判，而且比 VC++ 和 GCC 生成的代码快两倍！换句话说，ICC 利用了测试循环来击败基准测试...
-
如果你给 Intel 编译器无分支的代码，它会直接对其进行向量化... 并且和有分支代码一样快（通过循环交换）。
这说明即使是成熟的现代编译器，在优化代码方面也存在很大差异...