rep movsd

지난번의 메모리 사용 분석의 예에 이어, 이번에는 메모리 정리 유틸리티를 만들 수 있는 핵심 코드를 가지고 또다른 유틸리티를 하나 만들어 본다. 어렵게 생각할 것 없이 자기 취향이나 요구사항에 맞게 이 핵심코드를 포장하면 바로 완성이다.

원리

NT계통의 윈도우즈에서 사용되는 메모리 최적화 프로그램의 원리는 매우 단순하다. 즉, 현재 시스템에 돌아가고 있는 프로세스마다 SetProcessWorkingSetSize() 또는 EmptyWorkingSet()를 호출하는 것이다. 이 단순한 원리를 어떻게 사용자에게 제공하는가에 따라 CleanMem같은 모양을 가질 수도 있고, Minimem이나 Beautiful Memory같은 모양이 나오기도 한다.

위에서 한줄로 쓴 원리를 코드로 표현할 때에는, 현재 시스템에 돌아가고 있는 프로세스를 찾는 방식에 따라 몇가지 구현이 가능하다. 예를 들어, 윈도우즈 SDK에 포함된 예제중에 하나는 프로세스 목록을 얻기 위해 레지스트리를 읽어와서 그 내용을 해독한다. 다른 방법으로는 toolhelp32로 분류되는 API를 이용하는 방법이 있다. 이 방법을 이용해서 메모리 최적화 프로그램의 원리를 C 코드로 표현하면 다음과 같다.

HANDLE hProcess, hSnap;
PROCESSENTRY32 pe32;

hSnap = CreateToolhelp32Snapshot(TH32CS_SNAPPROCESS, 0);
if (hSnap == INVALID_HANDLE_VALUE)
	return;

pe32.dwSize = sizeof(PROCESSENTRY32);
if (!Process32First(hSnap, &pe32)) {
	CloseHandle(hSnap);
	return;
}

do {
	hProcess = OpenProcess(PROCESS_ALL_ACCESS, FALSE,
				pe32.th32ProcessID);
	if (hProcess) {
		EmptyWorkingSet(hProcess);
		CloseHandle(hProcess);
	}
} while (Process32Next(hSnap, &pe32));
CloseHandle(hSnap);

요구사항

이미 있는 구현은 위에서 언급한 세가지 말고도 아주 많다. 아무리 그렇게 많아도 원리는 모두 똑같은 것이니 아무거나 자기 취향에 맞는 것을 골라서 사용하면 된다. 여기서 다시 만드는 이유는 다음과 같은 요구사항을 만족시키는 기존의 구현을 찾지 못했기 때문이다.

• 간단한 원리를 실행하기 위해 배보다 배꼽이 더 커서는 안된다. 비주얼 베이직 런타임이나 .NET 프레임웍을 따로 설치하는건 딱 질색.
• 실행 파일 자체가 뭔지 모를 도구로 압축되어 있는 것은 안된다. 이런 것은 도리어 메모리를 더 많이 소비하게 만들고 많은 경우에 보안사고로 연결된다. 바이러스 감시 프로그램이 압축된 실행파일을 경고하는 것은 다 이유가 있다.
• 설정파일을 메모장으로 언제든지 읽어서 쉽게 설정을 바꿀 수 있어야 한다. 레지스트리 깊숙히 설정을 숨겨놓는 것은 설정할 때에도 곤란하고 나중에 삭제할 때에도 골치 아프다.
• 한번 설치하면 일일이 신경쓰지 않고 잊어버려도 상관없어야 한다. 위의 작동 원리는 NT계통의 윈도우즈에서만 돌아가니까 NT 서비스로 돌아가면 좋겠다. 서비스로 돌아갈거면 자체적으로 사용하는 메모리 양도 적어야 한다.
• 메모리 정리하지 않을 프로그램을 지정할 수 있어야 한다. 어떤 프로그램은 이미 자체적으로 메모리를 정리하고 있으므로 따로 해줄 필요가 없다. 불필요하게 건드리면 오히려 그 프로그램의 실행만 방해한다.

설치

압축파일을 받아 적절한 곳에 압축을 풀면 다음과 같은 두개의 파일이 나온다.

