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
It will load the correct branch in pipeline and correct sequence 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 사이의 올바른 동작을 예측하는 것은 매우 어렵습니다.