[c언어] 러시아 페인트공 알고리즘

기본으로 돌아가기

우리는 기본에 충실해야 한다. 학교에서 기본을 가르칠 때 당장 필요없다고 "이딴거 배워서 뭐하냐?? 사회나가면 다 쓸모 없다." 라고 한다면 그 사람은 그 분야의 대부분을 놓친 것이다. 전공이 직업과 상관 없다면 모르지만 일단 비슷한 계열의 직업이라면 학교다닐 때 기본에 충실해야 한다. (그리고 일단 데려와라 한대 맞고 시작해야겠다. =_=;;;)

1 + 1 도 못 하는 사람에게 "사회나가면 1 X 3 이라는 것이 있다더라. 1 + 1 같은 쓰잘데기 없는 거 공부하지 말고 1 X 3 이나 2 X 3 을 공부해라."라고 말한다면 얼마나 웃기겠는가?? 곱셈은 덧셈의 성질을 이용해서 만들어진 것이다. 덧셈을 모르고 곱셈만 한다면 곱셈은 할 수는 있을 것이다. 하지만 곱셈뿐이다. 왜 이렇게 되는지, 문제가 발생했을 때는 어떻게 해결해야 하는지 모를 것이다. 학교에서 곱셈을 가르쳐 줄 수도 있을지 모른다. 하지만 어차피 곱셈은 사회에 나가면 배울 것이라면, 혹은 경력이 쌓여 자연적으로 배우는 것이라면 굳이 학교에서 가르칠 필요가 있을까?? 학교는 학문을 연구하는 곳이다. 왜 곱셈은 안 가르쳐 주냐고 하는 사람이 있다면 다시 한번 생각해 봐라. 지금 자신이 있어야 할 곳이 학교가 아닌 사회가 아닌지...

아는 사람이 해준 이야기이다. 자기 팀에 팀장과 자기 2명이다. 어느날 문제가 발생해서 봤더니 두 대의 서버가 도매인 문제로 오류가 발생하는 것 같았다. 팀장에게 도매인 문제인 것 같다고 했더니 팀장이 도매인이 뭐냐고 했다고 한다. 음... 머라 말을 해야할지... 개발팀 팀장이 과연 맞긴 한건지... 그리고 또 이런 일도 있었다고 한다. 보안상 서버는 모든 포트를 막아 놓고 웹서비스를 위해 80포트만 열어 놓은 상태이다. 어떤 서비스를 위해 링크를 거는데 암만해도 안 보인다는 것이다. 역시나 우리의 팀장... 이번에도 실망시키지 않았다. 소스에 80 포트가 아닌 다른 포트로 링크 걸고는 혼자 쇼했다고 한다. 회사에 몇년을 있었을텐데 80 포트 이외의 포트가 막혀 있는 것을 몰랐을까...

기본에 충실해라. 일단 기본으로 돌아가자...
아래 내용은 조엘 온 소프트웨어 (유쾌한 오프라인 블로그)에 있는 내용이다. 약간의 프로그래밍의 전문적인 지식을 요하는 내용이다.





C언어에서의 문자열은 값이 0인 null문자로 끝나는 몇 바이트를 포함한다. 이는 두가지 명백한 문제점이 있다.
1. 널 문자가 나올 때 찾아보기 전에는 끝을 알 수 없다.
2. 문자열에는 0값을 포함할 수 없으므로, JPEG 그림 같은 Binary Large OBject(BLOB)를 문자열 내부에 저장할 수 없다.

문자열 하나를 다를 문자열에 덧붙이는 함수인 strcat을 구현해 보자.

void strcat(char * dest, char * src)
{
while(*dest) dest++;
while(*dest++ = *src++);
}

잘 보면 문제점이 보인다. 첫번째 문자열에서 널문자를 찾아간 뒤 두번째 문자열을 뒤에 붙인다. 언뜻 보기에는 괜찮아 보이지만 아래와 같은 코드를 실행하면 문제가 될 수 있다.

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에서도 똑같이 일어나고 있는 것이다. 문자열을 붙일 때 마다 널문자를 찾아서 헤매고 다니다 보니 필요 이상으로 느려지고 성능이 떨어진다. 똑똑한 프로그래머라면 mystrcat라는 함수를 독자적으로 구현할 것이다.

char * mystrcat(char * dest, char * src)
{
while(*dest) dest++;
while(*dest++ = *src++);
return --dest;
}

이건 간단한 트릭이다. 이제 페인트공이 페인트 통을 일 끝나는 곳에 놓고 퇴근을 한다. 리턴값으로 만들어진 문자열 끝부분을 주는 것이다. 이렇게 하면 널문자를 찾아 끝까지 헤매는 일은 줄어들 것이다. 대량으로 문자열을 넣어도 성능이 떨어지지는 않을 것이다.

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 ");

