Stream :: Duff's Method

Duff's Method

Computer Science/General CS 2009/01/22 13:24

[Duff's Method]

데이터를 옮기거나 처리할떄, for문이나 while문을 쓰는데, 데이터 하나 처리할떄 한번 비교하는 기존의 반복문은 비효율적!
-> 한번 비교로 여러 작업을 한번에 하고 싶지만, 그렇게 하면 마지막에 추가로 처리해버리는 경우도 있다는 것이 문제!
-> 반복문과 swtich-case문을 함께 적절히 쓰면 속도가 매우 향상될 수 있다.

[Example]

(아래 메일 해석 참고)

[참고자료]

1. duff's mail: http://www.lysator.liu.se/c/duffs-device.html

2. 위키피디아: http://en.wikipedia.org/wiki/Duff's_device

3. 포스팅 1: http://ideathinking.com/cpptips/y2k2/duffs_device.html

4. 포스팅 2: http://www.sour.co.kr/tc/simpsons/entry/Duffs-Device?category=1

5. 포스팅 3: http://agrumpy.egloos.com/307838

6. 포스팅 4: http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

7. Duff's Algorithm을 이용한 속도향상(KLDP): http://kldp.org/node/38269

8. if문과 switch문의 성능에 대한 논의(KLDP) : http://kldp.org/node/62262

[붙임]

(1번 참고 문헌의 메일 해석 ( http://agrumpy.egloos.com/307838 에서 발췌)

Evans & Sutherland Picture System의 programmable IO data register로 short 데이터 배열을 복사하는 다음 루틴을 보죠.



        send(to, from, count)

        register short *to, *from;

        register count;

        {

                do

                        *to = *from++;

                while(--count>0);

        }

(물론 count가 0이면 이 루틴은 실패하지요)

VAX C 컴파일러는 이 루프를 두개의 인스트럭션으로 컴파일합니다. (movw와 sobleq라고 생각됩니다만) 해보면 알 수 있듯이, 이 루프는 실시간 에니메이션 재생 프로그램의 가장 큰 병목이 됩니다. 50% 정도 느리게 되지요. 이런 경우 속도를 높이는 전통적인 방법은 sobleq를 줄여 루프를 조금 돌게 만드는 것이지요. 그렇게 하면, 남은 바이트들을 처리하는 문제가 남게 됩니다.

저는 C를 쓸 때는 이것을 원래 루프문 안에 인덱스를 달아놓은 switch를 사용해 처리합니다. 물론 어셈블 언어로 코드를 짤 수 있다면, 바로 남은 바이트들을 처리하도록 루프 중간으로 점프하도록 했겠지요. 어제 이걸 고민하다가 다음과 같은 코드를 만들었습니다.



        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);

                }

        }