rep movsd

MMX 지원이 없는 고전 펜티엄에서 빠른 memcpy()를 구현하기 위해 다음과 같은 코드를 쓰던 적이 있었다.

L0:     fild    QWORD PTR [esi]
        fistp   QWORD PTR [edi]
        add     esi,8
        add     edi,8
        sub     ecx,8
        ja      L0

그런데, 정수를 FPU 레지스터로 읽어들이는 fild는 부동소수점 실수를 읽어들이는 fld보다 느리다. 메모리로 쓰는 fistp 역시 fstp보다 느리다. 고전 펜티엄에서는 그 차이가 두드러진다. 어셈블리 초보의 입장에서 보면, 64비트 정수나 배정도 실수나 모두 64비트 크기를 가지는 자료이니, 조금 더 빠른 fld/fstp의 조합을 쓰는 것이 당연하게 보인다. 그런 생각을 실제로 벤치마크로 보여주는 코드도 웹에 떠돌아 다닌다.

링크된 벤치마크 코드를 돌려봐도 잘만 돌아가는데, 왜 이것이 초보나 저지르는 실수인가? 그것은, 코드자체에 있는 것이 아니라, 부동소수점 자료의 표현때문이다. fld/fstp를 쓰는 memcpy() 구현은 보통때에는 별 이상없이 작동하지만, 복사하는 내용이 특정한 값이면 프로그램 실행이 멎어버리는 경우가 있다. 인텔 매뉴얼 1권의 용어로는, SNaN 값이 복사대상이면 그런 일이 벌어진다. (엄밀하게 말하자면, 실행이 멈출지 아닐지는 프로그램에서 예외처리를 어떻게 하는가와 운영체제의 예외처리 정책에 따른다. 프로그램에서 FPU 예외처리를 하지 않고 운영체제의 기본 예외처리를 따른다면, 운영체제의 정책에 따라 실행이 멎을 수도 있고 계속 실행할 수도 있다. 프로그램에서 FPU 예외처리를 하면, 실행은 계속 할 수 있겠지만, NaN 값을 FPU 레지스터로 읽어들이는 경우에는 보통 실수 값을 읽을 때보다 한참 느리게 작동한다. 그러므로, 예외발생/예외처리/NaN처리의 과정을 거치면 엄청난 속도상의 손실이 발생한다.)

이것을 직접 확인해 볼 수 있는 예로서, 위의 링크에 있는 파일을 받아서 begin() 함수를 다음과 같이 약간 고쳐서 실행해 볼 수 있다. (빨간 글씨로 되어 있는 부분을 추가한다.)

void begin( LPBYTE mem1, LPBYTE mem2, int size, const char* text ) {
	memset(mem1,0x55,size);
	memset(mem2,0xff,size); // 0xAA를 0xff로 바꾸고 다음 두 줄을 추가.
	for (int i = 0; i < size; i += 8)
	    mem2[i+6] = 0xf0;
	printf(text);
}

인텔 32비트 CPU에서 조건부 분기 없이 32비트 정수의 절대값 구하기는 이미 잘 알려진 코드다. 32비트 운영체제가 대세가 되면서 한동안 어셈블리 코딩을 하지 않던 나에게 다시 인텔 어셈블리어 코딩을 하도록 끌어들인 그 코드. 조건부 분기하는 것보다 빠른 것은 물론 더 짧다.

; 입력:  eax = 절대값을 구할 정수
; 출력:  eax = 입력값의 절대값
; 기타 사용 레지스터:  edx
    cdq
    xor eax,edx
    sub eax,edx

초보를 위한 설명:

• CDQ명령으로 EAX 레지스터의 부호를 EDX로 복사하면, EDX는 -1이거나 0이다.
• XOR연산을 0에 대해 하면, 바뀌는 것 없다. 2의 보수로 표현한 -1에 대해 하면 NOT연산과 같다.
• SUB명령에 인수로 0을 주면, 바뀌는 것 없다. -1을 주면 INC명령과 같다.

어느정도 인텔 어셈블리 코딩을 해온 사람이라면 이 코드를 하도 많이 써서 관용구로 외우고 있을 것이다. 매크로로 만들어 놓은 사람도 분명 있을 것이고... 게다가, 앞뒤로 한줄씩만 더하면 바로 C표준함수 labs()이다. 물론, 이 코드를 내가 본 것이 벌써 10년전이니까, 요즘 컴파일러들은 labs()를 이렇게 바로 인라인할 것이라고 추측된다.

누군가 어셈블리어를 검색해서 찾아온 것을 보고 나서 32비트 초보 시절의 기억을 되새겨 보았다.

