rep movsd

부호 없는 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 프로그램을 작성할 때 비트 패턴을 뒤집는 경우.

CVS는 많은 사람들이 사용하고 있고, 사용하지 않더라도 무엇인지 한번쯤은 들어봤을만한 도구이다. 윈도우즈에 특화하려는 의도로 시작된 CVSNT도 있지만, 나의 경우에는 실행파일 하나만 있으면 설치할 필요도 없이 간편하게 모든 CVS 기능을 사용할 수 있는 원조 CVS를 선호한다. 윈도우즈용 실행파일도 FSF의 FTP사이트에서 제공된다. 그런데, 이 실행파일을 사용하면, 로컬 저장소를 지정할때, 드라이브를 지정할 수 없는 경우가 있다. 예컨대,

cvs -d :local:c:\cvs init

cvs -d :local:c:\cvs co CVSROOT

이를 해결하려면, 소스코드를 받아서 약간 고쳐서 컴파일하면 된다. 패치는 다음과 같다. (아래에서 다운로드 받을 수 있다.)

--- lib/canonicalize.c.old	Fri Jun 10 15:30:20 2005
+++ lib/canonicalize.c	Sun Jan 06 09:34:40 2008
@@ -20,6 +20,12 @@
 # include <config.h>
 #endif
 
+#ifdef WIN32
+/* need the next to exclude winsock headers */
+#define WIN32_LEAN_AND_MEAN
+#include <windows.h>
+#endif
+
 #include "canonicalize.h"
 
 #ifdef STDC_HEADERS
@@ -127,13 +133,44 @@
   return resolved;
 
 # else
+#  ifdef WIN32
+	/* Use GetFullPathName() with existence check. */
+	char namebuf[_MAX_PATH+1];
+	DWORD n;
+	char *p, *resolved;
+
+	n = GetFullPathName(name, sizeof(namebuf), namebuf, &p);
+	if (n == 0)
+		return NULL;
+	/* n is strlen() or required size, so, we have malloc() size. */
+	if ((resolved = xmalloc(n + 1)) == NULL)
+		return NULL;
+	/* if name buf was not enough, GetFullPathName() again. */
+	if (n > sizeof(namebuf)) {	/* get it directly to `resolved' */
+		if ((n = GetFullPathName(name, n + 1, resolved, &p)) == 0) {
+			free(resolved);
+			return NULL;
+		}
+	}
+	else {
+	    memcpy(resolved, namebuf, n + 1);	/* copy including NUL */
+	}
+	/* check if it exists. */
+	if (GetFileAttributes(resolved) == -1) {
+		free(resolved);
+		return NULL;
+	}
+	return resolved;
+#  else
 
   return canonicalize_filename_mode (name, CAN_EXISTING);
 
+#  endif
 # endif /* !HAVE_RESOLVEPATH */
 }
 #endif /* !HAVE_CANONICALIZE_FILE_NAME */
 