wsmin.exe는 NT서비스 실행파일이며 윈도우즈2000이상의 시스템에서만 작동한다. 설치를 완료하기 위해서는 NT서비스 데이타베이스에 등록해야 한다. 이는 명령행에서 다음과 같이 입력하면 된다. (관리자 권한이 필요하다.)

wsmin.exe /i

설치가 완료되면 시스템 시동때마다 자동으로 시작하게 기본값이 설정되어 있다. 이것을 바꾸려면 시작-제어판-관리도구-서비스를 열어서 Working Set Minimizer라고 된 것을 찾아 바꾸어주면 된다. (고수들은 명령행에서 services.msc라고 치는 것을 좋아한다.)

설정

설정파일은 wsmin.ini이며, 없어도 상관없다. 설정파일이 없으면 밑에서 설명하는 기본값들을 가지고 서비스가 작동한다. 만일 설정파일이 있다면 실행파일과 같은 디렉토리에 있어야 한다. 설정을 바꾸는 방법은 메모장(notepad.exe)같은 편집기로 열어서 이하에서 설명하는 항목을 편집하고 저장하면 된다. 변경한 설정을 적용하기 위해서는 wsmin.exe를 다시 시작한다. 이를 위해서는 시작-제어판-관리도구-서비스를 열어서 Working Set Minimizer라고 된 것을 찾아 "다시 시작"을 누르면 된다.

설정할 수 있는 것들 중 중요한 것은 메모리 정리하는 시간 간격과 정리하지 않을 파일들의 목록이다. 그외에도 심각한 오류를 기록할 로그파일 이름과 부팅이 느린 시스템에서 처음 메모리 정리까지 기다릴 시간을 설정할 수 있다.

메모리를 정리하는 시간간격은 1분부터 480분(= 8시간)사이의 값을 분 단위로 적어준다. 기본값은 30분이다.

[Settings]
Interval=60

그런데 이 프로그램은 시스템이 시작할때 자동으로 실행하는 것을 상정하고 있기 때문에, 프로그램 실행 이후 최초로 메모리 정리 작업을 하기까지 일정시간을 기다린다. 이는 부팅이 느린 시스템에서 다른 서비스들과 드라이버들을 올리기 전에 섣불리 메모리 정리를 시도하다가 시스템을 불안정하게 만드는 것을 방지하기 위해서 정한 값이다. 이 값도 역시 1분부터 480분 사이의 값을 분 단위로 설정할 수 있으며, 기본값은 1분이다.

[Settings]
InitialWait=3

메모리 정리에서 제외할 실행파일 이름은 [Ignore]섹션에 한줄에 하나씩 적어준다. 예를 들어, 서비스 관리자에는 손대지 않으려면

[Ignore]
services.exe

[Ignore]
C:\WINDOWS\system32\services.exe

삭제

이 프로그램을 삭제하려면, 우선 서비스를 종료하고 명령행에서 다음과 같이 입력하여 서비스 데이타베이스에서 삭제한다.

wsmin.exe /u

덧붙임

이미 언급한 바와 같이, working set을 줄이는 메모리 최적화는 메모리 할당/해제를 제대로 하지 않는 그저 그런 품질의 프로그램을 많이 실행할 때에 큰 효과가 있다. 그런 프로그램은 아예 사용하지 않는다면, 그 어떤 메모리 최적화 프로그램도 소용이 없다. 이런 경우에는 메모리 최적화 프로그램을 사용하는 만큼 메모리를 손해보는 것 밖에 없다.

게임은 메모리 정리 프로그램을 써봤자 소용없는 경우다. 가만 생각해보면 게임의 실행속도를 높이기 위해 굉장히 큰 캐쉬를 사용하는게 너무나 당연해서, 그 틈에 메모리 낭비가 있을 법도 하다. 그런데도 메모리 정리가 소용없는 이유는 게임을 실행하는 중이라면 그 게임이 실질적으로 유일한 작업이나 다름없기 때문이다. 바꾸어 말하면, 게임을 하는 중이라면 워드프로세서, 웹브라우저, 기타 등등 여러개의 작업이 게임과 함께 동시에 돌아갈 가능성이 별로 없다. 이런 상황에서는 메모리 정리를 해봐야 게임만 느려지고 다른 프로그램을 위해 메모리를 확보하는 효과도 없다.

파일

