Duff's Device

| 잡다한것들전부/C, C++, C# 2014. 1. 10. 13:03

Posted by 히아레인

출처 : http://allwiz.egloos.com/viewer/2803607

루프 최적화란 루프의 반복 회수를 줄이는 것을 말할 것입니다. 왜냐하면, 루프와 같은 분기 명령(JMP)이 많이 발생하면 할 수록 시스템의 성능을 저하될 것이기 때문입니다. 제 경우 현재 개발중인 프로그램에서 검색, 삽입, 수정, 삭제 처리를 위해 루프가 많은 구조다 보니, 이 루프들을 어떻게 효율적으로 줄일 수 있을까? 고민하다가 Duff's Device를 발견하게되었습니다.

1. Duff's Device
Duff's Device는 1983년 루카스필름에서 일하던 Tom Duff가 애니메이션 재생시 생기는 병목현상을 해결하기 위해 만들었다고 합니다. 그 당시에도 많은 논란이 있었다고 합니다만, 이 코드를 처음 본 제 느낌은 '우앗!' 이었습니다. 그리고 가까운 시일 내에 좀 더 테스트를 해보겠지만, 적용된다면 일반 루프에 비해 훨씬 효율적일것이라 생각합니다.

1.1 일반적인 복사
아래의 함수는 nArrSrc int형 배열의 값을 nArrDest로 복사하는 함수입니다.


const int MAX_ARRAY_SIZE = 10;

void CopyArray(int* nArrSrc, int* nArrDest, int nCount)
{
    do
    {
        *nArrDest++ = *nArrSrc++;
    } while( --nCount > 0 );
}

...
int nArrSrc[MAX_ARRAY_SIZE];
int nArrDest[MAX_ARRAY_SIZE];
...
CopyArray(nArrSrc, nArrDest, MAX_ARRAY_SIZE);

위의 예는 정상적으로 작동합니다. 그런데 만약 nCount가 1000번 혹은 10000 번이라면 얘기는 조금 달라지게 될 것입니다. 즉, 앞서 말한바와 같이 루프는 성능을 저하시키는 한 요소이기 때문입니다

1.2 Duff's Device 적용
앞서 구현한 CopyArray 함수는 Duff's Device에 의해 다음과 같이 수정될 수 있습니다.


const int REPEAT_COUNT = 8;

void CopyArrayEx(int* nArrSrc, int* nArrDest, int nCount)
{
    switch( nCount % REPEAT_COUNT )
    {
    case 0 :
        do {
        *nArrDest++ = *nArrSrc++;
    case 7 :
        *nArrDest++ = *nArrSrc++;
    case 6 :
        *nArrDest++ = *nArrSrc++;
    case 5 :
        *nArrDest++ = *nArrSrc++;
    case 4 :
        *nArrDest++ = *nArrSrc++;
    case 3 :
        *nArrDest++ = *nArrSrc++;
    case 2 :
        *nArrDest++ = *nArrSrc++;
    case 1 :
        *nArrDest++ = *nArrSrc++;
        } while ( (nCount -= REPEAT_COUNT) > 0 );
    }
}

위의 코드를 보면, switch-case문을 마치 goto문 처럼 사용한 것을 보실 수 있는데, 이를 보고 개인적으로 놀랐습니다. 세상엔 참 머리 좋은 사람이 많구나 하고요. 또한 REPEAT_COUNT로 8을 사용하였는데, 이는 캐쉬 크기에 맞춘 작업으로 보입니다. 일반적으로 위와 같이 loop unrolling 기법을 사용할 때에는 루프를 무한정 늘리는 것이 아닌 캐쉬 크기에 맞춰 8 혹은 16배의 loop unrolling을 사용한다고 합니다.

※ 참고 자료
• http://www.lysator.liu.se/c/duffs-device.html
• http://en.wikipedia.org/wiki/Duff's_device
• 여인춘, 프로그래밍 고수의 알고리즘 , 마이크로 소프트웨어 2006년 10월호, pp.298-pp.300, Loop unrolling

저작자표시

'잡다한것들전부 > C, C++, C#' 카테고리의 다른 글

동기화 비동기화 동기식 비동기식 이란? (0)	2014.01.13
추상 클래스 (C++) (0)	2014.01.10
Duff's Device (0)	2014.01.10
c++ 11 이란?? (0)	2014.01.09
strncpy 로 메모리 복사 (0)	2014.01.07
C언어 배열 초기화 방법 (0)	2014.01.07