+#ifndef WIN32
 /* Return the canonical absolute name of file NAME.  A canonical name
    does not contain any `.', `..' components nor any repeated file name
    separators ('/') or symlinks.  Whether components must exist
@@ -316,3 +353,4 @@
   free (rname);
   return NULL;
 }
+#endif

필요한 도구들

• C 컴파일러 - 없으면 Visual C++ Express를 받아서 설치하면 된다.
• patch - 없으면 여기에서 배포하는 것을 설치하면 된다.

명령행 요약

unzip cvs-1.12.13a.zip
cd cvs-1.12.13a
patch -p0 < cvs.patch
nmake -f cvsnt.mak

패치 파일

invalid-file

최적화에 있어서 가장 중요한 것은 역시 실제 측정이다. 아무리 좋아보이는 코드라도 실제로는 그다지 성능이 나오지 않을 수도 있기때문이다. 지난번의 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의 기본 예측 알고리즘에 의하면, 루프를 도는 동안 네번에 한번은 반드시 예측이 틀린다. 이 두가지를 고려하면, 루프의 크기를 적절한 수준으로 조정해 손실을 최소화하는 지점을 찾아야 한다.

대용량의 복사에 적당한 MMX명령을 사용한 memcpy의 구현보다도 더 빨리 하는 방법은 없는가라는 질문은 어쩌면 너무나도 당연하다. 이를 위해 펜티엄3에 처음으로 등장한 SSE명령을 이용하면 가능성이 보인다.

한가지 가능성은, 펜티엄3에서 SSE와 함께 등장한 정수명령을 사용하는 것이다. 그중에서 중요한 두가지는 movntq명령과 prefetchnta명령이다. 이들은 캐쉬의 활용도를 최적화함으로써 성능향상에 기여하도록 고안된 명령들이다. 이들을 이용해 지난번의 구현을 변경하면 다음과 같다.

THRESHOLD EQU 96
PREFETCHDIST EQU 128    ; 본문참조
; 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:     prefetchnta [esi+PREFETCHDIST]
        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
        movntq  [edi],mm0
        movntq  [edi+8],mm1
        movntq  [edi+16],mm2
        movntq  [edi+24],mm3
        movntq  [edi+32],mm4
        movntq  [edi+40],mm5
        movntq  [edi+48],mm6
        movntq  [edi+56],mm7
        add     edi,64
        sub     edx,64
        ja      L0
        emms
        ; sfence
        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

변경된 사항은 아주 단순하다. 우선, 주 루프의 선두에 prefetchnta를 사용하여 미리 앞으로 읽을 메모리를 캐쉬로 끌어들인다. 그리고 메모리를 쓸 때에는 캐쉬를 거치지 않고 바로 쓰도록 한다. PREFETCHDIST는 미리 읽어올 메모리의 주소를 결정하는 매크로 상수인데, 이것을 최적의 값으로 결정하는 방법은 상당히 복잡하다. 인텔의 최적화 설명서는 부록을 할애해서 원리를 개략적으로 설명하고, 정확한 값을 구하기 위해서는 자사의 제품을 구매사용할 것을 권하고 있다. 여기서 주어진 128이란 값은 대충 몇가지 값을 써보고 그중 나아보이는 것을 정한 것이며, 최적의 값은 아니다.

현재의 코드에서는 주석처리 되어 있지만, 여러개의 CPU를 장착한 고급시스템에서는 sfence를 사용해야 할 수도 있다. movntq는 WC메모리 타입에 맞추어 작동을 하는데, 각 CPU가 같은 메모리 영역을 다른 타입으로 보고 있다면, sfence없이는 그 내용의 일관성을 보장할 수 없기 때문이다. 경험상으로는 sfence가 없어도 아직까지 문제를 일으킨 적은 없었으나, 인텔이 사용설명서에 sfence를 사용하기를 강하게 권하므로 쉽게 무시하고 지나갈만한 것은 아니다.

펜티엄3의 새로운 명령들을 사용하여 구현한 memcpy는 두가지 커다란 문제점을 안고 있다. 첫째로, 인텔의 권고대로 sfence를 사용하는 경우에, sfence가 엄청나게 느리다는 것이다. 그래서, 상당히 큰 영역을 복사하는 경우가 아니면, sfence로 인한 손실이 커서 SSE를 사용하는 것이 간단한 rep movsd보다 느릴 가능성이 꽤 있다는 것이다. 둘째로, 경험상으로 보면 movntq는 시스템의 특성을 상당히 많이 탄다. 어떤 시스템에서는 이 명령이 매우 빠른 속도로 작동하는데, 다른 시스템에서는 MMX버전보다 형편없이 느리다. 다른 사람들은 movntq가 movq에 비해 느린 이유에 대한 설명도 제시하고 있고, 나름대로 설득력도 있어 보인다.

결론적으로, 펜티엄3에 추가된 명령을 이용한 memcpy는 빠르게 작동할 가능성이 있지만, 그에 못지않게 기존의 것보다 느려질 가능성도 크다. 그러므로, 이를 사용하기 전에는 반드시 속도측정을 먼저 해보아야 한다.