c++ - Javaと C言語 共通 点 - 並べ替えられた配列の処理が、並べ替えられていない配列の処理よりも速いのはなぜですか?

C 意味 / java / performance / optimization / branch-prediction

非常に奇妙な動作をするC++のコードがあります。何か不思議な理由で、データをソートすると、コードが奇跡的に約6倍速くなります。

#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;
}

当初は、言語やコンパイラの異常かと思い、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);
    }
}

Aplet123



Answer #1

同じ行で(これはどの回答でも強調されていなかったと思います)、時々(特に、Linuxカーネルのようにパフォーマンスが重要なソフトウェアで)次のようなifステートメントを見つけることができることを言及するのは良いことです。

if (likely( everything_is_ok ))
{
    / *何かをする* /
}

などと言われています。

if (unlikely(very_improbable_condition))
{
    / *何かをする* /    
}