Media Log

[loop unrolling]에 해당되는 글 1

  1. h Duff's Device 2011.04.07

Duff's Device

2011.04.07 07:47 | Programming
Duff's Device는 Tom Duff라는 사람이 1983년도에 생각해낸 switch 문장을 사용한 loop unwinding 얍삽이이다.
위키피디아에는 다음 코드가 인용되어져 있다.
send(to, from, count)
register short *to, *from;
register count;
{
    register 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);
    }
}
얼핏보면 switch 문장안에 do while 루프가 들어있는 것이 컴파일도 되지 않을 것처럼 보이지만 신기하게도 어느 컴파일러에서나 잘 컴파일된다.

이 코드가 컴파일 가능한 이유는 C언어의 switch 문법이
switch ( expression )
{
case constant-expression :
    statement-list
    break ;

case constant-expression :
    statement-list
    break ;

...

default :
    statement-list
    break ;
}
이 아니라 단지

switch ( expression )
    statement
이기 때문이다.

switch는 if문이나 for문 처럼 바로 뒤에 단일 문장이 올 수도 있고 블록으로된 문장들이 오는 것이 가능하다. 꼭 case 레이블이 바로 뒤따르지 않아도 된다는 뜻이다.
즉, 아래와 같은 코드도 적법하다.
switch(nn % 4)
{
for(; nn > 0; nn -= 4)
    {
case 0:    *destp++ = *srcp++;
case 3:    *destp++ = *srcp++;
case 2:    *destp++ = *srcp++;
case 1:    *destp++ = *srcp++;
    }
}

다시 처음에 나왔던 Duff's Device의 switch문을 보면, 그 코드는 마치 아래와 같이 동작할 것이다. 루프의 중간부분 부터 끼어들어갈 수 있다는 것이 중요하다.
switch(count & 7)
{
case 0 : goto lbl0;
case 1 : goto lbl1;
case 2 : goto lbl2;
case 3 : goto lbl3;
case 4 : goto lbl4;
case 5 : goto lbl5;
case 6 : goto lbl6;
case 7 : goto lbl7;
}

lbl0:
    while(count > 0)
    {
        handle_one();
        count--;
lbl1:
        handle_one();
        count--;
lbl2:
        handle_one();
        count--;
lbl3:
        handle_one();
        count--;
lbl4:
        handle_one();
        count--;
lbl5:
        handle_one();
        count--;
lbl6:
        handle_one();
        count--;
lbl7:
        handle_one();
        count--;
    }

이런 코드가 보통의 루프보다 빠른 이유는 불필요한 비교문을 줄여주기 때문이다.
do {                
    *a = *b++;
} while (--count > 0);
위 코드에서 몇번이나 count가 0과 비교 되겠는가. b의 포인터 증가 연산은 몇번 일어나겠는가. 쉽다. count 번이다.
Duff's device에서는 루프를 손으로 풀어서 씀으로써 count / 8 만큼으로 테스트 횟수를 줄일 수 있게 된다. (포인터 증가 연산은 줄일수 없고 비교연산만 줄일 수 있다)
꼭 8로 나눌 필요는 없으며, 이는 적절히 조정하면 된다. Duff는 캐시 사이즈를 고려해서 8 정도로 결정한 것 같다. 루프를 많이 풀어 쓸수록 더 많은 코드가 생성이되고 함수 크기가 커지게 될 것이다.

그런데 루프를 풀어서 쓰기 위해서 왜 꼭 switch 문을 사용한 것일까.
for(int i = 0; i < 100; i =+ 8)
{
    *a = *b++;
    *a = *b++;
    *a = *b++;
    *a = *b++;
    *a = *b++;
    *a = *b++;
    *a = *b++;
    *a = *b++;
}
위처럼 루프를 풀어내는 것도 물론 가능하다. 그런데 숫자가 딱 나누어 떨어지지 않으면(위 예에서는 100 / 8) 나머지 처리를 밑에서 한번 더 해주어야 한다. Duff의 코드에서는 n을 (count + 7) / 8 로 정하고 case 구문의 숫자 위치를 적절히 배열하여 나머지 처리를 안해도 되도록 한 것이 중요한 포인트이다. 이렇게 하면 한방에 깔끔하게 처리할 수 있고 따라서 텍스트의 크기도 약간 더 작아진다. 사실 이 포인트가 C언어의 문법으로 범용적인 loop unrolling을 구현가능하게 하는 것이며 Duff's Device라고 불리는 아이디어이다.

그런데 요즘 우리가 쓰는 거의 대부분의 컴파일러들은 최적화를 위해 loop unwinding을 지원하고 있으며, 손으로 루프를 풀어서 쓴 것보다 더 효율적으로 코드를 생성해준다. 오히려 그런 손으로 풀어쓴 루프가 컴파일러의 최적화를 방해해서 더 느린 코드가 생성될 수도 있다. 보기에 안좋은 것은 말할 필요도 없다.
이것은 이미 어딘가에 사용되고 있는 Duff's Device와 같은 코드들을 보통의 코드로 변경함으로서 오히려 더 빠른 성능을 얻을 수도 있다는 뜻이고 따라서 이런 루프 풀기를 적용하려고 할 때에는 정말 도움이 될지 미리 벤치마크를 잘 해봐야 한다. 만약 벤치마크 해보는 것이 귀찮다면 루프 풀기가 아닌 보통의 코드를 사용하는 쪽으로 베팅하는 것이 심신에도 좋고 동료들과의 관계에도 이로울 것이라 확신한다.
저작자 표시 비영리 동일 조건 변경 허락
신고

submit