다음은 조엘 온 소프트웨어 2장 관련 내용입니다.
C 언어 관련
C 문자열은 값이 \0, 널 문자(null character) 로 끝난다.
해당 방식에는 명백한 두 가지 문제점이 존재한다.
- 널 문자를 찾아서 문자열 끝까지 가보기 전에는 끝을 알아내는 방법이 없다.
- 문자열 내부에는 어떤 \0 값도 포함할 수 없으므로, JPEG 그림과 같은 비정형 이진 자료를 C 문자열 내부에 저장할 수 없다.
본인이 판단하기로는 C의 일반적인 문자열 함수로 다루고 싶다면 널 문자를 사용할 수 없다는 의미인 것 같다.
해당 방식을 ASCIZ 문자열이라고 하는데, ASCII Zero-terminated의 약어다.
정리하면 ASCIZ 문자열은 ASCII 문자들로 이루어지고, 끝에 널 문자 \0이 붙는 문자열을 의미한다.
책에서는 해당 방식이 문자열을 저장하는 최악의 방법 중 하나이며, 실무에서 사용하는 것을 추천하지 않는다.
왜 그런 것일까?
문자열 하나를 다른 문자열에 덧붙이는 함수인 strcat를 구현하면서 그 이유를 살펴보자.
void strcat(char* dest, char* src)
{
while (*dest) dest++;
while (*dest ++ = *src++);
}
1. while (*dest) dest++;
- dest가 가리키는 곳의 문자가 널 문자('\0')가 아닐 동안 포인터를 한 칸씩 이동한다.
- 즉, dest 문자열의 끝(널 문자 위치)을 찾는 과정이다.
🔍 예시
dest = "Hello"라면 메모리 구조는:
| H | e | l | l | o | \0 |
dest 포인터는 \0 위치까지 전진합니다.
2. while (*dest++ = *src++);
- *src의 문자 값을 *dest 위치에 복사한다.
- 그리고 dest와 src 모두 후위 증가 연산자 ++로 다음 문자로 이동한다.
- 복사한 값이 0 ('\0')이 되면 while 조건이 false가 되어 반복 종료한다.
즉, src의 모든 문자를 dest 끝에 붙이는 반복문입니다.
해당 코드에는 문제가 있는데, 여러 사람 이름을 문자열 하나에 이어 붙인다고 가정해보자.
char bigString[1000]; // 얼마나 할당해야 하는지 모름
bigString[0] = '\0';
strcat(bigString, "John, ");
strcat(bigString, "Paul, ");
strcat(bigString, "Geprge, ");
strcat(bigString, "Joel ");
문자열 백만 개를 덧붙인다면, 이런 방식이 올바르게 작용할까? 아니다.
strcat의 첫 부분은 매번 널 문자를 찾아 목적지 문자열을 헤매야하므로, strcat 함수는 매우 느리며, 작업 규모가 커지면 성능이 현저히 떨어진다. 해당 코드는 O(n²) 시간 복잡도를 가진다.
이와 같은 문제점은 먼저 다음과 같이 수정이 가능하다.
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(bigString, "John, ");
p = mystrcat(bigString, "Paul, ");
p = mystrcat(bigString, "Geprge, ");
p = mystrcat(bigString, "Joel ");
이제 n제곱이 아니라 선형 효율 O(n) 을 발휘하므로, 대량으로 문자열을 결합할 경우에 성능이 떨어지지 않는다.
파스칼 설계자들은 이미 이런 문제점을 알고있었으며, 문자열의 첫 바이트에 바이트 개수를 저장하는 방법으로 이를 해결했다.
이런 문자열을 파스칼 문자열이라고 한다.
파스칼 문자열은 널 문자를 포함할 수 있으며, 바이트에 들어가는 가장 큰 숫자가 255이므로, 파스칼 문자열은 255 바이트로 길이를 제한했다.
우리의 예제 코드를 다시 살펴보면 문제가 있는데, 바로 버퍼 오버플로에 취약하다.
- 해커는 1000바이트를 넘어선 1100 바이트 문자열을 덧붙일 수 있다.
- 이렇게 스택 프레임을 덮어쓰는 방법으로 반환 주소를 바꿔놓아 함수가 끝나고 돌아가는 시점에 해커가 작성한 코드를 수행하게 만들 수 있다.
따라서 프로그래머는 얼마나 많은 기억공간을 할당해야 할지 계산해야만 한다.
코드는 아래와 같다. 조금 곤란하다.
char* bigString;
int i = 0;
i = strlen("John, ")
+ strlen("Paul, ")
+ strlen("George, ")
+ strlen("Joel ");
bigString = (char*) malloc (i + 1);
// 널 문자를 위한 공간을 고려하세요
지금까지 문자열 크기를 알아내기 위해 모든 문자열을 탐색했다.
또한 덧붙이는 과정에서 문자열을 탐색한다.
최소한 파스칼 문자열을 사용할 경우라면, strlen 연산은 빠르다.
분명 자동으로 기억공간을 다시 할당하는 strcat 버전을 작성할 수 도 있따.
여기서 기억 공간 할당자라는 골치 아픈 문제가 등장한다.
- malloc의 본질은 사용 가능한 메모리 블록을 연결 리스트로 길게 연결한 자유 체인(free chain)이다.
- malloc은 연결 리스트를 따라가며, 요청 받은 메모리 양보다 큰 블록을 찾는다.
- 이렇게 찾은 블록을 2개로 쪼개서, 하나는 호출한 사용자에게 반환하며, 쪼개고 난 다음에 남아있는 블록은 다시 연결 리스트에 넣어둔다.
- free를 호출할 때, free는 해제한 메모리를 자유 체인에 추가한다.
- 결국 자유 체인은 자그마한 조각으로 잘게 쪼개지므로, 큰 조각을 요청하면, 원하는 크기를 충족하는 조각이 없을 수도 있다.
- 이럴 경우 malloc이 타임아웃을 선언한 다음에 자유 체인 주위를 샅샅이 훑어 조각을 정렬하고 인접한 작은 자유 블록을 더 큰 블록으로 결합한다.
- 결국 오래 걸리는 작업이고, 이 모든 혼란의 끝은 malloc의 성능 특성이 결코 아주 빠르다고 볼 수 없으며, 정리하는 과정에서 예측 불가능하게 오래걸릴 수 있다는 사실로 귀결된다.
책을 읽으면서, 위의 내용이 학부생 때 배운 메모리 단편화의 문제면서, 해당 내용이 JVM 동작과 유사하다고 생각했다.
책에서는 이런 현상이 가비지 컬렉션을 지원하는 시스템과 동일한 성능 특성이며,
결국 전형적인 malloc 구현을 따라도 가비지 컬렉션과 비슷한 성능 이슈가 생길 수 있다고 말한다.
똑똑한 프로그래머는 항상 2배수로 메모리 블록을 할당하는 방법으로 잠재적적인 소란을 최소화한다.
이런 방법은 자유 체인에서 생기는 무시무시한 단편화 문제를 상당히 줄여준다.
또한 realloc을 호출할 때, 항상 직전에 할당했던 두배 크기로 기억 공간을 늘려야 한다고 한다.
이런 방식을 따른다면 realloc 호출이 log(n)번을 초과할 필요가 전혀 없으며,
아주 큰 문자열을 처리하는 경우라도 그럴 듯한 성능 특성을 보여주면서 동시에 결코 50%를 초과해서 기억 공간을 낭비하지 않음을 보장한다,
이후 책에서는 XML 을 별로라고 말하는 사람에게 장점도 말하는데(구문 트리 관련) 이는 생략하겠다.
포스팅 이유
책에서는 전공자들이 C를 대충 배우고 JAVA를 바로 사용하는 것을 비판하고 있다.
요즘 시대는 더욱 더 발전해서 AI 가 대부분의 코딩 작업을 수행한다.
프로그래머? 개발자로 살아가면서 제일 중요한 건 기초와 열정이라고 생각한다.
해당 글을 작성하면서 열정과 기초를 다지는 게 중요하다는 동기 부여를 위해 작성하게 되었다.
사실 C는 학부생 3학년부터 작성을 한 적이 없기에 허헣... 머쓱..
기초가 제일 중요한 법..!!!
책에서 준 숙제
- 트랜스메타 칩이 항상 굼벵이처럼 기어가는 이유
- HTML의 기본 TABLE을 위한 규격 명세를 너무나도 형편없이 설계한 탓에, 모뎀 사용자의 웹 페이지에서는 큰 테이블이 늦게 뜨는 이유
- COM이 너무 빠르지만, 프로세스 경계를 가로지를 때는 느린 이유
- NT 개발자들이 화면 드라이버를 커널 공간에서 사용자 공간으로 이동한 이유
이상으로 포스팅을 마칩니다.
