在这段C++代码中，对数据进行排序（在定时区域之前）可以使主循环的速度提高约6倍。
起初，我以为这可能只是一种语言或编译器的异常，所以我尝试了Java：
与类似但较不极端的结果。
我的第一个想法是排序会将数据放入缓存中，但这是愚蠢的，因为数组刚刚生成。
#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)
{
for (unsigned c = 0; c < arraySize; ++c)
{ // Primary loop.
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '\n';
std::cout << "sum = " << sum << '\n';
}
- 没有
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);
}
}
与类似但较不极端的结果。
我的第一个想法是排序会将数据放入缓存中，但这是愚蠢的，因为数组刚刚生成。
- 到底发生了什么？
- 为什么处理排序后的数组比处理未排序的数组快？
代码正在对一些独立的项求和，所以顺序不应该有影响。
相关/后续问答关于使用不同/较新编译器和选项产生相同效果的问题：
cmov（gcc 优化标志 -O3 使代码比 -O2 更慢)），那么有序或无序并不重要。但是当问题不像计数那样简单时，不可预测的分支仍然是一个非常真实的问题，因此删除这个问题是不明智的。 - Peter Cordesarray[i]>128比较进行条件复制或交换。(除非您要多次计数，并且希望将数组的大部分分区以使其仍然快速，在一些附加或修改后未分区的部分中出现错误预测)。如果您可以让编译器执行此操作，最好使用SIMD进行向量化，或者至少在数据不可预测时使用无分支标量。(请参见上面的评论获取链接。) - Peter Cordes