최적화 기법 중 루프 풀기를 안 들어 본 사람은 거의 없을 듯하다. 위키에 있는 코드를 무단으로 복사.

for (int x = 0; x < 100; x++)
  delete(x);

이 루프를 풀어헤치면..

for (int x = 0; x < 100; x += 5) {
  delete(x);
  delete(x+1);
  delete(x+2);
  delete(x+3);
  delete(x+4);
}

이렇게 해서 얻는 이득은 루프 순환에 대한 비용, 크게 두 가지로 생각하면: (1) 루프 탈출 비교 검사(x < 100)와 (2) 분기문 자체의 비용을 줄 일 수 있다. (1)은 자명하고 (2)는 뭐 파이프라인 어쩌고 그런 것임. 그러나 만약 루프 길이가 어느 정도 길다면 CPU 안에 있는 분기 예측기(캐시 같은 장치라고 보면 됨)가 아주 훌륭히 돌아가므로 (2) 문제는 상당히 해소된다.

그렇다면 루프 풀기로 인한 단점은? 코드 크기가 증가하여 발생하는 여러 문제점(캐시..)과 루프 한 순환 길이가 커지니 레지스터 할당의 압박(레지스터가 부족해서 몇몇 임시 변수들은 스택이나 메모리로 쫓겨 나야)이 있겠다. 또, 위에서 본 엄청나게 간단한 경우 말고, 루프를 5번 풀었는데 순환 횟수가 5의 배수가 아니라면 나머지 경우도 적절히 처리 잘 해줘야 한다.

그런데 이렇게 프로그래머가 노가다 말고 컴파일러도 스스로 알아서 루프를 ‘적절히’ 풀어준다. 최적화 옵션을 주면 대부분의 컴파일러는 어느 정도 루프 풀기를 해준다. 아래 아주 간단한 산수 코드를 VC++에서 그냥 보통 최적화(/O2)를 주면…

// 원 프로그램 (입력 받은 숫자 만큼의 합을 구해 출력)
1: int main(int argc, char* argv[])
2: {
3:   int count = atoi(argv[1]), sum = 0;
4:   for (int i = 1; i <= count; ++i)
5:     sum += i;
6:   printf("%d", sum);
7:   return 0;
8: }

아래처럼 변하는데… 어셈블러 이해하는 게 좀 간단치 않더라. 그래서 열심히 C 코드로 의역해보았다. 아래 C 코드를 돌리면 원 프로그램과 정확하게 똑같이 돌아간다.

// 최적화 후 바뀐 코드 (최적화된 기계어 코드를 의역) 
 1: int main(int argc, char* argv[])
 2: {
 3:   int count = atoi(argv[1]); // eax
 4:   int sum_temp = 0;          // edi
 5:   int sum = 0;               // esi
 6:   int temp = 0;              // ebx
 7:   int count_temp = 0;        // edx
 8:   int i = 1;                 // ecx
 9:
10:   if (count >= 2 ) {
11:     count_temp = count-1;
12:     do {
13:       sum_temp += i;
14:       sum += i+1;
15:       i += 2;
16:     } while (i <= count_temp);
17:   }
18:
19:   if (i <= count)
20:     temp = i;
21:
22:   sum += sum_temp;
23:   sum += temp;
24:   printf("%d\n", sum);
25:   return 0;
26: }

프로그램 자체가 워낙 작아 최적화 하더라도 필요한 변수는 고작 6개. 그래서 이 여섯 변수는 모두 레지스터에 할당이 되어 실제 메모리를 사용하지는 않는다. 이런 걸 변수들이 enregistered 되었다고 표현.

우리가 보려는 건 루프 풀기. 루프 풀기가 일어난 곳은 12라인에 있는 do 루프. (어셈블리로 되어있는 순환문을 그냥 do-while로 바꾼 것일 뿐) 보다시피 덧셈 부분이 두 번 일어나고 루프 카운터 변수 i도 2씩 증가하므로 원래 루프를 두 번 풀었음을 볼 수 있다.

그런데 카운트가 짝수이거나 홀수 일 때, 또 크기가 2보다 작다면 여러 예외 사항이 발생하므로 정확성을 보존하는 코드도 당연히 잘 생성되었다. 통상 이런 걸 프롤로그, 에필로그라고 하는데, 이렇게 간단한 시그마 합 구하는 루프도 그리 직관적이지 않는 방법으로 루프 풀기가 되었다.

이런 루프 풀기 옵션은 좀 더 세밀히 옵션을 줄 수도 있다.

VC++에다 인텔 컴파일러 깔면 이런 거 볼 수 있다. (VC++도 아마 자체 옵션이 있을 수도)

가장 중요한 이 루프 풀기로 인한 성능 향상은.. 어셈블리 해석하느라 지쳐 생략… 누가 해주시면 감사..

루프 풀기의 고전은 Duff’s device라는 것이 있다.

do {                          /* count > 0 assumed */
    *to = *from++;            /* Note that the ''to'' pointer is NOT incremented */
} while (--count > 0);

dsend(to, from, count)
char *to, *from;
int count;
{
    int n = (count + 7) / 8;
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
               } while (--n > 0);
    }
}

do-while 루프를 총 8번 풀어 헤치는데 그렇다면 루프 순환이 8의 배수가 아닐 경우를 처리 해야 한다. Duff씨의 고안은 이 나머지 처리를 기가 막힌 트릭으로 해결하고 있다. 저런 테크닉은 난 태어나서 이 코드에서 처음 봤다. 유심히 switch-case가 어떻게 되어있는지 가만히 살펴 보라. 코드를 보면 맨 처음 나머지 만큼 점프를 하여 그 부분을 반복하고 그 뒤에는 8의 배수 만큼 계산한다.

그런데 이건 지나치게 코드를 증가 시키는 단점이 있어 위키를 보니 XFree86 Server에서 이 부분을 제거하니 상당한 코드 크기 감소와 성능 향상이 있었다고 한다. 이 코드는 과거 프로세서에서는 통했을지 모르겠으나 최신 프로세서에서는 유효하지 않을 수 있다. XOR를 이용한 변수 교환 역시 그러하다. 그러니 무엇이던 최적화를 할 땐 대상 컴퓨터에서 간단한 미니 벤치마크로 정확하게 정량적인 데이터를 얻어 결정해야 할 것이다.

x86에는 CMOV라는 conditional mov 연산이 있다. CMOV에 깔린 배경을 설명하자면 너무 길고, 분기문의 오버헤드를 조금이라도 줄이려고 펜티엄 프로부터 지원된 연산이다. 그런데 이게 펜티엄 4까지만 해도 성능이 별로 안 좋았다. 그러나 요즘은 많이 나아져서 예측이 힘든 분기문에서는 CMOV가 일반적인 비교+점프보다 더 나을 때가 많다. 역시 CMOV 이것도 여러 복잡한 변수가 있으므로(CMOV는 EFLAGS 의존성을 추가시켜서 예상치 못한 직렬화를 유발시킬 수 있음) 직접 돌려봐서 빠른지 확인해야만 한다. (리누스 토발즈 아저씨는 매우 강한 어조로 x86 CMOV를 욕했는데 꼭 그러하지는 않음. 내가 실험해본 결과도 그러하고…)

여기서 다시 한번 최적화의 기본 명제: “어설픈 최적화는 하지 않는 것” 이라는 명언을 떠올린다.