Bit-and-Byte.md

비트와 바이트

비트와 바이트는 모든 상위단계의 결정 사항(아키텍처, 전략)에 영향을 미친다.

비트와 바이트의 기초부터 잘 알아야하는 이유다.

C의 문자열

C의 문자열은 값이 0인 null 문자로 끝나는 바이트 배열이다.

이 방식의 두 가지 문제점

• 널 문자를 찾아서 문자열 끝까지 가보기 전에 문자열의 끝을 알아낼 수가 없다.
• 문자열 내부에 0을 포함할 수 없으므로, JPEG 같은 비정형 이진 자료(Binary Large Object, BLOB)를 C 문자열 내부에 저장할 수 없다.

또 다른 문제점:

문자열을 복사하는 strcat 함수는 실행할 때마다 널 문자를 찾아다녀야 하므로 작업이 많아지면 성능이 현저히 떨어진다.

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

비효율적인 러시아 페인트공 알고리즘의 하나이다.

새로 만들어진 더 긴 문자열의 끝을 가리키는 포인터를 반환하면 문제점을 해결할 수 있다.

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

파스칼 문자열

문자열의 첫 바이트에 바이트 개수를 저장하는 방법으로 이 문제를 해결할 수도 있다.

대신에 아래 처럼 코드를 작성해야 하지만

char* str = "\006Hello!";

이런 꼼수도 있다.

char* str = "*Hello!";
str[0] = strlen(str) - 1;

정확한 기억공간할당이 중요한 이유

생각없이 기억공간을 할당하면

해커가 버퍼 오버플로를 사용해 스택 프레임을 덮어쓰는 방법으로 반환 주소를 바꿔놓아 함수가 끝나고 돌아가는 시점에 해커가 작성한 코드를 실행하게 만들 수 있기 때문이다.

아래와 같이 문자열 크기만큼 기억공간을 할당하는 방법이 있다.

char* bigString;
int i = 0;
i = strlen("John, ")
+ strlen("Paul, ")
+ strlen("George, ")
+ strlen("Joel, ");
bigString = (char*) malloc(i + 1);

파스칼 문자열을 사용하면 strlen 연산을 더 빠르게 할 수 있다.

근데 여기서 malloc이 다른 문제를 발생시킨다.

malloc의 동작방식

malloc은 사용 가능한 메모리 블록을 연결 리스트로 길게 연결한 자유 체인이다.

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

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

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

자유 체인이 계속해서 쪼개지므로 원하는 크기의 메모리 블록이 없을 수 있다.

이런 경우 자유 체인의 조각들을 정렬하고 작은 자유 블록을 큰 블록으로 결합한다.

이 과정에서 시스템이 느려질 수 있다.

또 다른 해결방법

항상 2배수로 메모리 블록을 할당하는 방법이 있다.

공간을 낭비하는 것 같지만 항상 50% 이하로 기억공간을 소비하므로 자유 체인의 단편화를 줄여줄 수 있다.