다운로드 전에: 이 프로그램을 실행함으로써 발생할지도 모르는 어떠한 불상사에 대해서도 제작자는 책임지지 않는다. (이는 더도 아니고 덜도 아니고 딱 마이크로소프트 수준의 사용허가 문구이다.)

wsmin.zip은 아래 표에 적힌 파일들이 담긴 압축파일이다. 압축을 풀고 NT서비스 데이타베이스에 등록해야 설치가 완료되며, 이에 관해서는 위의 설명을 참조하면 된다. 이런 작업이 귀찮거나 어려운 사람들은 wsminsetup.exe를 받아서 실행하면 설치가 된다. 이것은 똑같은 내용물을 Inno Setup을 이용하여 설치파일로 만든 것이다.

단순 압축 파일:

wsmin.zip

  설치 실행 파일:

wsminsetup.exe

Cholesky분해는 양정부호행렬을 하삼각행렬과 그 전치행렬의 곱으로 표현하는 것이다라는 내용은 기초 선형대수학 교과서에 나오는 얘기다. 수학과 담을 쌓고 사는 사람이 아니면 늦어도 학부 3학년에는 이것을 배운다. 수학적 중요성은 잠깐 잊어버리더라도 계산상으로 Cholesky분해는 꽤 중요하다. 우선 LU분해에 걸리는 시간의 절반밖에 안걸린다. 게다가, 수치상 안정적이어서 다른 알고리즘에 비해 계산과정상 누적되는 오차의 영향을 덜 받는다. 단점도 물론 있다. 자세한 것은 선형대수 교과서나 수치해석 교과서를 보면 잘 나온다.

주요한 사용 예를 들자면: 최적화 문제의 답을 수치해석적으로 구해야만 하는 경우에 목적함수가 터무니없이 이상하게 생기지 않았으면 가중최소제곱법을 반복해서 답을 구할 수 있다. 이때 가중최소제곱법의 답을 구할때 Cholesky분해를 이용한다. (물론, 다른 방법으로 가중최소제곱법의 답을 구할 수도 있다. 예를 들어 MINPACK은 QR분해를 이용한다.)

실제로 계산하는 법은 의외로 간단하다. 이미 구현되어 제공되는 함수들도 많다. 예를들어 LAPACK의 DPOTRF는 배정도실수 행렬을 다루는 Fortran서브루틴이다. 같은 기능을 하는 함수가 NAG와 IMSL에도 물론 있다. 그런데, 이론적으로 Choleksy분해는 양반정부호행렬까지 확장될 수 있다. 그러나, 대부분의 라이브러리의 Cholesky분해 함수들은 양정부호행렬만 다룬다. 양반정부호행렬을 다루는 구현이 이미 1968년에 공개되었다는 점을 고려하면 이런 상황이 좀 의아하다. 내가 아는한 IMSL의 imsl_f_lin_sol_nonnegdef()만이 양반정부호행렬을 다루는 C 구현이다.

이하의 구현은 위에 링크된 1968년에 공개된 Fortran 구현을 C로 다시 구현하면서 Farebrother and Berry의 버그수정과 그것을 고려한 Barrett and Healy의 개선을 포함한 것이다. Healy의 원래 구현은 입력행렬과 출력행렬이 같은 주소를 가리켜도 되었는데, Barrett and Healy의 개선점을 포함하면서 그것이 허용되지 않게 되었다. 양정부호행렬만 분해한다면 이 함수는 LAPACK의 DPPTRF와 같은 기능을 한다.

함수 원형

int cholesky(double A[], int n, double U[], int *nullity)

A (입력)

양반정부호 행렬. 하삼각행렬부분만 1차원배열로 저장한다. 즉 A는 n*(n+1)/2개의 원소를 A₁₁, A₂₁, A₂₂, A₃₁, ... 순으로 저장한 1차원 배열.

n (입력)

A의 차원. 즉, 수학적으로 A는 n×n행렬.

U (출력)

Cholesky분해의 결과로 나오는 하삼각행렬. 역시 1차원 배열로 저장된다.

nullity (출력)

A의 영공간의 차원. NULL이면 출력이 없다. NULL을 전달했으나 이후에 영공간의 차원을 알고자 한다면, 대각원소들 중에 0.0인 것들의 갯수를 세면 된다.

0

작업 성공

-1

비정상적인 매개변수: n <= 0이거나 A와 U가 같은 주소를 가리키는 경우.

