为什么处理排过序的数组比处理未排过序的数组更快？
这是一段看似非常特殊的 C++ 代码。为啥把数据排序后代码快了近六倍？
#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;
}- 不排序
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)
{
// Primary loop
for (int c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}结果和 C++ 版本类似，只是快慢差距不那么悬殊。
一开始我以为是因为排序导致数据被缓存，但后来我意识到这是不对的，因为数组是刚刚生成的。
- 那到底是怎么回事？
- 为什么处理排过序的数组比处理未排过序的数组更快？
- 代码总结了一些独立的术语，顺序无关紧要。（译注：没看懂）
答案
你是分支预测失败的受害者。
什么是分支预测？
这是一个铁路岔口：
图片来自 Mecanismo，来自 Wikimedia Commons。在CC-By-SA 3.0许可下使用。
为了讨论背景，我们假设这是在 19 世纪 - 在无线通信发明之前。
你是个搬岔工，听到火车即将到来。你不知道这趟车应该走哪条路，所以你停下火车去询问司机他们想要的方向。然后正确地进行搬岔。
火车很重，惯性大。所以他们启动和停下需要较长时间。
有没有更好的办法？我想那就是由你来猜火车往哪个方向走并搬岔！
- 如果你猜对了，那就继续吧。
- 如果你猜错了，司机会停下来倒车，然后向你大喊大叫，让你翻转开关，然后它从另一条路走。
如果你每次都能猜对 ，火车就永远不会停下来。
如果您经常猜错
，火车将花费大量时间停止，后退和重启。
考虑一个 if 语句：在处理器级别，它是一条分支指令：
假设你是处理器，你看到了一个分支。你不知道它会走哪条路径。这是要怎么做呢？你会暂停执行并等待前面的指令完成。然后继续沿着正确的路径前进。
现代处理器很复杂，管道很长。所以他们 “热身” 和 “慢下来” 需要较长时间。
有没有更好的办法？那就是你来猜分支的方向！
- 如果你猜对了，你继续执行。
- 如果你猜错了，则需要刷新管道并回滚到分支点。然后你可以重新启动另一条路径。
如果你每次都能猜对，执行就可以永远不会停止。
如果你经常猜错 ，你会花很多时间停止，回滚和重启。
这就是分支预测。我承认这不是最好的类比，因为火车可以用旗帜向方向发出信号。但是在计算机中，处理器直到最后一刻才知道分支将朝哪个方向发展。
要怎样猜测才能尽量减少回滚重启次数呢？可以看看过去的历史！如果火车 99% 都往左开，那这次也一样猜左边。如果历史上是交替着开，那么这次也按交替来猜。如果它每 3 次走一条路，你就猜相同......
换句话说，你可以尝试识别模式并按照这个模式的规律来猜。这基本就是分支预测器的工作方式。
大多数应用程序具有表现良好的分支。因此，现代分支预测器通常会达到 >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, 133, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completely random - hard to predict)那可以做些什么呢？
如果编译器无法将分支优化为条件移动，并且如果你愿意牺牲可读性换取更好的性能，则可以尝试一些优化手法。
替换：
if (data[c] >= 128)
sum += data[c];为：
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];这个优化通过位操作来消除了分支。
（注意，这个优化并不完全等同于原始的 if 语句。但在这种情况下，它对data[]所有输入值都有效。）
基准测试：酷睿 i7 920 @ 3.5 GHz
C ++ - Visual Studio 2010 - x64 发行版
// Branch - Random
seconds = 11.777
// Branch - Sorted
seconds = 2.352
// Branchless - Random
seconds = 2.564
// Branchless - Sorted
seconds = 2.587Java - Netbeans 7.1.1 JDK 7 - x64
// Branch - Random
seconds = 10.93293813
// Branch - Sorted
seconds = 5.643797077
// Branchless - Random
seconds = 3.113581453
// Branchless - Sorted
seconds = 3.186068823观察：
- 使用分支：已排序和未排序的数据之间存在巨大差异。
- 通过优化：排序和未排序数据之间没有区别。
- 在使用 C ++ 的情况下，当数据被排序时，优化版实际上比分版还要更慢一点。
一般的经验法则是避免在关键循环中依赖数据进行分支。（例如本示例）
更新：
-
在 x64 上使用
-O3或-ftree-vectorizeGCC 4.6.1 能够生成条件移动。因此，排序和未排序数据之间没有区别 - 两者都很快。 -
即使在
/Ox下，VC ++ 2010 也无法为此分支生成条件移动。 -
英特尔编译器 11 （Intel Compiler 11）做了一些神奇的优化。它会进行循环交换 ，从而将不可预测的分支提升到外循环。因此，它不仅能够免受错误预测的影响，而且速度也是 VC++ 和 GCC 速度的两倍！换句话说，ICC 利用测试循环来击败基准......
-
如果你给英特尔编译器提供无分支代码，那么它将向右矢量化…… 并且与分支一样快（通过循环交换）。
这说明即使是成熟的现代编译器，在优化代码的能力方面也会有很大差异……