부호 없는 32비트 정수에서 1로 세트된 비트의 수를 세어서 돌려준다. 예컨대, 15를 받으면, 4개의 비트가 세트되어 있으니 4를 돌려준다.

누가 갑자기 와서 이 함수를 당장 만들어내라고 하면 제일 먼저 생각해낼 만한 것은 LSB가 1이면 1을 더하고 오른쪽으로 쉬프트를 하는 루프를 떠올릴 것이다. 다른 방법으로는 1바이트 안의 비트 수를 적어 놓은 테이블을 만들어 놓고 4번 루프를 돌면서 각 바이트 안의 비트 수를 더하는 방법도 있다.

그런데, 메모리 접근하는데 시간이 오래 걸리고, 루프를 32번 도는 것도 참을 수 없이 느리다면, 이런 방법이 있다: 1비트로 표현한 2진수를 더하면 그 최대값은 2비트로 표현이 가능하다는 것에 주목하면 이 원리를 쉽게 이해할 수 있다. 즉, 맨 처음에는 홀수번째 비트와 짝수번째 비트를 쪼개서 더한다. 그 다음에는 2비트 묶음 단위로 더하고, 그 다음에는 니블 단위로, 바이트 단위로, 16비트 단위로 더해주면 원하는 답이 나온다. 이 원리를 인텔 32비트 어셈블리어로 직역하면 다음과 같다.

; unsigned bitcount(uint32_t a)
bitcount PROC
        mov     eax,[esp+4]
        ; 비트 단위 더하기
        mov     edx,eax
        and     eax,55555555h  ; 홀수 비트
        xor     edx,eax        ; 짝수 비트
        shr     edx,1          ; 짝수 비트를 하나 밀어서
        add     eax,edx        ; 더해주면 16개의 부분합이 나온다.
        ; 2비트 단위 더하기
        mov     edx,eax
        and     eax,33333333h
        xor     edx,eax
        shr     edx,2
        add     eax,edx
        ; 니블 단위 더하기
        mov     edx,eax
        and     eax,0f0f0f0fh
        xor     edx,eax
        shr     edx,4
        add     eax,edx
        ; 바이트 단위 더하기
        mov     edx,eax
        and     eax,00ff00ffh
        xor     edx,eax
        shr     edx,8
        add     eax,edx
        ; 16비트 단위 더하기
        mov     edx,eax
        and     eax,0000ffffh
        xor     edx,eax
        shr     edx,16
        add     eax,edx
        ret
bitcount ENDP

그런데, 이 코드를 유심히 살펴보면 이렇게 많이 쓸 필요가 없다는 것을 곧 알게 된다. 불필요한 부분을 제거하고 좀더 간결하게 짜면 다음과 같다.

; unsigned bitcount(uint32_t a)
bitcount PROC
        mov     eax,[esp+4]
        mov     edx,eax
        shr     eax,1
        and     eax,55555555h
        sub     edx,eax
        mov     ecx,33333333h
        mov     eax,edx
        shr     edx,2
        and     eax,ecx
        and     edx,ecx
        add     eax,edx
        mov     edx,eax
        shr     eax,4
        add     eax,edx
        and     eax,0f0f0f0fh
        imul    eax,01010101h
        shr     eax,24
        ret
bitcount ENDP

이 함수가 사용되는 경우: 작은 클래스의 객체들을 많이 생성하여 new를 스스로 만들어 쓰는 경우, 불필요한 낭비를 줄이기 위해 블록 헤더를 따로 두지 않고 사용중인 메모리 블록을 비트맵으로 관리한다. 이럴때, 객체를 몇개나 생성했는지를 알려면 비트맵의 비트의 수를 세면 된다.

똑같은 원리가 파일시스템에도 사용된다. 파일저장블록(FAT용어로는 클러스터)의 비트맵을 이용해서 사용된 블록을 기록하고 관리하는 파일시스템에서 디스크 사용량을 알려고 한다면, 같은 방식으로 빠르게 알 수 있다. (NTFS가 이런 방식을 쓴다는 얘기를 들었다. 소스코드를 본 적이 없어서 정말인지는 모른다.)

부호없는 32비트 정수를 받아서 그 비트 패턴을 뒤집어 출력한다. LSB부터 MSB로 각 비트를 0부터 31까지 번호를 붙이면, 0번 비트와 31번 비트를 서로 바꾸고, 1번 비트와 30번 비트를 서로 바꾸고, ..., 15번 비트와 16번 비트를 바꾸어 돌려준다.

