C++에서 정렬된 배열이 정렬되지 않은 배열보다 더 빠르게 처리되는 이유는 무엇일까?

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, ..., B

배열이 오름차순으로 정렬되어 있으면 앞쪽 절반은 계속 조건이 거짓(연산 A), 뒤쪽 절반은 계속 참(연산 B)이 됩니다. CPU는 이러한 규칙적인 패턴을 쉽게 학습하여 올바른 분기를 파이프라인에 미리 적재할 수 있습니다. 그 결과 예측 성공률이 매우 높아져 A, A, A, ..., B, B 순서로 중단 없이 빠르게 처리됩니다.

정렬되지 않은 배열의 경우

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

반면 배열이 무작위로 섞여 있으면 조건의 결과가 A와 B 사이를 불규칙적으로 오갑니다. 이런 경우에는 분기 예측이 제 역할을 하기 어렵습니다. CPU가 다음 분기를 정확히 맞히기가 매우 힘들고, 예측이 틀릴 때마다 파이프라인을 비우고 다시 시작하는 분기 실패(branch miss) 비용이 반복적으로 발생합니다.

결론

즉, 데이터 자체를 처리하는 시간은 동일하더라도, 정렬된 데이터는 분기 패턴이 규칙적이어서 CPU의 분기 예측기가 높은 정확도로 동작할 수 있기 때문에 전체 실행 속도가 훨씬 빨라집니다. 이는 알고리즘 복잡도가 같더라도 데이터의 배치와 메모리 접근 패턴이 실제 성능에 큰 영향을 미칠 수 있음을 보여주는 대표적인 사례입니다.