for (int j = 0; j < N; j++){
for (int i = 0; i < M; i++){
a[i][j] += 1;
}
}
이 코드는 i와 j의 위치를 바꾼 코드보다 훨씬 느리다.
(간단한 코드라 컴파일러가 최적화할지는 모르지만, 논리적으로 그렇다.)
cpu캐시는 64byte이고, ram접근은 100클럭 이상이다.
비트연산은 1클럭이다.
cpu캐시히트가 나면 캐시 접근으로 빠르게 처리하지만 안 나면 램 접근으로 100클럭을 쓴다.
램 한번 접근 시간=비트연산 100번 시간이다.
위의 코드는, 물리적으로 붙어 있는 값을 같이 처리하지 않기 때문에, 대부분 상황에서 캐시미스가 난다.
같은 언어에 같은 알고리즘인데도 100배 차이가 나는 것이 가능하다.