. 버퍼의 자료구조

프로그램은 자료구조와 알고리즘으로 구성되는데 이 둘은 서로 긴밀한 연관을 맺고 있으며 또한 상호 보완적이다. 동일한 성능의 프로그램을 작성한다고 했을 때 자료구조가 간단하면 알고리즘이 복잡해져야 하고 반대로 자료구조가 복잡하면 알고리즘이 상대적으로 간단해져도 된다. 모든 프로그램은 표현하고자 하는 정보를 어떤 식으로 저장하고 관리할 것인지 자료구조를 먼저 설계한 후 자료구조에 맞게 알고리즘을 구현한다.

편집기가 처리하는 가장 중요한 데이터는 역시 편집 대상인 텍스트이다. 텍스트를 어떤 식으로 저장하고 관리할 것인가, 즉 버퍼의 설계 방식을 최우선적으로 결정해야 한다. 버퍼 설계는 편집기 제작의 첫 단추에 해당하는데 잘 설계해놓으면 코드 작성도 쉽고 기능을 확장하기에도 유리하다. 반면 잘못 설계하면 중간에 고치기 어려우며 낭패를 당할 수도 있으므로 처음부터 신중하게 선택해야 한다.

그래서 우선 편집기를 본격적으로 제작하기 전에 버퍼를 어떤 식으로 설계하는 것이 좋은지부터 면밀하게 검토해보도록 하자. 텍스트 데이터를 표현하기 위한 방법은 크게 두 가지 방식으로 나누어지는데 첫 번째는 디스크 기반이고 두 번째는 메모리 기반이다. 디스크 기반의 버퍼란 편집파일을 전부 읽어오지 않고 당장 필요한 부분만 읽어오는 방식인데 과거 메인 메모리가 크지 않았을 때 주로 사용한 방식이다. 메인 메모리가 4MB인 상황에서 1MB짜리 파일을 메모리로 읽어 들이면 25%의 메모리를 점유하는 셈이 되기 때문에 그럴 수가 없었다.

요즘은 메인 메모리가 넉넉한 데다가 메모리가 부족하면 운영체제가 알아서 디스크에 가상 메모리를 잡아주기 때문에 굳이 비효율적인 디스크 기반 방식을 사용할 필요가 없어졌다. 게다가 파일이 정말로 크다면 파일 매핑 객체를 사용하는 방법이 있으므로 디스크 기반은 아예 생각하지 않는 것이 좋다. 메모리를 기반으로 하는 버퍼는 다시 두 가지 방식으로 나누어진다.

단일 버퍼

전체 텍스트를 하나의 문자열 버퍼로 관리한다. 만약 4줄로 구성된 문서를 표현한다면 메모리상에 다음과 같이 기록될 것이다.

버퍼의 시작위치를 가리키는 포인터 변수 buf 하나만 선언하고 이 버퍼에 문서를 통째로 저장해두었다. 문서를 표현하는데 단일 버퍼 하나만 있으면 된다. 이 방법은 다음과 같은 장점이 있다.

 

보다시피 극단적으로 단순한 구조를 가지고 있기 때문에 관리할 필요가 거의 없다. 버퍼의 시작위치와 원하는 오프셋만 알면 문서를 자유롭게 조작할 수 있다.

이런 일차원적인 구조는 텍스트 파일의 디스크 이미지와 완전히 일치한다. 그래서 파일 입출력이 간단하며 읽는 즉시 문서를 보여 줄 수 있고 저장할 때도 buf 배열을 파일로 쓰기만 하면 된다. 또한 이 구조는 Win32의 메모리 맵 파일과도 호환되므로 대용량 파일을 메모리 맵 파일로 매핑한 후 사용하면 과다한 메모리 소모없이 큰 문서를 읽을 수 있다.

문서 자체를 기억하는 버퍼 외의 추가 정보가 필요치 않으며 문서의 용량과 거의 동일한 크기의 버퍼를 사용하므로 메모리의 낭비가 없다.

 

하지만 앞에서도 말했듯이 자료구조가 단순하면 알고리즘이 복잡해져야 한다. 단일 버퍼 방식은 그 단순함으로 인해 다음과 같은 단점을 가진다.

 

