회사에서 성능 튜닝하다가 진짜 이해가 안 되는 걸 발견해서 질문 올립니다. 아래처럼 배열을 쭉 돌면서 조건 맞는 값만 더하는 단순한 코드가 있어요.
for (int i = 0; i < SIZE; i++) {
if (data[i] >= 128)
sum += data[i];
}
이 루프를 여러 번 돌리는데, 배열을 미리 정렬(sort)해두고 돌리니까 정렬 안 하고 돌릴 때보다 몇 배나 빨라지더라고요. 데이터 값도 똑같고 더하는 결과도 똑같습니다. 반복 횟수도 같고요.
제 상식으로는 시간 복잡도가 둘 다 O(n)으로 같으니까 속도도 비슷해야 하는 거 아닌가요? 정렬하는 시간은 따로 계산에서 뺐는데도 그래요. 데이터 배치 순서만 바뀌었을 뿐인데 왜 실측 속도가 이렇게 차이 나는 건지 도무지 모르겠습니다. CPU 내부에서 뭔가 일어나는 건가요?