C++에서 정렬된 배열이 정렬되지 않은 배열보다 처리 속도가 빠른 이유는 무엇일까?

핵심 원리: 분기 예측(Branch Prediction)

C++에서 정렬된 배열을 처리하는 것이 정렬되지 않은 배열보다 빠른 이유는 바로 분기 예측(branch prediction) 때문입니다. 컴퓨터 아키텍처에서 분기 예측이란 프로그램 명령어 흐름에 나타나는 조건 분기(점프)가 실행될지 말지를 CPU가 미리 추측하는 기술을 의미합니다.

현대 CPU는 파이프라인 방식으로 동작하기 때문에 다음에 실행할 명령어를 미리 예측해 불러와야 최고 성능을 낼 수 있습니다. 예측이 맞으면 파이프라인이 끊기지 않고 계속 작동하지만, 예측이 틀리면 이미 진행 중인 작업을 버리고 다시 시작해야 하므로 상당한 성능 저하가 발생합니다.

간단한 예제 코드

if(arr[i] > 50) {
    // 연산 B 수행
} else {
    // 연산 A 수행
}

위 코드를 100개의 요소에 대해 정렬된 배열과 정렬되지 않은 배열로 각각 실행하면 어떤 차이가 생기는지 살펴보겠습니다.

정렬된 배열의 경우

1, 2, 3, 4, 5, …… 50, 51………100
A, A, A, A, A, A, B, B

배열이 오름차순으로 정렬되어 있으면 앞쪽 요소들은 조건을 만족하지 않아 연산 A가, 뒤쪽 요소들은 조건을 만족해 연산 B가 순서대로 실행됩니다. 즉, 분기 패턴이 매우 규칙적이므로 CPU는 올바른 분기를 파이프라인에 미리 적재하고 일관된 순서로 처리할 수 있습니다.

A, A, A, A, A, A, A, A, B, B

정렬되지 않은 배열의 경우

5, 51, 6, 90, 4, 49, 60…
A, B, A, B, A, A, A, B

반면 배열이 뒤섞여 있으면 연산 A와 B가 무작위로 번갈아 나타납니다. 이런 경우에는 분기 예측이 큰 역할을 하지 못하며, CPU가 A와 B 중 어떤 연산이 실행될지 정확히 맞추기가 매우 어렵습니다. 예측 실패가 잦아질수록 파이프라인 플러시가 반복되어 전체 처리 속도가 느려집니다.

정리

결국 데이터가 정렬되어 있으면 분기 패턴이 예측 가능해져 CPU의 분기 예측기가 거의 항상 정확하게 동작하고, 그 결과 파이프라인이 중단 없이 효율적으로 유지됩니다. 반면 정렬되지 않은 데이터는 예측 실패가 빈번하여 같은 코드라도 눈에 띄게 느리게 실행됩니다. 따라서 조건 분기가 많은 반복문에서는 데이터를 미리 정렬해 두는 것만으로도 상당한 성능 향상을 얻을 수 있습니다.