특정 위치를 찾는데 시간이 걸린다. 위 그림에서 네 번째 줄 가는 나그네를 찾으려면 버퍼의 처음부터 읽어가면서 개행문자 셋을 지난 후의 위치를 찾아야 한다. 문서가 크면 클수록, 찾는 줄이 뒤쪽에 있을수록 검색 속도는 더욱 느려질 것이다. 그러나 이 단점은 별도의 인덱스를 유지함으로써 해결할 수 있다.

삽입과 삭제가 느리다. 문서의 특정 위치에 문자를 삽입할 경우 삽입되는 위치 이후의 문자는 모두 뒤쪽으로 이동되어야 한다. 예를 들어 1M 크기의 문서가 있고 이 문서 중간에 글자 하나를 삽입한다고 해보자.

이 글자가 삽입될 공간을 중간에 만들어야 하므로 뒤쪽의 문자들이 삽입될 글자 길이만큼 이동되어야 한다. 삭제할 때는 반대로 뒤쪽 문자들을 앞쪽으로 복사해야 한다. 문서가 짧다면 그리 큰 문제가 아니겠지만 문서가 길어지면 글자 하나 삽입할 때마다 엄청난 메모리 이동이 필요하므로 효율적이지 못하다. 버퍼 하나가 문서 전체를 가지고 있으므로 이 구조에서는 어쩔 수 없는 문제다. 해결 방법이 전혀 없다.

줄단위 버퍼

이 방법은 문서 전체를 하나의 버퍼에 저장하는 것이 아니라 한 줄당 하나의 버퍼에 저장하는 것이다. , 문서 전체를 줄의 배열로 간주하고 각 버퍼에 한 줄씩 텍스트를 저장한다. 4줄짜리 문서를 예로 들면 다음과 같이 메모리에 입체적으로 표현될 것이다. 여기서 줄이라는 용어는 개행코드로 물리적으로 분리되어 있는 문단의 개념이다.

형태적으로 문서는 각 줄을 가리키는 포인터 배열로 표현된다. 또는 좀 더 삽입과 삭제에 유연함을 주고자 한다면 연결 리스트(Linked List)로 구현할 수도 있다. 이 방법은 단일 버퍼에 비해 좀 더 발전된 형태이며 다음과 같은 장점이 있다.

 

검색이 무척 빠르다. n번째 줄을 찾고 싶으면 buf[n]을 읽으면 되는데 배열의 첨자 연산은 고속으로 처리되기 때문에 거의 시간이 들지 않는다. 문서의 크기가 아무리 커도 검색 속도가 느려지는 법은 없다.

삽입 삭제도 비교할 수 없을 만큼 빠르며 문서 크기에도 거의 영향을 받지 않는다. 문서가 백만 줄이든 천만 줄이든 그 줄에 삽입하는 글자는 그 줄의 버퍼에만 영향을 미치기 때문에 대용량의 메모리 이동이 필요없다. 하지만 여러 줄을 한꺼번에 삽입, 삭제할 때는 포인터 배열을 조작해야 할 필요가 있다. 예를 들어 6번 줄을 통째로 삭제하면 7번 줄이 6번 줄이 되야 하고 그 이후의 줄들도 줄줄이 한 칸씩 위로 올라와야 한다. 그러나 포인터 배열 조작은 텍스트를 전혀 건드리지 않으므로 속도상 불리한 점이 별로 없으며 연결 리스트를 사용할 경우 배열 조작도 필요치 않다.

각 줄에 북마크나 줄번호 등의 부가 정보를 같이 저장할 수 있다. 한 줄에 대한 정보를 구조체로 작성하고 이 구조체에 원하는 정보를 멤버로 포함시키면 된다. 이렇게 되면 문서는 포인터 배열이 아니라 구조체 배열이 된다.

 

보다시피 단일 버퍼를 사용하는 방법에 비해서 여러 모로 장점이 많다. 하지만 구조가 약간 복잡해졌기 때문에 이로 인한 단점도 있다.

 