하지만 이 코드는 불행히도 1000바이트의 문자만 저장할 수 있다. 처음에는 충분할 것 같아서 정한 것이 나중에는 부족하게 될 수도 있다. 또, 똑똑한 해커라면 이 1000바이트 공간에 1100바이트 문자열을 덧붙이는 방법을 찾아내서 덮어씌울지도 모른다. 이런 것을 토대로 함수 스택 프레임을 덮어써서 반환 주소를 원하는 주소로 바꾸어 놓아 함수가 끝나고 돌아가는 시점에 해커가 작성한 코드를 실행하게 할 수 있다. 특정 프로그램이 버퍼 오버플로우에 취약하다고 말할 때 바로 이런 시나리오가 등장하는 것이다.
그럼 우찌할꼬~

char * bigString;
int i = 0;
i = strlen("John, ")
+ strlen("Paul, ")
+ strlen("Gerge, ")
+ strlen("Joel ");
bigString = (char *) malloc(i + 1);
/* 널문자 1바이트... */
... (위의 문자열 붙이는 코드 생략) ...

이건 문자열 개수를 세는 strlen이 나온다. 이놈도 널문자를 만날 때 까지 문자를 세겠지만 별 수 있나... 하지만 여기서의 문제는 strlen이 아니다. 바로 malloc이다. malloc의 본질은 사용 가능한 메모리 블럭을 linked list로 길게 연결한 free chain이다. malloc은 linked list를 따라가다 요청받은 메모리 양보다 클 블럭을 찾아서 2개로 쪼갠다. 하나는 호출한 사용자에게 주고 남은 나머지는 다시 free chain에 붙이게 된다. 결국 free chain은 작은 조각으로 쪼개지므로, 큰 조각을 요청하면 원하는 크기를 충족하는 조각이 없을 수도 있다. 이럴 경우 malloc은 타임아웃을 선언한 다음에 free chain주위를 샅샅이 뒤져서 조각을 정렬하고 인접한 작은 블럭을 더 큭 블럭으로 결합한다. 결국 종종 예측할 수 없을 정도로 느려질 수 있다는 사실이다. 이러한 현상은 garbage collection을 지원하는 시스템과 동일한 성능 특성이며, 시스템 성능 저하 원인이 garbage collection이라는 주장이 전적으로 옳지만은 않다는 놀라운 결록이 도달한다. 비록 정도는 약하지만, 전형적인 malloc 구현을 따를 경우에도 garbage collection과 유사한 성능 저하 문제가 생기니 말이다.
똑똑한 프로그래머는 항상 2의 배수로 블럭을 할당하는 방법으로 잠재적인 혼란을 최소화한다. 예를 들어, 4바이트, 8바이트, 18446744073709551616바이트와 같이 말이다. 이런 방법으로 free chain에서 생기는 단편화를 상당히 줄여준다. 비록 이런 방법이 상당히 큰 공간을 낭비하는 듯이 보일지는 몰라도, 항상 50% 이하로 기억공간을 소비한다는 사실을 쉽게 확일할 수 있다. 따라서 프로그램이 요구하는 크기에 비해 2배를 넘지 않는 기억공간을 사용하기에, 그라지 큰 문제가 되지 않는다.

(중략)

많은 컴퓨터 관련 교육과정들이 자바가 가장 좋은 초보자용 언어라고 선전한다. 흔히 자바는 쉽고, 따분한 문자열이나 malloc과 같은 골칫덩어리를 다루는 과정에서 혼란을 겪지 않으며, 아주 큰 프로그램을 모듈로 나눠서 만들 수 있는 근사한 객체지향 프로그램밍 기법을 배울 수 있다는 화려한 이유들이 따라 나온다. 흐지만 여기에는 교육적인 재앙이 기다리고 있다. 졸업생들은 하향 평준화돼 러시아 페인트공 알고리즘을 여기저기에 만들어내며, 심지어 자신의 잘못을 인식조차 못할 것이다.

- 조엔 온 소프트웨어 (유쾌한 오프라인 블로그)
2장 기본으로 돌아가기 中
원문 : Back to Basics

+ 위의 책 내용의 strcat이나 malloc같은 것을 세세하게 알라는 것이 아니다. 개발자는 이러한 것이 있다는 것을 알고는 다음에 써먹을 수만 있으면 돼는 것이다. (이러한 것이 있다는 것을 아는 것이 기본이 아닐까??) 지금같은 정보의 홍수 속에서 이 많은 정보들을 모두 알 수는 없는 법이다. 안다라는 지식의 개념이 knowhow였던 시대는 지났다. knowwhere의 시대라고 하지 않는가?? 어떻게 하는지 아는 것은 대략적인 것만 알면 된다. 실제로 많이 사용한다면 저절로 알게 돼니 말이다. 어디에 있어서 어떻게 찾아야 하는지를 아는 것이 지금 이 시대의 진정한 지식이자 경력인 것이다.

+ 전산에서 가장 중요한 것은 OS, 자료구조, 컴파일러, 알고리즘, 네트워크 등 눈에 보이지 않는 것들이다. OS가 어떻게 동작하는지 알아야 내가 만든 것이 어떻게 동작하는지 알고, 컴파일러가 어떻게 동작하는지 알아야 내가 원하는 결과를 가진 프로그램이 탄생하는 것이다.

출처 : http://entireboy.egloos.com