Duff’s Device 는 메모리 복사에 사용되는 최적화 기법이다.

1983년 12월 Lucasfilm 에서 일하던 Tom Duff 가 고안하였다.

이 기법은 흔히 알려진 Loop Unrolling 의 근간이 되었다.

일반 복사

복사기능을 하는 코드를 C 로 표현해보면 다음과 같다.

void copy_byte( char* dst, char* src, int cnt )
{
    while ( cnt-- > 0 )
        *dst++ = *src++;
}

byte 단위로 복사하는 순진한 코드이고 더 최적화할 여지는 있지만 기본적인 컨셉은 위와 같다.

Duff’s Device 복사

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가지 특징으로 인해 정상적으로 작동된다.

1. switch 구문의 느슨한 명세. case 라벨은 다른 어떠한 구문의 앞에 prefix 형태로 존재해도 문법적으로 유효하다는 점.
2. C 언어에서 loop 의 중간부분으로 jump 할 수 있는 기능.

퍼포먼스

테스트를 통해 이 둘의 퍼포먼스를 비교해 보았다.

256 MB 의 메모리를 복사하는데 걸린 시간을 측정하였으며, i5 + 4GB ram + Windows7 64bit 머신에서 Release 로 빌드한 결과이다.

Duff’ Device 가 대략 2배 빠르게 나타났다.

Duff 의 코드는 Loop Unrolling 을 통해 코드상 branch 되는 횟수가 많이 줄었으며 (이 부분이 속도 향상에 가장 큰 영향을 미친다.) switch-case 문의 꼼수로 나머지reminder 를 심플하게 처리한다.

마지막으로

위에서 소개한 Duff’s Device 가 가장 빠른 복사 알고리즘은 아니다.

한 예로, 위에 소개한 일반복사 를 4byte 버전으로 수정하였더니 125.22 ms 로 Duff’s Device 보다도 빨랐다. 이 마저도 Loop Unrolling 을 하면 더 빨라질 수도 있다. 1)

Duff’s Device 의 사용법은 문법적으로 많은 논란의 대상이 되어왔다. 그리고 올바르게 최적화해주지 않는 컴파일러를 거치면 속도가 느려질 수도 있다.

따라서 Duff’s Device 복사를 그대로 사용하기 보다는 이 테크닉을 가능케 하는 언어적 특성을 이해하고 활용할 만한 곳을 찾아보는 것이 더 좋다고 생각한다.

대신 활용하기 전에는 반드시 대상의 아키텍쳐, 최적화 레벨, 컴파일러를 고려하여 꼼꼼한 테스트 후, 안정적이고 더 빠르다는 확신이 있을때만 사용되어져야 하겠다.