단일 버퍼를 사용하는 방법에 비해 메모리 소모가 많다. 각 줄의 텍스트 버퍼는 추가될 문자를 고려하여 약간의 여분을 주어 메모리를 할당해야 하므로 미사용 메모리 양이 많고 또 삽입 삭제가 잦을 시에 메모리 재할당이 빈번하게 이루어지므로 메모리의 단편화가 심해진다. 복잡한 구조의 대가로 인해 메모리는 많이 소모할 수밖에 없다.

텍스트 파일의 구조와는 다른 형태를 가지기 때문에 파일 입출력이 번거롭다. 파일을 읽은 후 화면에 출력하려면 먼저 각 줄을 분석해서 줄 버퍼에 메모리를 할당하고 텍스트를 복사하는 과정을 거쳐야 한다. 그래서 파일을 읽은 후 출력될 때까지 약간의 시간이 걸리는데 파일이 클수록 이 시간이 많이 걸린다. 저장할 때도 흩어져 있는 줄들을 모아 한 파일에 기록해야 하므로 역시 느리다.

이 단점이 별로 중요하지 않다고 생각할 수도 있겠지만 편집기를 텍스트 뷰어로 사용하는 사람에게는 치명적인 단점이다. 10MB 정도의 텍스트 파일을 읽고자 하는데 수십 초를 기다려야 한다면 누가 좋아하겠는가? 실제 발표되어 있는 상용 편집기들도 이 방법으로 작성된 것은 파일을 처음 읽어 들이는 속도가 굉장히 느리고 반응성이 좋지 않다. 물론 일단 읽은 후에는 빠른 속도로 편집할 수 있다.

구조가 복잡하기 때문에 관리가 다소 귀찮은 면이 있다. 문서를 편집하거나 이동, 복사, 붙여넣기를 할 때, 특히 줄끼리의 문자열 이동시 이것저것 해야 할 처리가 많다. 따라서 버그의 가능성도 훨씬 더 높고 개발중에 디버깅을 하기도 무척 번거롭다. 이는 곧 개발 비용이 많이 든다는 얘기와도 같다.

 

버퍼를 관리하는 두 가지 방법에 대해 알아 보았는데 물론 이 두 방법 외에도 파일 매핑 객체를 사용한다거나 하는 제 3의 방법들이 있을 수 있다. 하지만 다른 방법들도 이 두 방법의 변형이거나 조합 정도에 불과할 것이다.

, 그럼 이제 편집기를 만들기 전에 버퍼의 구조를 먼저 선택해야 한다. 이때 가장 우선적으로 고려되어야 할 사항은 삽입, 삭제 속도이다. 메모리 소모, 검색, 변환, 관리 등의 처리는 내부적으로 일어나는 일이므로 사용자가 그 차이를 느끼기 어려운데 반해 삽입, 삭제는 사용자의 키보드 조작에 의해 일어나는 일이므로 쉽게 체감된다. 문서가 조금 커졌다고 해서 타이프치는 속도를 못 따라온다면 그 편집기 누가 쓸려고 하겠는가?

앞에서 살펴본 바에 의하면 단일 버퍼 방법이 줄단위 버퍼 방법보다 삽입, 삭제에는 불리하다. 그렇다면 과연 얼마나 불리한지 간단한 예제를 만들어 테스트를 해보도록 하자. MemTest라는 이름으로 프로젝트를 만들고 다음 소스를 입력해보자.

 

#include <windows.h>

 

LRESULT CALLBACK WndProc(HWND,UINT,WPARAM,LPARAM);

HINSTANCE g_hInst;

HWND hWndMain;

LPCTSTR lpszClass=TEXT("MemTest");

 

int APIENTRY WinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance

       ,LPSTR lpszCmdParam,int nCmdShow)

