이상하고 아름다운 JAVA 퀴즈 6

문제

import java.util.*;

public class Q6 {

    public static void main(String[] args) {
        Random random = new Random();
        
        int[] array = new int[100000];

        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(500);
        }
        //0부터 499 사이의 랜덤한 숫자를 100000개 생성하여 배열에 저장

        System.out.println(doLoop(array)); //A (정렬하지 않은 배열 대상으로 loop)

        Arrays.sort(array);

        System.out.println(doLoop(array)); //B (정렬한 배열 대상으로 loop)
    }

    private static int doLoop(int[] array) {
        long startTime = System.currentTimeMillis();
        long sum = 0; //임시 변수

        for (int i = 0; i < 10000; i++) { //배열 반복을 10000번 반복 (수행 시간 측정 위해)
            for (int j = 0; j < array.length; j++) {
                if (array[j] < 250) {
                    sum += array[j];
                }
            }
        }

        return (int) (System.currentTimeMillis() - startTime); //수행 소요시간 반환
    }
}

A와 B에서 출력되는 값(반복문 수행시간)은 유사한가?

 

아니면 유의미한 차이가 있는가?

 

정답

B가 훨씬 빠르다.

환경마다 다르겠지만, A는 2814ms, B는 488ms가 소요되었다.

 

순서를 바꿔서 정렬된 배열에 대해 먼저 반복문을 수행해도 마찬가지로,

정렬된 배열의 반복이 훨씬 빠르다.

 

이는 Branch Prediction (분기 예측) 때문이다.

 

정렬된 데이터에 대해 if (array[j] < 250) 조건 분기는

처음 약 50%의 데이터는 true값을, 나머지 데이터는 false값을 연속적으로 가진다.

 

이는 CPU의 분기예측기의 효율을 끌어올릴 수 있다. (해당 분기에 의해 반복적으로 같은 위치로 jump됨을 감지)

 

그러나 조건의 결과가 무작위적인경우, 분기예측기는 50%확률로 예측에 실패할 것이고

성능에 악영향을 끼치게 된다.

 

참고  : https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array?rq=2