rep movsd

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

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

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

L0:     movsb
        dec     ecx
        jnz     L0

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

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

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

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

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

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

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

지난 번의 간단한 memcpy는 유용성이 제한됨을 이미 말한바 있다. 이것을 좀더 유용하게 만드는 방안으로 고려할만한 것이 메모리 주소 정렬이다.

인텔계통의 32비트 CPU는 메모리를 4바이트 단위로 접근한다. (4바이트 단위라는 표현 대신 DWORD단위라는 표현이 더 익숙할 수도 있다.) 예컨대, 0x1234번지에서 4바이트를 읽을 때에는 0x1234번지부터 0x1237번지까지 한번 접근해서 4바이트를 읽어들인다. 한편, 0x1235번지에서 4바이트를 읽을 때에는 0x1235번지부터 0x1237번지까지 접근해서 3바이트를 읽고, 0x1238번지에 접근해서 1바이트를 읽는다. 같은 양의 데이타를 읽을 때, 메모리 접근 횟수가 많아지면 속도가 느려지는 것은 자명하다. 메모리로 자료를 쓸때에도 마찬가지 현상이 일어난다.

따라서, 자료를 읽어들이는 주소와 쓰는 주소를 4바이트 단위로 정렬하면, memcpy의 속도가 개선될 여지가 있다. 그런데, 두개의 주소가 동시에 정렬되지 않는 경우가 종종 발생한다. 예컨대,

memcpy(p, p+1, 10);

과거에는 쓰는 주소를 정렬하는 것을 당연한 최적화로 받아들였다. 특히, WC메모리를 활용할 수 없는 오래된 CPU의 경우에는, 메모리로부터 읽을 때보다 메모리로 쓸 때에 주소를 정렬하는 것이 속도증진에 도움이 되었다. 하지만, 요즘의 CPU들의 경우에는 반드시 그렇지만은 않다. 그러므로, 어떤 주소를 정렬하는지가 더 나은가 하는 것은 자기가 사용하는 CPU에서 속도를 측정해봐야 결론을 내릴 수 있다.

쓰는 주소를 정렬하는 고전적인 경우를 가정하고 memcpy를 구현해보면 다음과 같다.

; 주소정렬을 고려한 memcpy
; void *memcpy(void *dst, void *src, size_t n)
memcpy  PROC C
        push    edi
        mov     edi,[esp+4+4]   ; dst
        mov     eax,edi         ; return value
        push    esi
        mov     esi,[esp+8+8]   ; src
        mov     edx,[esp+8+12]  ; n
        ; dst 주소 정렬.
        ; src를 정렬하려면 esi를 쓰면 된다.
        ; 본문 참조.
        mov     ecx,edi
        neg     ecx
        and     ecx,3
        sub     edx,ecx         ; 아주 짧으면?
        jbe     L0              ; 그러면 그냥 rep movsb
    rep movsb
        mov     ecx,edx
        and     edx,3
        shr     ecx,2
        ; 정렬된 주소로 복사.
    rep movsd
L0:     add     ecx,edx
    rep movsb
        pop     esi
        pop     edi
        ret
memcpy  ENDP

지난번의 코드와 달라진 부분은 빨간 글자로 표시된 부분이다. 새로 추가된 부분은 주소를 정렬하기 위해 미리 복사하는 부분이고, 두번째의 바뀐 부분은 rep movsd의 실행결과로 ecx의 값이 0이 되는 것을 고려하면 지난번의 mov ecx,edx와 동일한 역할을 하는 것을 쉽게 알 수 있다.

주소를 정렬하기 위해 미리 복사해야 하는 양은 정의상 현재 주소의 4의 보수의 마지막 자리이다. 2의 보수를 구하는 것과 같은 방법으로 NOT연산후에 1 증가시키는 방법으로 구할 수 있으며, 2의 보수로 음수를 표현하는 인텔 CPU에서는 편리하게 neg명령 써서 한번에 해결할 수 있다.

이미 다 아는 바와 같이, memcpy는 메모리 영역을 복사하는 표준 C 함수이다. C 수준에서 가장 간단하게 그 아이디어를 표현하자면, 이렇게 쓸 수 있다.

void *
memcpy(void *dst, void *src, size_t n)
{
        char *d = dst, *s = src;
        while (n--)
                *d++ = *s++;
        return dst;
}

; x86에서 가장 간단한 memcpy
; 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     ecx,[esp+20]    ; n
    rep movsb
        pop     esi
        pop     edi
        ret
memcpy  ENDP

; 약간 더 빠른 memcpy
; 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     ecx,[esp+20]    ; n
        mov     edx,ecx
        shr     ecx,2
        and     edx,3
    rep movsd
        mov     ecx,edx
    rep movsb
        pop     esi
        pop     edi
        ret
memcpy  ENDP

펜티엄 프로 이후의 CPU를 대상으로, 배정도 실수의 부호를 구하도록 변형한 부호함수.
단정도 부호함수와의 차이는 -0.0을 점검하는 부분에 명령 하나가 더 추가되었다는 것.
펜티엄 프로 이후에 쓸 수 있는 명령을 써서 훨씬 짧게 구현되었다.

dsignum proc
    mov eax,[esp+8]
    cdq
    lea edx,[2*edx+1]
    add eax,eax  ; check -0.0
    or  eax,[esp+4]
    cmovne eax,edx
    ret
dsignum endp

몇년전 프로그래밍 포럼에 만들었던 글타래에 적었던 코드. 그 글타래 자체는 다른 사람의 글에서 요청 비슷하게 한 것을 보고 열었었다. 내 스스로 쓸 일이 있을 것이라고는 생각을 하지는 못했다. 그런데, 최근에 다루는 문제를 푸는데 부호만 알면 되는 경우가 있을 줄이야! 내가 쓴 것을 내가 검색하는 어처구니 없음은 말할 것도 없고...

어처구니 없는 일을 다시 하지 않기 위해 적어두자.

입력: 단정도 부동 소수점 상수.
출력: 입력 값이 양수이면 1, 음수이면 -1, 0 이면 0.
대상: 인텔 32비트 CPU
제한 사항: 조건부 분기를 쓰지 말 것.

; int signum(float x)
; return value in eax
signum proc
    mov eax,[esp+4]
    cdq
    cmp eax,1
    sbb edx,1
    adc edx,1
    ; handle -0.0
    add eax,eax
    neg eax
    sbb eax,eax
    and eax,edx
    ret
signum endp