1 ... n

A가 양반정부호행렬이 아니며, 리턴값에 해당하는 행에서 처음으로 양반정부호행렬이 아님이 발견됨

구현
수식자체와 양정부호행렬임을 검사하는 방법은 아무 선형대수 교과서나 수치해석 교과서를 봐도 잘 설명되어 있다. 위에 링크된 논문들과 그에 따른 구현에서 중요한 것은 언제 어떻게 선형종속임을 결정하는가 하는 부분이다. (약간 줄 수가 많아 접어놓음.) C 코드를 보려면 클릭

#include <math.h>
#define eta 1.0e-9 /* Healy (1968)에서 설정된 값 */

int
cholesky(double A[], int n, double U[], int *nullity)
{
    int     i, j, k, l, m, icol, irow;
    double  w, x;

    if (n <= 0 || A == U)
	return -1;

    if (nullity)
	*nullity = 0;

    icol = j = k = 0;
    do {
	x = eta * eta * A[k + icol];
	irow = 0, l = 0;
	do {
	    w = A[k];
	    for (i = irow, m = j; i > 0; --i)
		w -= U[l++] * U[m++];
	    if (irow == icol)
		break;
	    if (U[l] == 0.0) {
		if (w * w > fabs(x * A[l]))
		    return k + 1;
		U[k] = 0.0;
	    }
	    else
		U[k] = w / U[l];
	    ++l, ++k;
	} while (++irow <= icol);

	if (fabs(w) > fabs(eta * A[k])) {
	    if (w < 0.0)
		return k + 1;
	    U[k] = sqrt(w);
	}
	else {
	    U[k] = 0.0;
	    if (nullity)
		++(*nullity);
	}
	++k, ++icol;
	j += icol;
    } while (icol < n);
    return 0;
}

더 해볼만한 것
원 논문의 바로 다음에 이어지는 논문에는 이 함수를 이용해서 양(반)정부호행렬의 (일반화)역행렬을 구하는 함수가 공개되어 있다. 같은 기능을 하는 것을 스스로 만들어쓰려면 BLAS의 DTPSV를 이용하면 된다.

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비트 초보 시절의 기억을 되새겨 보았다.

• 2의 보수를 사용하는 기계에서, 정수 i의 맨 아래쪽 1 비트(1로 세트된 비트 중 LSB에 제일 가까운 비트)를 0으로 만들려면 C 수식으로 i & (i-1)를 쓴다. 부호없는 정수로 생각하면, 1을 빼는 연산이 항상 맨 아래 비트를 0으로 만들고, 그보다 더 LSB쪽에 있는 비트는 1로 만든다는 것을 쉽게 알 수 있다.

  이 방법을 사용한 예는 Ken Thompson이 Unix에 썼다고 하는 전설이 있는 비트 수 세기 루프이다.

  /* i에 비트 수를 세고자 하는 값이 들어있다. */
  bitcount = 0;
  while (i != 0) {
      bitcount++;
      i &= i - 1;
  }

  이 코드는 2의 보수를 사용하는 모든 기계에서 작동한다.

• 반대로, 2의 보수를 사용하는 기계에서 정수 i의 맨 아래쪽 1 비트만 남기고 다 지우려면, C 수식으로 i & -i를 쓴다. 이것도 2의 보수방식으로 부호를 바꾸는 연산이 NOT연산후에 1을 증가시킨다는 것을 기억하면 이 코드를 이해할 수 있다.

  이 방법을 응용하면, 어떤 정수가 2의 누승인지 쉽게 알아낼 수 있다. 이진법에서 2의 누승은 단 하나의 비트만 1이고 나머지 비트는 모두 0이다. 그러므로, 이렇게 하면 빨리 알아낼 수 있다:

  if ((i & -i) == i) { /* 2의 누승 */ }

  이 역시 머신워드 크기에 관계없이 2의 보수를 사용하는 모든 기계에서 작동한다.

• 맨 아래쪽 1 비트가 몇번째 비트인지 알아내는 것은 루프를 돌아도 알아낼 수 있지만, 인텔계열 386이상의 CPU에서는 bsf명령을 쓰면 한번에 알 수 있다. BSD계통의 Unix에는 같은 목적으로 ffs()라는 함수가 제공된다.