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와 같은 코드들을 보통의 코드로 변경함으로서 오히려 더 빠른 성능을 얻을 수도 있다는 뜻이고 따라서 이런 루프 풀기를 적용하려고 할 때에는 정말 도움이 될지 미리 벤치마크를 잘 해봐야 한다. 만약 벤치마크 해보는 것이 귀찮다면 루프 풀기가 아닌 보통의 코드를 사용하는 쪽으로 베팅하는 것이 심신에도 좋고 동료들과의 관계에도 이로울 것이라 확신한다.
