다음 두 코드는 좀 복잡해 보이지만 하는 일이 똑같다. 어느 코드가 더 빠를까? (병렬 행렬 곱셈 코드 중 일부분인데, 행렬을 격자 모양으로 자른 뒤, 그것을 각각 곱하고 결과를 취합하는 코드이다.)

#pragma omp for 
for (i = 0; i < M/B; ++i) {
  for (j = 0; j < M/B; ++j) {
    for (k = 0; k < M/B; ++k) {
      for (x = 0; x < B; ++x) {
        for (y = 0; y < B; ++y) {
          for (z = 0; z < B; ++z) {
            tC[i*B*M+j*B*B+x*B+y] += tA[i*B*M+k*B*B+x*B+z] * tB[k*B*M+j*B*B+z*B+y];
          }
        }
      }
    }
  }
}
 
#pragma omp for
for (i = 0; i < M/B; ++i)
  for (j = 0; j < M/B; ++j)
    for (x = 0; x < B; ++x)
      for (y = 0; y < B; ++y)
        par_tiled_output[i*B*M+j*B+x*M+y] = tC[i*B*M+j*B*B+x*B+y];

#pragma omp for 
for (i = 0; i < M/B; ++i) {
  for (j = 0; j < M/B; ++j) {
    for (k = 0; k < M/B; ++k) {
      for (x = 0; x < B; ++x) {
        for (y = 0; y < B; ++y) {
          for (z = 0; z < B; ++z) {
            tC[i*B*M+j*B*B+x*B+y] += tA[i*B*M+k*B*B+x*B+z] * tB[k*B*M+j*B*B+z*B+y];
          }
          par_tiled_output[i*B*M+j*B+x*M+y] = tC[i*B*M+j*B*B+x*B+y];
        }
      }
    }
  }
}

썰렁한 답변이지만 "그 때 그 때 달라요"가 정답이다. 그러나 대부분의 경우 후자보다 전자의 코드가 더 빠르게 돌아갈 확률이 크다고 답할 수 있다. 특히 tC, tA, tB와 같은 배열의 크기가 제법 클 경우에는 전자가 더 빨리 돌아간다.

그 이유는 쉽게 예상하겠지만, 전자의 코드가 데이터 접근의 지역성(locality)를 더 많이 활용하므로 캐쉬 미스가 더 줄고, 결과적으로 더 빠르게 작동할 수 있는 것이다. 캐쉬 미스를 줄여, 복잡한 for 루프로 인한 각종 오버헤드를 뛰어넘는 것이다. 물론 분기문이 들어가면 골치아파지지만 규칙성이 강한 for 루프는 비교적 큰 어려움 없이 CPU가 처리할 수 있다.

실제로 위 두 코드를 Xeon 쿼드 코어 프로세서에서 돌려보면 전자의 코드가 5~8% 정도 빠른 성능을 일관되게 보여준다. 만약 코드에서 사용된 배열의 크기가 크다면 더 큰 성능 차이를 보일 수도 있다.

이러한 기법을 흔히 Loop Fission, 루프 분할(?) 라고 부른다.

// Original loop
int i, a[100], b[100];
for (i = 0; i < 100; i++) {
  a[i] = 1; 
  b[i] = 2;
}

// After loop fission
int i, a[100], b[100];
for (i = 0; i < 100; i++) {
  a[i] = 1;                     
}
for (i = 0; i < 100; i++) {
  b[i] = 2;
}

이렇게 데이터 참조하는 부분을 각기 다른 루프에 나눠 캐쉬 사용성을 극대화 하는 것이다. 그리고 이 반대로 하나의 루프로 합치는 것을 Loop Fusion이라고 부르기도 한다. 위에서 예로든 행렬 곱셈의 경우에는 오히려 루프를 합치는 것이 나쁜 경우이다.

요즘 L2 캐쉬가 6MB 씩이나 되고 (물론 듀얼코어가 합쳐서 쓰는 용량이기는 하지만) 속도가 많이 빨라져서 캐쉬 효율성까지 고려한 프로그래밍을 과연 데스크탑, 서버에서 짜야하는지 의문이 들지도 모른다. 그러나 여전히 이런 저수준의 최적화는 매우 효과적이다. 자료구조의 형태를 보다 캐쉬 후렌들리(...) 하게 바꾸면 지금의 아주 빠른 최신 듀얼 코어 프로세서에서도 여전히 큰 성능 향상을 기대할 수 있다.