실제 구현은, 우선 bswap을 이용해서 바이트 단위의 순서를 뒤집어 놓은 다음에 각 바이트 안에서 비트패턴을 뒤집는 방식을 사용한다. 각 바이트 안에서는, 우선 니블 순서를 뒤집고, 각 니블 안에서 인접한 2비트씩의 순서를 뒤집고, 마지막으로 2비트 안에서 인접한 비트의 순서를 뒤집는다. 마치 퀵소트 알고리즘처럼 두개의 그룹씩 순서를 바꾸어간다고 생각하면 코드를 이해하기 쉽다.

; uint32_t bitreverse(uint32_t a)
bitreverse PROC
        mov     eax,[esp+4]
        bswap   eax
        mov     ecx,eax
        and     eax,0f0f0f0fh
        xor     ecx,eax
        rol     eax,8
        or      eax,ecx
        mov     ecx,eax
        and     eax,33333333h
        xor     ecx,eax
        rol     eax,4
        or      eax,ecx
        mov     ecx,eax
        and     eax,55555555h
        xor     ecx,eax
        rol     eax,2
        or      eax,ecx
        ror     eax,7
        ret
bitreverse ENDP

bswap명령은 486이상에서 사용이 가능한 명령이므로 386에서 사용하려면 같은 효과를 내는 코드를 써야한다. 예를들어,

    xchg    ah,al
    ror     eax,16
    xchg    ah,al

대표적인 용도: 누구나 한번쯤은 숙제로 짜야하는 FFT 프로그램을 작성할 때 비트 패턴을 뒤집는 경우.

최적화에 있어서 가장 중요한 것은 역시 실제 측정이다. 아무리 좋아보이는 코드라도 실제로는 그다지 성능이 나오지 않을 수도 있기때문이다. 지난번의 movq와 movntq의 비교가 이미 살펴본 예이다. memcpy의 구현에 관련해서 실제로 시간을 측정해 비교해 볼만한 사항이 몇가지 있다.

조건부 분기

CPU의 파이프라인이 길어지면서 점점 더 조건부 분기 예측이 틀렸을때의 손실이 커진다. 물론, 요즘 나오는 CPU는 펜티엄같이 어처구니 없는 예측을 하지는 않아서, 예측이 맞는 경우가 더 많게 구성되어 있다. 그러므로 예측이 틀려도 그 손실보다는 맞는 경우의 이득의 합이 더 크게 되는 경우가 많다.

지금까지의 구현에서는 조건부 분기 예측을 놓고 도박을 하는 것보다는 차라리 확실하게 알려진 소요시간을 믿자라는 암묵적인 원칙이 있었다. 예컨대, 단순한 구현에서

        mov     edx,ecx
        shr     ecx,2
        and     edx,3
    rep movsd
        mov     ecx,edx
    rep movsb

그러나, 조건부 분기 예측의 성능이 좋다면, ecx의 값을 점검하여 그 값이 0일때에는 복사명령을 건너뛰게 해서 속도를 증진시킬 수도 있을 것이다. 실제로 그러한지는 측정을 해서 비교해봐야 알 것이다.

루프 정렬

인텔의 최적화 설명서는 루프의 선두를 16바이트 경계에 정렬할 것을 권한다. 지금까지의 구현에서 MMX와 SSE명령을 사용한 루프는 함수의 선두가 16바이트 경계에 정렬되어 있으면 자연스럽게 루프의 선두도 16바이트 경계에 정렬되게 짜여있다. 그런데, 이 코드에 조건부 분기를 더하여 불필요한 복사주소 정렬을 건너뛰게 한다면, 루프의 선두가 16바이트 경계에 정렬되지 않게된다. 그러할때에, 그것을 그대로 두고 실행하는 것이 더 빠른가 아니면 다시 align지시자를 이용해 16바이트 경계로 정렬되도록 강제하는 것이 더 빠른가는 측정을 통해 비교해봐야 알 수 있을 것이다.

루프 크기

이미 설명된 바이지만, 루프 언롤링은 조건부 분기의 수를 줄이는 대신 루프의 크기를 크게 한다. 이는 루프를 도는 동안 코드캐쉬의 활용도를 떨어지게 할 가능성이 있다. 한편, 이런 루프를 도는 동안에는 조건부 분기 예측이 틀리는 경우가 반드시 발생한다. 예컨대, 펜티엄2의 기본 예측 알고리즘에 의하면, 루프를 도는 동안 네번에 한번은 반드시 예측이 틀린다. 이 두가지를 고려하면, 루프의 크기를 적절한 수준으로 조정해 손실을 최소화하는 지점을 찾아야 한다.