C 에서 문자열의 문제점#
- 널 문자를 찾아서 문자열 끝까지 가보기 전에는 끝을 알아내는 방법이 없다.
- 문자열 내부에는 어떤 0값도 포함할 수 없으므로, JPEG 그림과 같은 비정형 이진 자료 Binary Large OBject(BLOB)를 C 문자열 내부에 저장할 수 없다.
C 문자열이 이런 방삭을 채택한 이유#
- 유닉스와 C 언어를 고안했을 무렵 사용한 PDP-7 마이크로프로세서 때문이다.
- PDP-7은 ASCIZ 문자열 타입을 지원하는데, ASCIZ에는 ‘끝이 Z(ero)인 ASCII’라는 의미를 가진다.
ASCIZ의 문제점#
- strcat을 구현하는 과정이 러시아 페인트공 알고리즘을 사용하고 있다.
- strcat의 첫 부분은 매번 널 문자를 찾아 목적지 문자열을 해매다녀야 하므로 느리며, 작업규모가 커지면 성능이 현저히 떨어진다.
파스칼 문자열#
- 문자열의 첫 바이트에 바이트의 개수를 저장한다.
- 문자열 길이를 알아내기 위해 루프를 돌 필요가 없기 때문에, 빠른 성능을 보여준다.
malloc의 동작 과정#
- malloc의 본질은 사용 가능한 메모리 블록을 linked list로 길게 연결한 free chain이다.
- malloc은 linked list를 따라가며, 요청받은 메모리 양보다 큰 블록을 찾는다. 찾은 블록을 2개로 쪼개서, 하나는 호출한 사용자에게 반환하고 쪼개고 난 다음에 남아있는 블록은 다시 linked list에 넣어둔다.
- free를 호출할 떄, free는 해제한 메모리를 free chain에 넣어둔다.
- 원하는 크기를 충족하는 조각이 없을 경우: malloc이 타임아웃을 선언한 다음에 free chain 주위를 샅샅이 훑어 조각을 정렬하고 인접한 작은 자유 블록을 더 큰 블록으로 결합한다. 성능 저하 문제가 생긴다.
2배수로 메모리 블록을 할당하는 방법#
- free chain에서 생기는 단편화를 상당히 줄여준다.
- 프로그램이 요구하는 크기에 비해 2배를 넘지 않는 기억공간을 사용한다.
목적지 버퍼를 자동으로 재할당하는 strcat 함수를 작성하는 경우#
- realloc을 호출할 떄, 항상 직전에 할당했던 두 배크기로 기억공간을 눌여줘야된다.
- realloc 호출이 log(n)번을 초과할 필요가 전혀 없으며, 아주 큰 문자열을 처리하는 경우에도 그럴 성능 특성을 보여준다.
- 결코 50%를 초과해서 기억공간을 낭비하지 않음을 보장한다.
- 이런 페인트공 알고리즘을 만들지 않기 위해서 CPU부터 시작해서 C를 활용하는 데까지 차곡차곡 기초를 닦아야 한다.