以下は、非常に奇妙な動作を示す C++ コードの一部です。奇妙な理由で、(タイミング領域の前に) データを並べ替えると、奇跡的にループがほぼ 6 倍速くなります。
#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 秒で実行されます。
(並べ替え自体は、配列を 1 回通過するよりも時間がかかるため、未知の配列に対してこれを計算する必要がある場合、実際には行う価値はありません。)
最初は、これは単なる言語またはコンパイラの異常ではないかと考えたので、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);
}
}
同様の結果ですが、それほど極端ではありません。
最初に考えたのは、並べ替えによってデータがキャッシュに取り込まれるということでしたが、配列が生成されたばかりなので、それはどれほどばかげていると思いました。
- 何が起こっている？
- 並べ替えられた配列の処理が、並べ替えられていない配列の処理よりも速いのはなぜですか?
コードはいくつかの独立した用語を要約しているため、順序は重要ではありません。
関連/フォローアップの Q&Aは、異なる/新しいコンパイラとオプションでの同じ効果について:
