Skip to content

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 할 수 있는 기능.

See also

Favorite site