rep movsd

x86 memcpy [3] MMX 이용

programming 2007. 12. 11. 17:00

memcpy의 속도를 빠르게 하기 위해서 메모리 주소를 정렬하여 복사하는 방법은 이미 보았다. 이보다 더 빠르게 복사를 하려면, 주소정렬 이외의 다른 방법을 살펴보아야 한다. 그중에서 가장 먼저 생각할 수 있는 것은 루프 언롤링(loop unrolling)이다.

루프 언롤링은 말 그대로 루프를 풀어헤쳐서 분기하는 횟수를 줄이는 것이다. 루프를 반복하는 횟수를 미리 알고 있다면, 그 횟수만큼 루프 안에서 수행되는 명령들을 그대로 나열함으로써 루프탈출 조건 검사와 분기를 없애는 것이 가능하다. 이러한 경우는 루프를 완전히 풀어헤친 경우이다. 하지만, memcpy의 경우에는 루프 반복횟수를 미리 알 수가 없다. 그러므로, 완전히 풀어헤칠 수는 없고, 적당한 선에서 조건검사와 분기의 횟수를 줄이는 것이 가능하다.

사실, 이전에 rep movsb대신 rep movsd를 썼을때 이미 루프를 4번 언롤한 것이었다. 단지 다른 명령으로 썼기 때문에 그것이 바로 눈에 띄지 않았을 뿐이다. 예를 들어 다음과 같은 루프를 생각해보자.

L0:     movsb
        dec     ecx
        jnz     L0

이 루프는 ecx가 0이 아닐때 rep movsb와 같은 효과를 내는 루프이다. 이 루프를 4번 언롤한다면,

L0:     movsb
        movsb
        movsb
        movsb
        sub     ecx,4
        ja      L0

이렇게 쓸 수 있다. (물론, 이 루프에 들어오기 전에 ecx의 값은 4보다 크거나 같아야 한다.) 여기서 4개의 movsb를 하나의 movsd로 바꾸어 주면, 이전의 memcpy 구현과 같은 것이 된다.

L0:     movsd
        sub     ecx,4
        ja      L0

그렇다면, 4번만 언롤할 것이 아니라 더 많이 하는 것을 속도 증진의 방법으로 생각해 볼 수 있다. 여기에서 MMX명령이 유용해진다. 위의 예에서 루프를 8번 언롤한 것과 같은 효과를 가지는 루프는 다음과 같다.

L0:     movq    mm0,[esi]
        movq    [edi],mm0
        add     esi,8
        add     edi,8
        sub     ecx,8
        ja      L0

이와 같은 아이디어를 가지고 MMX레지스터를 모두 활용하여 루프를 64번 언롤한 memcpy는 다음과 같다.

THRESHOLD EQU 96        ; 본문 참조
; void *memcpy(void *dst, void *src, size_t n)
memcpy  PROC C
        push    edi
        mov     edi,[esp+8]     ; dst
        mov     eax,edi         ; return value
        push    esi
        mov     esi,[esp+16]    ; src
        mov     edx,[esp+20]    ; n
        cmp     edx,THRESHOLD
        jb      L1
        mov     ecx,edi
        neg     ecx
        and     ecx,7
        sub     edx,ecx
    rep movsb
L0:     movq    mm0,[esi]
        movq    mm1,[esi+8]
        movq    mm2,[esi+16]
        movq    mm3,[esi+24]
        movq    mm4,[esi+32]
        movq    mm5,[esi+40]
        movq    mm6,[esi+48]
        movq    mm7,[esi+56]
        add     esi,64
        movq    [edi],mm0
        movq    [edi+8],mm1
        movq    [edi+16],mm2
        movq    [edi+24],mm3
        movq    [edi+32],mm4
        movq    [edi+40],mm5
        movq    [edi+48],mm6
        movq    [edi+56],mm7
        add     edi,64
        sub     edx,64
        ja      L0
        emms
        and     edx,63
L1:     mov     ecx,edx
        and     edx,3
        shr     ecx,2
    rep movsd
        mov     ecx,edx
    rep movsb
        pop     esi
        pop     edi
        ret
memcpy  ENDP

지난번의 구현에 비해 달라진 부분은 빨간 글자로 쓰여진 부분이다. 달라진 부분중 맨 처음 나타나는 부분은, MMX명령을 이용한 복사가 효율적인 지점을 결정하는 것이다. 이는 THRESHOLD라는 매크로 상수로 미리 지정했는데, 이 값은 CPU와 메모리의 특성에 의존한다. 예컨대, 위의 구현에서는 96바이트 이상을 복사하면 MMX명령을 써서 복사하고, 그렇지 않으면 아주 간단한 방법으로 복사를 하도록 하고 있다. 96이라는 값은 이 코드를 시험한 컴퓨터에서 MMX명령을 쓴 루프가 지난번의 구현보다 빨라지는 지점을 실험을 통해 알아내어 적어준 것이다. 다시 말하지만, 이 값은 시스템마다 다르다.

두번째로 바뀐 부분은 주소를 8바이트 경계로 정렬하도록 하는 것이다. 이번에는 주소의 8의 보수의 마지막자리를 구하는 작업인데, 2의 보수를 사용하는 인텔계통의 CPU에서는 단 한줄만 바꿈으로서 해결이 된다.

마지막으로, 주 루프는 아주 단순한 MMX복사 명령들이다. 8개의 MMX 레지스터를 가득채워서 64번 언롤링하는 효과를 얻고 있다. 주 루프를 빠져 나와서는 인텔이 설명하는대로 반드시 emms명령을 한번 실행해주고, 아직 남아있는 복사할 양을 계산해주는 것으로 변경된 부분이 끝난다.

이번 구현에서 주의해야 할 사항은 다음과 같다.

위의 구현은 대용량 복사가 자주 있는 경우에 적절하다. 만일 복사하는 양이 거의 항상 THRESHOLD값보다 작다면, 지난번의 구현에 오히려 불필요한 검사 작업만 더해져서 더 느릴 뿐이다.
언롤링을 무조건 많이 하는 것이 좋은 것은 아니다. 위의 구현은 MMX레지스터를 최대한 활용했지만, 그 결과 주 루프의 크기가 73바이트가 되었다. MMX 초기 CPU의 경우에는 CPU 내부의 코드캐쉬가 이것을 다 수용할 수 없어서 루프를 매번 읽어와서 해독하고 실행하게 된다. 그렇게 되면, 언롤링을 덜하고 주 루프의 크기를 줄이는게 오히려 속도 향상에 도움이 되기도 한다. 결론적으로, 가장 좋은 언롤링의 정도는 CPU와 메모리의 영향을 받으므로, 시스템마다 다르게 조정이 되어야 한다.

memcpy 구현 연재 목록

[3] MMX 이용