{

     HWND hWnd;

     MSG Message;

     WNDCLASS WndClass;

     g_hInst=hInstance;

    

     WndClass.cbClsExtra=0;

     WndClass.cbWndExtra=0;

     WndClass.hbrBackground=(HBRUSH)(COLOR_WINDOW+1);

     WndClass.hCursor=LoadCursor(NULL,IDC_ARROW);

     WndClass.hIcon=LoadIcon(NULL,IDI_APPLICATION);

     WndClass.hInstance=hInstance;

     WndClass.lpfnWndProc=(WNDPROC)WndProc;

     WndClass.lpszClassName=lpszClass;

     WndClass.lpszMenuName=NULL;

     WndClass.style=CS_HREDRAW | CS_VREDRAW;

     RegisterClass(&WndClass);

 

     hWnd=CreateWindow(lpszClass,lpszClass,WS_OVERLAPPEDWINDOW,

          CW_USEDEFAULT,CW_USEDEFAULT,CW_USEDEFAULT,CW_USEDEFAULT,

          NULL,(HMENU)NULL,hInstance,NULL);

     ShowWindow(hWnd,nCmdShow);

     hWndMain=hWnd;

    

     while(GetMessage(&Message,0,0,0)) {

          TranslateMessage(&Message);

          DispatchMessage(&Message);

     }

     return (int)Message.wParam;

}

 

#include <stdio.h>

void MemTest()

{

     LARGE_INTEGER st,ed,freq;

     double gap;

     TCHAR Mes[256];

     TCHAR *buf;

     int i;

 

     buf=(TCHAR *)malloc(1048576*10);

     QueryPerformanceCounter(&st);

     for (i=0;i<10;i++) {

          memmove(buf,buf+1,1048576*10-1);

     }

     QueryPerformanceCounter(&ed);

     QueryPerformanceFrequency(&freq);

     gap=((double)(ed.QuadPart-st.QuadPart))/((double)freq.QuadPart);

     sprintf(Mes, "10MB 열번 이동 테스트에 %.4f초 경과했습니다.",gap);

 

     MessageBox(hWndMain,Mes,"속도 측정 결과",MB_OK);

     free(buf);

}

 

LRESULT CALLBACK WndProc(HWND hWnd,UINT iMessage,WPARAM wParam,LPARAM lParam)

{

     HDC hdc;

     PAINTSTRUCT ps;

     char Mes[]="마우스 왼쪽 버튼을 누르십시오";

 

     switch(iMessage) {

     case WM_LBUTTONDOWN:

          MemTest();

          return 0;

     case WM_PAINT:

          hdc=BeginPaint(hWnd, &ps);

          TextOut(hdc,10,10,Mes,lstrlen(Mes));

          EndPaint(hWnd, &ps);

          return 0;

     case WM_DESTROY:

          PostQuitMessage(0);

          return 0;

     }

     return(DefWindowProc(hWnd,iMessage,wParam,lParam));

}

 

마우스 왼쪽 버튼을 클릭하면 MemTest 함수를 호출하는데 이 함수는 10MB의 메모리를 이동시키는 동작을 10번 수행하고 경과 시간을 출력한다. 결국 100MB의 메모리를 이동시키는 작업을 하는 것과 동일하다. 실행 결과는 CPU, 메모리의 속도에 따라 달라지는데 나의 노트북(P3-600 시스템)에서 테스트해 본 결과 0.87초 정도가 걸렸다. 비교적 최신의 CPU에서 테스트해 본 결과는 0.19초로 훨씬 더 빨랐는데 그러고 보니 노트북을 업그레이드할 때가 된 것 같다.

대충 1초가 조금 안되는 시간이 걸렸는데 이 계산대로라면 1MB를 이동하는 데는 불과 0.01초도 안 걸린다는 얘기다. 100MB라면 사실 굉장히 큰 용량인데도 생각보다는 빠르다. 왜냐하면 memmove CPU가 하드웨어 차원에서 지원하는 명령이며 엄청나게 고속으로 동작하기 때문이다. 이 함수의 내부는 C 코드도 아니고 어셈블리 코드도 아니며 CPU가 바로 알아들을 수 있는 이진 기계어 코드를 바로 호출하도록 되어 있으며 그 속도가 감히 상상을 불허할 정도다. 최신의 CPU에서는 1초에 50억 개의 비트를 단 한 번에 이동시킬 수 있는 정도이니 그 속도가 어느 정도인지 감이 올 것이다.

