2장 - 기본으로 돌아가기

조엘 온 소프트웨어 

사람들이 저지르는 가장 큰 실수중 몇 가지는 최저층에서 벌어지는 몇 가지 단순한 동작원리를 자세히 알지 못하거나 아예 잘못 알고 있기 때문에 생긴다고 생각한다.

"궁전을 멋지게 지었는데 기초공사가 형편 없었다."

C에서 문자열이 동작하는 방법을 기억해보자.

 C문자열은 값이 0인 널(null) 문자로 끝나는 몇 바이트를 포함한다. 이 방식에는 다음과 같은 두 가지 명백한 문제점이 눈에 들어온다.

1. 널 문자를 찾아서 문자열 끝까지 가보기 전에는 끝을 알아내는 방법이 없다.

2. 문자열 내부에는 어떤 0값도 포함할 수 없으므로, JPEG 그림과 같은 비정형 이진 자료 Binary Large OBject(BLOB)를 C 문자열 내부에 저장할 수 없다.

어떻게 C 문자열을 이런 방식으로 사용하게 되었을까?

 이유는 유닉스와 C프로그래밍 언어를 고안했을 무렵 사용한 PDP-7 마이크로프로세서 때문이다. PDP-7은 ASCIZ 문자열 타입을 지원하는데, ASCIZ에는 '끝이 영(Z)인 ASCII'라는 의미가 있다.

참고 * Assembler 지시자는 '.으로 시작한다.

.asciz "string"...

.asciz 은 .ascii와 같으나 각각의 문자열에는 0의 값을 가지는 한바이트가 따 라온다. .asciz의 "z"은 "zero"를 의미한다.

ASCIZ가 단순히 문자열을 저장하는 유일한 길인것인가? 물론 아니다. 오히려 ASCIZ는 문자열을 저장하는 최악의 방법 중 하나 이다. 실전에 쓰는 프로그램, API, 운영체제, 클래스 라이브러리를 위해서는 다른 모든 코드를 오염시키는 ASCIZ 문자열을 반드시 피해야 한다. 왜 그럴까?

문자열 하나를 다른 문자열에 덧붙이는 함수인 strcat을 통해 알아보자.

void strcat( char* dest, char* src )

{

while(*dest) dest++;

while(*dest++ = *src++);

}

코드를 조금만 살펴보면 여기서 무엇을 하는지 알 수 있다.

첫째. 문자열에서 널 문자를 찾아간다. 종결자를 찾아내면, 

둘째. 문자열을 돌아 다니며, 한번에 글자 하나씩을 복사해서 첫번째 문자열 뒤에 붙인다.

이런 문자열  처리와 결합 방법은 커닝헌과 리치 시절(C의 아버지)에는 충분했을지 모르지만, 한 가지 문제점이 있다. 여러 사람 이름을  문자열 하나에 이어 붙인다고 생각해보자.

char bigString[1000]; /* 얼마나 할당해야 할지 알 수 없음... */

bigString[0] = '\0';

