为什么处理排过序的数组比处理未排过序的数组更快？
这是一段看似非常特殊的 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 利用测试循环来击败基准......
-
如果你给英特尔编译器提供无分支代码，那么它将向右矢量化…… 并且与分支一样快（通过循环交换）。
这说明即使是成熟的现代编译器，在优化代码的能力方面也会有很大差异……
分支预测。
对于排序数组，条件data[c] >= 128对于条纹值首先为false ，然后对于所有后续值变为true 。这很容易预测。使用未排序的数组，您需要支付分支成本。
当数据被排序时，性能显着提高的原因是分支预测惩罚被消除，正如Mysticial的答案中精美地解释的那样。
现在，如果我们看一下代码
if (data[c] >= 128)
sum += data[c];我们可以发现这个特殊的if... else...分支的含义是在条件满足时添加一些东西。这种类型的分支可以很容易地转换为条件移动语句，它将被编译成x86系统中的条件移动指令： cmovl 。分支以及因此潜在的分支预测惩罚被移除。
在C ， C++ ，这个语句可以直接编译（没有任何优化）到x86的条件移动指令，是三元运算符... ? ... : ...所以我们将上面的语句重写为等价的语句：
sum += data[c] >=128 ? data[c] : 0;在保持可读性的同时，我们可以检查加速因子。
在 Intel Core i7 -2600K @ 3.4 GHz 和 Visual Studio 2010 发布模式下，基准是（从 Mysticial 复制的格式）：
86
// Branch - Random
seconds = 8.885
// Branch - Sorted
seconds = 1.528
// Branchless - Random
seconds = 3.716
// Branchless - Sorted
seconds = 3.7164 位
// Branch - Random
seconds = 11.302
// Branch - Sorted
seconds = 1.830
// Branchless - Random
seconds = 2.736
// Branchless - Sorted
seconds = 2.737结果在多个测试中是稳健的。当分支结果不可预测时，我们获得了很大的加速，但是当它是可预测的时候我们会受到一点点的影响。实际上，在使用条件移动时，无论数据模式如何，性能都是相同的。
现在让我们通过调查它们生成的x86程序集来更仔细地查看。为简单起见，我们使用max1和max2两个函数。
max1使用条件分支if... else ... ：
int max1(int a, int b) {
if (a > b)
return a;
else
return b;
} max2使用三元运算符... ? ... : ... ：
int max2(int a, int b) {
return a > b ? a : b;
}在 x86-64 机器上， GCC -S生成下面的组件。
:max1
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl -8(%rbp), %eax
jle .L2
movl -4(%rbp), %eax
movl %eax, -12(%rbp)
jmp .L4
.L2:
movl -8(%rbp), %eax
movl %eax, -12(%rbp)
.L4:
movl -12(%rbp), %eax
leave
ret
:max2
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
movl -4(%rbp), %eax
cmpl %eax, -8(%rbp)
cmovge -8(%rbp), %eax
leave
ret由于使用了指令cmovge max2使用的代码要少cmovge 。但真正的好处是max2不涉及分支跳转， jmp ，如果预测结果不正确，则会产生显着的性能损失。
那么为什么有条件的移动表现更好呢？
在典型的x86处理器中，指令的执行分为几个阶段。粗略地说，我们有不同的硬件来处理不同的阶段。因此，我们不必等待一条指令完成开始新指令。这称为流水线 。
在分支情况下，以下指令由前一个指令确定，因此我们不能进行流水线操作。我们必须等待或预测。
在条件移动的情况下，执行条件移动指令被分成几个阶段，但是像Fetch和Decode这样的早期阶段不依赖于前一个指令的结果; 只有后期才需要结果。因此，我们等待一个指令执行时间的一小部分。这就是为什么当预测很容易时，条件移动版本比分支慢。
“ 计算机系统：程序员视角 ” 一书第二版详细解释了这一点。您可以检查第 3.6.6 节有关条件移动指令 ，整个第 4 章用于处理器体系结构 ，第 5.11.2 节用于特殊处理分支预测和错误预测惩罚 。
有时，一些现代编译器可以优化我们的代码以便以更好的性能进行汇编，有时一些编译器不能（有问题的代码使用 Visual Studio 的本机编译器）。在不可预测的情况下了解分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以至于编译器无法自动优化它们时编写具有更好性能的代码。