这是一段非常奇特的C++代码。出于某种奇怪的原因，对数据进行排序奇迹般地使代码运行速度提高了 3 倍。
#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;
// !!! Con esto el siguiente bucle se ejecuta más rápido.
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);，代码将在12.41秒内运行。 - 数据排序后，它在3.82秒内运行。
起初我认为这可能是语言或编译器异常。所以我尝试了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;
// !!! Con esto el siguiente bucle se ejecuta más rápido.
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);
}
}
这给出了类似但不太极端的结果。10.7和6.2秒。
起初我认为这可能与将数据排序到缓存中有关，然后我意识到数据刚刚生成，并且在排序之前应该已经在缓存中。
- 这是怎么回事？
- 为什么有序数组比无序数组快？
- 该代码正在计算独立项的总和。顺序不应该影响，在任何情况下，遍历所有元素并且总是添加相同的元素，给出相同的结果，无论它们是否有序。
这是一个从英文原文翻译的问题，并根据它在我的计算机上给出的结果进行了调整：为什么处理排序数组比处理未排序数组更快？通过GManNickG
您是分支预测器中错误的受害者。
什么是跳跃预测？
考虑一个铁路叉：
假设我们处于 19 世纪——远早于远程或无线电通信。
你是一个叉子的操作员，你听到一列火车接近。你不知道它应该遵循什么路径。所以你停下火车向飞行员询问它的方向。你把针放在正确的方向上。
火车很重，惯性很大，所以要花很长时间才能停下来。
有更好的方法吗？你可以猜到火车的方向！
如果你每次都打，火车就永远不用停下来。
如果您经常失败，火车将花费大量时间停止、返回和重新启动。
考虑一个 if 语句在处理器级别，它是一个条件跳转语句。
你是处理器，你会看到条件跳转。你不知道它会不会跳。去做？停止执行并等待前面的指令完成。然后你继续走正确的道路。
现代处理器复杂且高度分段，需要很长时间才能_开始执行_和_停止执行_。
有没有更好的办法？猜猜会不会跳！
如果你点击 always，执行永远不会中断。
如果您经常崩溃，您会花费大量时间停止、撤消和重新启动。
这是分支预测。我承认这不是最好的类比，因为火车的飞行员可以用三角旗指示方向。但是在计算机中，处理器直到最后一刻才知道跳转是否会执行。
那么使用什么预测策略来最小化火车必须掉头并转向另一条路的次数呢？看着历史！如果火车有99%的时间向左行驶，那么您预测左侧。如果它切换，那么你切换你的预测。如果它向一个方向发展 3 次中的 1 次，你会做出同样的预测......
换句话说，您尝试识别一种模式并遵循它。这或多或少是跳跃预测器的工作方式。
大多数程序都有表现良好的条件跳转。所以现代分支预测器有>%90 hits ，但是当面对不可识别的模式的不可预测的条件分支时，分支预测器实际上是无用的。
深化主题：“Jump Predictor”维基百科文章。
以上在语句中为我们提供了问题出在哪里的线索
if：请注意，数据均匀分布在 0 到 255 之间。当对数据进行排序时，大约前一半的迭代不会进入语句
if。在此之后，他们将始终输入语句if。这对于分支预测器非常有用，因为同一类型的分支总是连续多次生成。
即使是一个简单的饱和计数器也能正确预测跳跃，除了变化后的几次迭代。
快速浏览：
但是，当数据完全随机时，跳跃预测器就没有用了，因为它无法预测随机数据。
可能会有大约50%的预测失败。（这并不比随机预测好）
可以做什么？
如果编译器无法在条件赋值中优化条件分支，那么如果您愿意为了性能而牺牲代码清晰度，则可以使用一些技巧。
替换：
经过：
这将删除条件跳转并用一些按位操作替换它。
（注意，这个技巧并不严格等同于
if原始语句，但在这种情况下，它对 的所有值都有效data[]。）基准测试：Core 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能够生成条件映射。因此，排序数据和未排序数据之间没有区别——两者都很快。即使使用
/Ox.Intel Compiler 11 做了一些神奇的事情。交换两个循环，从而将条件跳转到外部循环。它不仅不受预测失败的影响，而且速度是 VC++ 和 GCC 生成速度的两倍。换句话说，ICC利用测试循环击败了性能测试......
如果您在不跳转的情况下为英特尔编译器提供代码，它会直接对其进行矢量化......并且它与条件跳转（使用循环交换）一样快
这表明即使在现代和成熟的编译器中，它们优化代码的能力也可能存在巨大差异......
这个答案是由Mystical翻译的英文原版