strcat(bigString, "John", ");

strcat(bigString, "Paul", ");

strcat(bigString, "George", ");

strcat(bigString, "Joel", ");

코드도 깔끔하고, 잘 동작할것 같이 보이지 않는가?

그렇다면 성능 측면에선 어떻게 생각 하는가? 생각처럼 빠르다고 생각하는가? 자료가 늘어나도 재대로 동작 할것인가?

문자열 백만 개를 덧붙인다면, 이런 방식이 과연 올바른 방식인가?

해당 코드는 러시아 페인트공 알고리즘을 사용하고 있다.

도로 차선 페인트 작업을 하는 러시아 페인트공이 있었습니다. 작업 첫날 페인트공은 페인트 통을 들고 나가서 300야드를 칠했습니다. 깜짝 놀란 책임자는 "정말 놀라운데! 정말 손놀림이 좋군."이라며, 페인트공에게 1코펙을 주었습니다. 다음날 페인트공은 겨우 150야드만 칠했습니다. 그래도 책임자는 "음, 어제 만큼은 못하지만, 여전히 손놀림이 좋아. 150야드도 대단하지."라며, 1코펙을 주었습니다. 그 다음날 페인트공은 30야드를 칠했습니다. 책임자는 "고작 30야드라니! 용납할 수 없네! 첫날에는 어떻게 오늘보다 10배를 넘게 칠한건가? 도대체 뭐가 문제야?"라고 윽박질렀습니다. 풀이 죽은 페인트공은 이렇게 말했습니다.  "저도 어쩔 수 없었습니다. 매일 페인트통에서 점점 멀어지니까요."                                                                      - 조엘 온 소프트웨어 中, 조엘 스폴스키

이 일화는 앞서 작성한 strcat을 사용할 때 어떤 문제가 발생하는지를 정확히 설명한다.

strcat의 첫 부분은 매번 빌어먹을 널 문자를 찾아 목적지 문자열을 찾아다녀야 하므로, strcat 함수는 필요 이상으로 느리며, 작업 규모가 커지면 성능이 현저히 떨어진다.

매일 사용하는 코드 대부분이 이런 문제점을 가지고 있다.

파일 시스템 대다수를 이런 방식으로 구현하는 바람에, 특정 디렉토리에 너무 많은 파일을 넣게되면 문제가 생긴다.

파일이 가득 차 있는 윈도우 휴지통을 열어보라. 휴지통을 여는 과정에서 시간이 제법 오래 걸리는데, 이는 휴지통에 들어있는 개수에 직접 비례하지는 않는다. 그 보다는 코드 어딘가에 러시아 페인트공 알고리즘이 존재하기 때문이다.

틀림없이 선형 효율을 보여야 하는 곳에서 n제공 효율이 나타난다면 어딘가에 숨어있을 러시아 페인트공을 의심해라.

이러한 문제점을 어덯게 고쳐야 할까?

똑똑한 C 프로그래머는 다음과 같이 mystrcat이라는 함수를 독자적으로 구현한다.

char* mystrcat( char* dest, char* src )

{

while(*dest) dest++;

while(*dest++ = *src++);

return --dest;

}

어떤 트릭을 사용했을까? 별다른 노력을 들이지 않고서도 새로 만들어진 더 긴 문자열의 끝을 가리키는 포인터를 반환한다.

이런방식으로 이 함수를 호출하는 함수는 문자열을 새로 읽지 않고서도 덧붙이는 장소를 결정할 수 있다.

물론 n제곱이 아니라 선형 효율을 발휘하므로, 대량으로 문자열을 결합할 경우 성능이 떨어지지는 않는다.

파스칼 설계자들은 이미 이런 문제점을 알고 있었으며, 문자열의 첫 바이트에 바이트 개수를 저장하는 방법으로 이를 해결했다.

이런 문자열을 파스칼 문자열이라고 한다. 파스칼 문자열은 0을 포함할 수 있으며, 널 문자로 끝나지 않는다.

바이트에 들어가는 가장 큰 숫자가 255이기에, 파스칼 문자열은 255바이트로 길이를 제한한다.

하지만 널 문자로 끝나지 않기 때문에 ASCIZ 문자열과 같은 크기만큼 기억공간을 차지 한다.

파스칼 문자열의 가장 멋진 특징은 문자열의 길이를 알아내기 위해 단순히 루프를 돌 필요가 없다는 점이다.

문자열 길이를 알아내는 작업은 전체 루프를 도는 대신 어셈블리 명령 하나로 족하며, 훨씬 빠른 성능을 보여준다.

 옛날에 사용했던 메킨토시 운영체제는 모든 곳에서 파스칼 문자열을 사용했었다. 메킨토시가 아닌 다른 플랫폼에서도 많은 C프로그래머가 속력문제로 파스칼 문자열을 사용하곤 했었다.

엑셀은 내부적으로 파스칼 문자열을 사용하므로(핵심 운영체제 API를 파스칼 스타일에 맞춰 만들었다.) 엑셀 곳곳에서 문자열을 255바이트로 제한한다. 이러한 구현 방식은 엑셀이 번개처럼 빠른 이유 중 하나가 되겠다.

오랫동안  파스칼 문자열을C 코드에 넣기 위해 아래처럼 코드를 작성해야 했다.

char* str = ""\006Hello!";

바이트를 하나씩 손으로 헤아려, 문자열의 첫 바이트에 수작업으로 집어 넣어야만 한다. 게으른 프로그래머는 이런 작업을 손쉽게 하기 위해 조금 느리게 돌아가는 프로그램을 작성한다.

char* str = "*Hello!";

str[0] = strlen(str) - 1;

이렇게 프로그램을 작성할 경우 파스칼 문자열을 따르지만, 

널 문자로 끝난다(컴파일러가 이렇게 만들었다.)는 사실에 주목해야 한다. 

다시 쟁점으로 돌아가서...

char bigString[1000]; /* 얼마나 할당해야 할지 알 수 없음 */

기억공간을 정확하게 할당하기 위해 도대체 얼마나 많은 바이트가 필요한지 계산해보자.

왜 기억공간을 정확하게 계산해야 할까?

이미 알려진 바와 같이, 똑똑한 해커라면 작성한 코드를 읽고난 후, 1000바이트만을 할당한 사실을 알아낸 후

1000 바이트로 할당된 기억공간을 1100 바이트 문자열을 덮어쓰는 방법으로 반환 주소를 바꿔놓아, 함수가 끝나고 돌아가는 시점에 해커가 작성한 코드를 수행하게 만들 수 있다.

특정 프로그램에 버퍼 오버플로에 취약하다고 말할 때 바로 이런 시나리오가 등장한다.

최근 마이크로소프트 아웃룩의 버그를 이용해 10대 청소년조차도 쉽게 해킹하는 불상사가 생기기 전에는, 버퍼 오버플로우가 해킹과 웜 바이러스 제작에 쓰이는 기본 기술이었다.

따라서 그런 실수를 저지르는 프로그래머들은 모두 멍청이라고 밖에 볼수 없다.

프로그래머는 얼마나 많은 기억공간을 할당해야 할지 계산해야만 한다.

그런데 실제 C로 이런 기억공간을 계산하는 작업은 결코 만만하지 않다.

비틀즈의 예를 다시 살펴보자.

char bigString[1000]; /* 얼마나 할당해야 할지 알 수 없음 */

char* p = bigString;

bigString[0] = '\0';

p = mystrcat(p, "John, ");

p = mystrcat(p, "Paul, ");

p = mystrcat(p, "George, ");

p = mystrcat(p, "Joel ");

얼마만큼 많은 기억공간을 할당해야 할까? 정석적으로 이를 풀어보자!

char* bigString;

int i = 0;

i = strlen("John, ");

+ strlen("Paul, ");

+ strlen("George, ");

+ strlen("Joel, ");

bigString = (char *) malloc (i + 1);

/* 널 문자를 위한 공간을 기억하시오! */

지금까지 단지 문자열 크기를 알아내기 위해 모든 문자열을 탐색해야 했다. 또한 덧붙이는 과정에서도 문자열을 탐색했다.

최소한 파스칼 문자열을 사용할 경우라면, strlen 연산은 빠르다. 

아마도 자동으로 기억공간을 다시 할당하는 strcat 버전을 작성할 수 있을 것이다.

여기에서 기억공간 할당자라는 "malloc"이 등장한다.

malloc의 동작원리를 살펴보자.

malloc의 본질은 사용 가능한 메모리 블록을 연결 리스트(linked list)로 길게 연결한 자유 체인(free chain) 이다.

malloc은 연결 리스트를 따라가며, 요청받은 메모리 양보다 큰 블록을 찾는다.

이렇게 찾은 블록을 2개로 쪼개서, 하나는 호출한 사용자에게 반환하고, 남은블록은 다시 연결리스트에 넣어둔다.

free를 호출할 때, free는 해제한 메모리를 자유 체인에 추가한다.

결국 자유 체인은 자그마한 조각으로 잘게 쪼개지므로, 큰 조각을 요청하면, 원하는 크기를 충족하는 조각이 없을 수도 있다.

이럴 경우 malloc은 timeout을 선언하게 되며, 자유 체인 주위를 샅샅이 훑어 조각을 정렬하고 인접한 작은 자유블록을

더 큰 블록으로 결합하는 작업을 하게 된다.

결국 이 모든 혼란의 끝은 malloc의 성능 특성이 결코 아주 빠르다고 볼 수 없으며(malloc은 항상 자유 체인을 돌아다닌다.),

정리하는 과정에서 종종 예측할 수 없을 정도로 지독하게 느려질 수 있다는 사실로 귀결된다.

덧붙여 말하면, 이런 현상은 가비지 컬렉션을 지원하는 시스템과 동일한 성능 특성이며, 시스템 성능 저하 원인이 가비지 컬렉션이라는 주장이 전적으로 옳지만은 않다는 놀라운 결론에 도달하게 된다.

비록 정도는 약하지만, 전형적인 malloc 구현을 따를 경우에도 가비지 컬렉션과 유사한 성능 저하 문제가 생긴다.

똑똑한 프로그래머는 항상 2배수로 메모리 블록을 할당하는 방법으로 잠재적인 혼란을 최소화 한다.

예를 들어 4바이트, 8바이트, 16바이트, 18446744073709551616 바이트와 같이 말이다.

레고 블록으로 집을 지어본 사람이라면 누구가 자연스럽게 공감하듯이, 이런 방법은 자유 체인에서 생기는 무시무시한 단편화를 상당히 줄여준다.

비록 이런 방법이 상당히 큰 공간을 낭비하는 듯 보일지는 몰라도, 항상 50%이하로 기억공간을 소비한다는 사실을 쉽게 확인할 수 있다.

따라서 프로그램이 요구하는 크기에 비해 2배를 넘지 않는 기억공간을 사용하기에, 그다지 큰 문제가 되지 않는다.  

목적지 버퍼를 자동으로 재할당하는 똑똑한 strcat 함수를 작성한다고 가정하자.

strcat이 항상 필요한 크기에 맞춰 정확하게 기억공간을 할당 할 필요가 있을까?

조엘의 선생님이자 조언자인 스탄 아이센스테트씨는 이렇게 말한다.

"realloc을 호출할 때, 항상 직전에 할당했던 두 배 크기로 기억공간을 늘여줘야 한다고 제안한다"

이런 방식을 따른다면 realloc 호출이 log(n)번을 초과할 필요가 전혀 없으며, 아주 큰 문자열을 처리하는 경우라도 그럴 듯한 성능 특성을 보여주면서 동시에 결코 50%를 초과해서 기억공간을 낭비 하지 않음을 보장한다.

이랬거나 저랬거나, 바이트 세계에서 인생은 점점 꼬여만 간다. C를 더이상 사용할 필요가 없다면 무척 기쁘겠으나, 펄, 자바, VB, XSLT와 같은 위대한 언어들이 있기에 이런 문제를 생각할 필요가 없다. 프로그래밍 언어가 이렇게 복잡한 작업을 알아서 해주기 때문이다. 

하지만 잘 돌아가던 배관 시설도 거실 중간에서 꼬여 버리는 일도 생기듯, String 클래스나 StringBuilder 클래스의 차이점을 따져 두 가지 중에서 무엇을 사용할지 생각해야 할 필요도 있다.

아직 컴파일러는 우리의 의도를 제대로 파악해서 러시아 페인트공 알고리즘을 사용하지 않아도 되게 도와줄 만큼 똑똑하지는 않기 때문이다.

관계형 데이터베이스에서 SELECT author FROM books를 어떻게 구현 할까?

관계형 데이터베이스(books 테이블) 내부에 들어있는 모든 열의 바이트 크기는 같으며, 모든 필드는 항상 열의 시작에서 고정 오프셋으로 찾을 수 있다.

예를 들어 books 테이블에서 각 레코드가 100바이트 크기를 차지하며 author 필드의 오프셋이 23이면, author 필드를 23, 123, 223, 323 바이트 위치에 저장한다. 이 질의 결과에서 다음 레코드로 옮기는 코드를 어떻게 구현할까? 아주 간단하다.

pointer += 100;

CPU 명령 하나로 끝나며, 무지 빠르다.

그렇다면 XML에 저장한 책 테이블을 살펴보자.

<? xml blah blah>

<books>

<book>

<title>UI Design for Programmers</title>

<author>Joel Spolsky</author>

</book>

<book>

<title>The Chop Suey Club</title>

<author>Bruce Weber</author>

</book>

</books>

퀴즈를 하나 내겠다. 여기서 다음 레코드로 옮기는 코드는 어떻게 될까?

이 시점에서, 뛰어난 프로그래머라면 XML을 램으로 올려 트리로 파싱해 놓은 다음, 이런 작업을 비교적 빨리 수행할 수 있다고 말할지도 모르겠다. 

여기서 CPU가 책에서 저자를 선택할 때(SQL문으로 따지면 SELECT author FROM books) 수행해야 하는 작업은 너무나도 따분하게 하품만 계속하게 만들 것이다.

모든 컴파일러 개발자가 알고 있는 바와 같이 구문 분석과 파싱 작업은 컴파일 과정에서 가장 느린 부분이다.

문자열과 관련한 작업을 대량으로 수행하고 메모리 할당을 대량으로 하기 때문에 무척 느린 것이다.

따라서 우리는 구문 해석과 파싱과 추상 구문 트리를 메모리에 만든다. 이런 작업은 모든 요소를 한번에 적제할 만큼 충분한 기억 공간이 있다고 가정한다.

관계형 데이터베이스를 사용할 경우 레코드에서 레코드로 이동하는 시간은 일정하며, 실제로 CPU 명령어 하나이다.

설계부터 이렇게 만든 것이다. 

메모리 사상 파일(memory mapped file)에 힘입어 실제로 사용하기를 원하는 디스크 페이지만을 로드하면 된다.

XML을 사용한다면, 미리 파싱을 해서 레코드에서  레코드로 이동하는 시간을 일정하게 만들지만, 처음 시작에 많은 시간을 소모한다. 미리 파싱을 하지 않을 경우라면 레코드에서 레코드로 이동하는 시간은 이동에 앞서 레코드 길이에 의존하게 되며, 여전히 CPU 명령어 수백 개를 수행하게 만든다.

위 설명은 좋은 성능이 필요하고 자료가 많다면, XML을 사용할 수 없다는 이야기로 들린다. 자료가 별로 많지 않거나 아주 빠르게 일을 수행할 필요가 없다면, XML은 좋은 형식이다.

자료와 속력 두 가지 모두를 만족시키려면, 파스칼 문자열 선두에 길이를 저장하는 방법처럼 파일 안 어디에 뭐가 있는지 쉽게 찾을 수 있는 힌트용으로 쓸 메타 자료를 XML에 추가로 저장하는 방법으로 자료를 파싱하고  탐색할 필요가 없게 만들어야 한다.

그러나 이럴 경우 당연히 워드프로세서를 사용해서 파일을 수정할 수 없다.

이런 수정 작업은 메타 자료에 치명타를 가하며, 더 이상 호환성을 보장하는 진짜 XML이 아니기 때문이다.

이 글을 통해 독자가 무엇가를 배웠거나 다시 생각해볼 기회가 되었으면 한다.

strcat과 malloc이 실제로 어떻게 움직이는지와 같은, 전산과 신입생이 지루해할 만한 사항을 살펴봄으로써 당신이 XML과 같은 기술을 다룰 때, 최상위 전략과 아키텍처 결정에 활용할 수 있는 무기를 여러분 손에 쥐어드리고 싶다.

몇 가지 숙제를 내겠다.

트랜스메타 칩이 항상 굼벵이처럼 기어가는 이유에 대해 생각해보라. 

또한 HTML의 기본 TABLE을 위한 규격 명세를 너무나도 형편없이 설계한 탓에, 모뎀 사용자의 웹 페이지에서는 큰 테이블이 늦게 뜨는 이유를 생각해 보라.

하나더, COM이 너무나도 빠르지만, 프로세스 경계를 가로지를 때는 그렇지 못한 이유를 생각해보라.

이런 문제는 어떨까? NT 개발자들이 화면 드라이버를 커널 공간에서 사용자 공간으로 이동한 이유는 무엇일까?

지금까지 바이트를 놓고 생각했다.

모두 아키텍처와 전략에서 논하는 상위 단계 결정 사항에 영향을 미친다.

전산과 신입생은 CPU부터 시작해 C를 활용하는 데까지 차곡차곡  기초를 닦아야 한다.

솔직히 너무나도 많은 컴퓨터 관련 교육과정들이 자바가 가장 좋은 초보자용 언어라고 선전하는 현실에 질려 버렸다.

흔히 자바는 쉽고, 따분한 문자열이나 malloc과 같은 골칫덩어리를 다루는 과정에서 혼란을 겪지 않으며, 아주 큰 프로그램 모듈로 나눠서 만들 수 있는 근사한 객체지향 프로그래밍 기법을 배울 수 있다는 화려한 이유들이 따라 나온다.

하지만 여기에서는 교육적인 재앙이 기다리고 있다.

졸업생들은 하향 평준화돼 러시아 페인트공 알고리즘을 여기저기에 만들어내며, 심지어 자신의 잘못을 인식조차 못할 것이다.

펄 스크립트에서 이런 사실을 결코 볼 수 없을지라도, (물론 어렵지만) 기본적으로 문자열이 무엇인지 아주 깊은 단계에서 이해하지 못하기 때문이다.

다른이들이 뭔가를 잘 하도록 가르치길 원한다면, 기초부터 시작해야 한다.