这是一个看起来很奇怪的 C++ 代码示例。出于某种原因，对数据进行排序后，代码的运行速度几乎快了六倍。
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// Заполнение данными
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! С этой строкой следующий цикл работает быстрее
std::sort(data, data + arraySize);
// Проверка
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
// Основной цикл
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)
{
// Заполнение данными
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;
// !!! С этой строкой следующий цикл работает быстрее
Arrays.sort(data);
// Проверка
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Основной цикл
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);
}
}
结果，获得了类似的结果，但差距较小。
我的第一个想法是排序的时候，数据进入缓存，但后来我认为这是愚蠢的，因为刚刚创建了数组。
- 发生了什么？
- 为什么排序的数组比未排序的数组处理得更快？
答案翻译：@Mysticial
您是分支预测器错误的受害者。
什么是分支预测？
考虑一个铁路枢纽：
图片由 Mecanismo 提供，来自维基共享资源。在CC-By-SA 3.0 许可下使用。
现在想象一下，我们回到了 19 世纪，无线电发明之前。
您是铁路枢纽站操作员，您听到火车驶来。你不知道他应该走哪条路。你停下火车，问司机他想去哪里。然后将开关设置到所需位置。
火车很重，惯性很大。因此，启动和停止需要很长时间。
有没有更好的办法？你可以猜出火车将开往哪里！
如果你每次都猜对了，火车就永远不会停。
如果你经常犯错误，火车将失去很多时间来停止、返回和加速。
考虑一个 if 语句：在处理器级别，这是一个分支指令：
你是一个处理器，你看到了分支。您不知道将选择哪个分支。你该怎么办？您停止执行并等待上一条指令完成。然后你沿着正确的路径继续执行。
现代处理器很复杂，流水线很长。因此，“预热”和“停止”需要很长时间。
有没有更好的办法？你可以猜到哪个分支将被执行！
如果你每次都猜对了，执行将永远不会停止。
如果经常出错，停止、回滚和重启会花费很多时间。
这是过渡预测。我承认，这不是最好的比喻，因为火车可以用旗帜发出信号来指示方向。但在计算机中，处理器直到最后一刻才知道将采取哪个方向。
那么在猜测的时候选择哪种策略。尽量减少次数。火车应该什么时候返回并改道？你可以看到历史！如果火车 99% 的时间都在向左行驶，那么猜测就是：向左行驶。如果它们交替出现，那么猜测也会交替出现。如果每三次选择一条路径，则可以假设相同...
换句话说，您正在尝试定义一种行为模式并遵循它。这就是过渡预测器的工作原理。
大多数应用程序都有明确定义的分支。因此，现代分支预测器的正确猜测百分比通常 > 90%。但是当他们遇到具有未定义模式的不可预测的分支时，分支预测器实际上是无用的。
进一步阅读：“跳跃预测器”维基百科文章。
如上所述，问题在于这个 if 语句：
请注意，数据在 0 到 255 之间均匀分布。
当数据排序时，前半部分不会进入 if 语句。然后，在 if 语句中，所有其余部分都将消失。
这对预测器来说非常好，因为连续多次选择相同的分支。
即使是具有饱和度的简单计数器也能正确预测方向，除非在方向改变之后。
快速可视化：
但是当数据是随机的时，预测器就没有用了，因为它不能预测随机数据。
因此，错误预测的概率可能约为 50%。（不比随机猜测好）
那么可以做什么呢？
如果编译器不能优化分支选择，如果您愿意为了性能牺牲可读性，您可以尝试一些 hack。
代替：
在：
这消除了分支并用一些按位运算代替它。
（请注意，此 hack 并不完全等同于原始条件。但在这种情况下，它会为来自 的所有输入值生成正确的结果
data[]。）基准测试：酷睿 i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 版本
Java-Netbeans 7.1.1 JDK 7-x64
观察：
一般规则是避免在关键循环中使用数据相关条件。（如本例所示）
更新 ：
-O3带有或在 x64 上的GCC 4.6.1-ftree-vectorize可以生成 CMOV 指令。在这种情况下，已排序或未排序的数据之间没有区别 - 两种情况都很快。VC++ 2010 不允许生成分支 CMOV，即使在使用
/Ox.英特尔编译器 11 做了一些惊人的事情。它交换两个循环，从而将不可预测的分支推入外循环。所以它不仅不受预测错误的影响，而且生成速度是 VC++ 和 GCC 的两倍！换句话说，ICC 利用测试周期击败了测试......
如果您在没有分支的情况下为英特尔编译器提供代码，它将对其进行矢量化……而且它与分支（带循环）一样快。
这表明即使是成熟的编译器在优化代码的能力方面也可能彼此不同......
这种影响很可能是由于处理器分支预测块的存在而发生的。当数据排序后，分支成
只改变一次（起初条件失败，然后总是失败）并且预测效果更好。在未排序的序列上，更难预测它是否有效
if。如果将if其完全删除，您可以看到存在或不存在sort不会影响计算的持续时间。PS TC 代码似乎是从enSO问题中借来的。因此，要获得更详细的描述，您可以点击链接。正如我已经在评论中指出的那样，我的回答不是翻译。
您正在观察工作中的过渡预测器。这是一个属于处理器一部分的设备，具有流水线架构，可预测是否会在可执行程序中采用条件分支。
对于排序数组，数据
data[c] >= 128对于一个值带改变一次并且对于所有后续值都变为真。它们很容易被处理器预测（现代处理器中的分支预测准确率超过 90%）。使用未排序的数组，您需要为程序的分支速度付出代价。如果没有分支预测，流水线必须等到条件分支指令被执行才能进行下一次提取。分支预测器避免浪费时间试图找出分支。
最有可能的是，在排序时，数组
data进入了处理器缓存。如果我们考虑到数组的小尺寸，那么它必须完全落入 1 个缓存行。