C++에서 정렬되지 않은 배열보다 정렬된 배열을 처리하는 것이 더 빠른 이유는 무엇입니까?

C++에서는 분기 예측 때문에 정렬되지 않은 배열보다 정렬된 배열을 처리하는 것이 더 빠릅니다. 컴퓨터 아키텍처에서 분기 예측은 프로그램의 명령 흐름에서 조건 분기(점프)가 수행될 가능성이 있는지 여부를 결정합니다.

예를 들어 보겠습니다 -

if(arr[i] > 50) {
   Do some operation B
} else {
   Do some operation A
}

100개의 요소에 대해 이 코드를 정렬되지 않고 정렬된 순서로 실행하면 다음과 같은 일이 발생합니다. -

정렬된 배열의 경우 -

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

파이프라인의 올바른 분기와 올바른 순서를 로드합니다.

A, 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 사이의 올바른 동작을 예측하는 것은 매우 어렵습니다.