반복문에서 i,j와 j,i의 속도 차이

i,j
int a[20][20] = {1,};
for (int i=0; i<20; i++) {
  for (int j=0; j<20; j++) {
    sum += a[i][j];
  }
}

j,i
int a[20][20] = {1,};
for (int j=0; j<20; j++) {
  for (int i=0; i<20; i++) {
    sum += a[i][j];
  }
}

두개의 코드의 시간복잡도는 동일하다. 하지만, 두개의 처리속도가 동일하지는 않다.

그 이유는 데이터 지엽성에 따른 cash hit, cash miss현상때문이다.

 

processor인 cpu는 외부 메모리 말고, 내부 L1,L2,L3라는 캐시를 가지고 있고, 데이터를 가져올때, L1~3에 캐시데이터가 없어서 외부에서 데이터 정보를 가져오는 것을 cash miss라고 한다.

 

캐시 데이터 접근은 L1 -> L2 -> L3 -> 외부 메모리 순으로 진행되고, 캐시 데이터 load는 외부 메모리 -> L3 -> L2 -> L1순서로 저장하게 된다.

 

 또한 데이터를 가져올때, 해당하는 데이터뿐만 아니라, 주변에 있는 데이터도 한번에 긁어오게 되는데(한번 긁어오는데 까지 resource를 많이 사용해야되니깐, 효율성 측면에서), 한번에 긁어오는 순서대로 반복문을 돌리게되면, 더 빠른속도로 작동하게 된다.

 

실제 주소값은

a[0][0]:7fff8981c830
a[0][1]:7fff8981c834
a[0][2]:7fff8981c838
a[1][0]:7fff8981c880
a[1][1]:7fff8981c884
a[1][2]:7fff8981c888

과 같이 저장되어있으며, 동일 행에 순서대로 저장후, 다음 행에 저장되는것을 확인할 수 있다.

따라서 데이터를 가져올때, cash hit이 발생할 가능성이 높은 i,j순서대로 반복문을 실행하는것이 대체로 처리속도가 빠를 가능성이 높다.

 

어느정도로 빠른가에 대한 대답은 cpu와 처리하는 언어의 컴파일러마다 다르다고 생각해야되며, 어느부분들을 고려해야되는지에 대한것은 아래 참조한 글을 확인하면 알수있다.

 

각각 L1 L2 L3에 대한 access latency, cpu의 초당 처리 속도(2GHz), 64~32bit등등이 영향을 끼치는 요소이다.

 

참조: https://frogred8.github.io/docs/014_cache_line/