c++ - java - Rust C 대체 - 정렬되지 않은 배열을 처리하는 것보다 정렬 된 배열을 처리하는 것이 더 빠른 이유는 무엇입니까?

Go 성능 / 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))
{
    / * 무언가를하십시오 * /    
}