10MB의 문서를 편집하고 있다면 0.1초가 걸리는데 이 정도면 느리다고 느껴질 것이고 50MB 편집시는 0.5초가 걸리므로 도저히 못쓸 프로그램이라고 생각할 것이다. 타이핑 속도가 빠른 사람은 평균 분당 600타 정도를 치므로 삽입 시간은 최소한 0.1초 미만이어야 한다. 보통 편집파일은 1MB 미만인 경우가 대부분이고 100KB 정도의 파일은 한 번 키보드를 칠 때마다 1/1000초를 소모하므로 이런 작은 파일을 편집할 때는 무시해도 될만한 시간이다.

두 방법은 각각의 장단점을 가지고 있는데 각 방법의 성능은 편집할 파일의 크기와 함수 관계를 가지고 있다. 파일이 커질수록 단일 버퍼 방법이 불리하며 작으면 오히려 줄단위 버퍼 방법이 더 번거롭다. 정확하게 측정을 해 본 것은 아니지만 편집파일의 크기와 두 방법의 성능은 대체로 다음과 같은 함수 관계를 이룰 것이다.

어떤 방법이나 파일 크기가 커지면 성능이 떨어지는 것은 어쩔 수 없는 일이고 다만 반비례 직선의 기울기가 다를 뿐이다. 이 그래프 상에서 두 방법이 동일한 성능을 내는 α점을 가정할 수 있는데 이 점의 위치는 어디쯤 될까? 아마 10MB~30MB 사이가 되지 않을까 생각되는데 이 점은 CPU가 더 빨라지면 점점 뒤로 이동하는 경향이 있다. 그리고 CPU는 확실히 빨라지고 있다.

여러 가지 분석과 검토를 한 결과 ApiEdit는 단일 버퍼 방법을 채택하기로 했다. 왜냐하면 무엇보다 논리가 간단하고 직관적이기 때문이다. 또한 실습을 위한 프로젝트에서 디버깅을 편하게 할 수 있어야 한다는 점도 고려되었다. 서식이 없는 텍스트 편집기라면 단일 버퍼를 선택하는 것이 탁월한 선택인 것 같다. ApiEdit가 실습을 위한 예제이기 때문에 이 방법을 선호하는 것은 아니며 실제 제품을 만든다 하더라도 단일 버퍼가 훨씬 더 좋은 방법이다.

논리가 간단해진다는 것은 코드가 덜 복잡해진다는 얘기가 되고 이는 곧 개발 비용을 감소시켜 개발 기간을 단축시키는 효과를 가져온다. 바꾸어 얘기하자면 동일한 비용을 들였을 때 줄단위 버퍼를 사용하는 방식보다는 더 많은 기능을 안정적으로 제공할 수 있다는 얘기다.

그러나 그렇다고 해서 줄단위 버퍼 방법이 좋지 않다는 뜻은 아니다. 좀 복잡해도 잘 구현해놓으면 확장성은 확실히 우수하다. 서식과 기타 복잡한 개체들이 포함되는 워드프로세서라면 당연히 줄단위 버퍼를 선택하는 것이 좋을 것이다.

지금까지 발표된 대부분의 편집기들은 줄단위 버퍼 방식으로 작성되어 있다. 왜냐하면 그런 편집기를 만들기 시작할 즈음에는 CPU 속도가 형편없었고 따라서 파일이 조금만 커져도 단일 버퍼 방식으로는 제 속도를 낼 수가 없었다. 하지만 ApiEdit는 늦게 만들어진 관계로 고성능 CPU를 믿고 과감하게 단일 버퍼 방식을 채택하였다.

이 선택이 옳았는지 아닌지는 최종 제품의 성능을 테스트해 봐야 알 수 있으며 오로지 결과로서 평가되어야 한다. 어쨌든 두 방식을 다 선택할 수는 없기 때문에 초기에 이런 어려운 결정을 내리지 않을 수 없으며 한 번 내린 신중한 결정에 대해서는 스스로 확신을 가지고 밀어 부치는 수밖에 없다.