Duffs device
In the C programming language, Duff's device is a way of manually implementing loop unrolling by interleaving two syntactic constructs of C: the do-while loop and a switch statement. Its discovery is credited to Tom Duff in November 1983, when Duff was working for Lucasfilm and used it to speed up a real-time animation program.
Loop unrolling attempts to reduce the overhead of conditional branching needed to check whether a loop is done, by executing a batch of loop bodies per iteration. To handle cases where the number of iterations is not divisible by the unrolled-loop increments, a common technique among assembly language programmers is to jump directly into the middle of the unrolled loop body to handle the remainder. Duff implemented this technique in C by using C's case label fall-through feature to jump into the unrolled body.
Example
Duff 가 제시한 더 빠른 복사코드이다.
void copy_duff( char* dst, char* src, int cnt )
{
int repeat = ( cnt + 7 ) / 8;
switch ( cnt % 8 )
{
case 0: do { *dst++ = *src++;
case 7: *dst++ = *src++;
case 6: *dst++ = *src++;
case 5: *dst++ = *src++;
case 4: *dst++ = *src++;
case 3: *dst++ = *src++;
case 2: *dst++ = *src++;
case 1: *dst++ = *src++;
} while ( --repeat > 0 );
}
}
물론 대상 메모리가 8바이트의 배수가 아니더라도 잘 작동한다.
위 코드는 C 언어의 다음 2가지 특징으로 인해 정상적으로 작동된다.
- switch 구문의 느슨한 명세. case 라벨은 다른 어떠한 구문의 앞에 prefix 형태로 존재해도 문법적으로 유효하다는 점.
- C 언어에서 loop 의 중간부분으로 jump 할 수 있는 기능.