84 할당자의 속 — 힙, 대안 할당자, 대안 표준 라이브러리

84.1 장부 ① — 블록마다 붙는 머리말

free(p)는 크기를 받지 않는다. 그런데도 몇 바이트를 반납하는지 알아야 한다. 답은 단순하다 — 돌려준 주소 바로 앞에 크기가 적혀 있다.

        ┌────────────┬──────────────────────────┐
        │ 헤더        │ 사용자에게 준 자리         │
        │ 크기·플래그  │ ← malloc 이 돌려준 주소   │
        └────────────┴──────────────────────────┘

이 머리말이 45장에서 본 사실 두 가지를 설명한다. 1바이트를 요청해도 실제 소비는 훨씬 크다(헤더 + 정렬 여백), 그리고 작은 조각을 수없이 만들면 관리 정보가 데이터만큼 커진다.

고전적인 설계(dlmalloc 계열)는 여기에 한 겹을 더 얹는다. 블록의 끝에도 크기를 적어 두는 것이다 — 경계 태그(boundary tag). 그러면 어떤 블록에서 “바로 앞 블록”의 크기를 즉시 알 수 있어, 해제할 때 이웃한 빈 조각과 합치는(coalescing) 일이 상수 시간에 끝난다. 조각이 잘게 흩어지는 것을 막는 가장 기본적인 장치다.

84.2 장부 ② — 크기별 목록과 갈래별 캐시

빈 조각을 하나의 긴 목록으로 두면 요청마다 목록 전체를 훑어야 한다. 그래서 크기별로 목록을 나눈다 — 이것이 빈(bin)이다. glibc의 할당자를 예로 들면 대략 이런 층이 있다.

핵심은 갈래별 캐시(tcache)다. 여러 갈래가 같은 장부를 만지면 잠금 때문에 느려지므로(80장), 갈래마다 작은 서랍을 따로 두고 거기서 먼저 꺼낸다. 서랍이 비면 그때만 공용 장부로 간다. 오늘날 빠른 할당자들의 공통 설계이고, 이름만 다를 뿐(tcache, thread cache, mimalloc의 로컬 힙) 착상은 같다.

여기에 83장에서 본 두 가지가 붙는다. 힙이 모자라면 brk로 늘리거나 (작은 요청), 큰 요청은 mmap으로 따로 받는다. 그리고 큰 블록을 해제하면 운영체제로 반납될 수 있지만, 작은 것들은 대개 장부에만 표시된다.

84.3 단편화 — 누수가 없는데도 메모리가 는다

단편화는 두 얼굴이다.

내부 단편화 — 요청보다 큰 조각을 주어서 생기는 낭비다. 24바이트를 요청했는데 32바이트 칸을 주면 8바이트가 죽는다. 크기 클래스를 쓰는 할당자의 숙명이고, 대신 속도를 얻는다.

외부 단편화 — 빈 공간의 총합은 넉넉한데 연속된 큰 덩어리가 없어 큰 요청이 실패하는 상태다. 작은 조각들이 큰 조각 사이사이에 박혀 있으면, 그 큰 조각들을 합칠 수 없다.

이것이 “누수가 없는데 메모리가 계속 는다”는 현상의 정체다. 오래 도는 서버에서 특히 잘 나타나는데, 원인은 대개 수명이 다른 것들을 섞어 할당해서다 — 오래 사는 작은 객체 하나가 큰 빈 구역 한복판에 박혀 그 구역 전체를 묶어 버린다.

84.4 표준 malloc을 갈아 끼우기 — 대안 할당자들

프로그램을 고치지 않고 할당자만 바꿀 수 있다. malloc·free는 결국 이름이므로, 다른 구현을 링크하거나(정적) 실행할 때 끼워 넣으면 (리눅스의 LD_PRELOAD) 그쪽이 쓰인다.

바꾸면 얼마나 달라지는가 — 작업 부하에 따라 다르다가 정직한 답이다. 갈래가 많고 작은 할당이 폭주하는 서버에서는 수십 %가 바뀌기도 하고, 단일 갈래 계산 프로그램에서는 차이가 거의 없다. 그래서 규칙은 하나다: 재고 바꾼다. 그리고 바꾸기 전에 45장의 첫 번째 처방 — 뜨거운 루프에서 아예 할당하지 않기 — 을 먼저 시도하는 편이 대개 이득이 크다.

84.5 대안 표준 라이브러리

할당자보다 한 겹 더 크게 갈아 끼우는 선택지도 있다 — 표준 라이브러리 구현 자체다. 61장에서 “표준은 목록이고 구현은 여럿”이라 한 것의 실물이다.

고르는 기준은 대개 셋이다 — 크기(임베디드·컨테이너), 정적 링크의 편의(musl 이 강점), 기능의 넓이(glibc 이 강점). 그리고 옮길 때 부딪히는 것은 대개 표준 C 가 아니라 확장이다: glibc 에만 있는 함수, 로케일 처리, 스레드·시그널의 미묘한 차이 같은 것들. 61장의 결론 — “표준에 있는 것만 쓰면 옮겨진다” — 이 여기서 값을 한다.

84.6 모양을 바꾸는 대안 — 아레나, 풀, 그리고 할당자를 인자로

지금까지는 같은 malloc을 더 잘 만드는 이야기였다. 다른 길이 있다. 할당의 모양 자체를 바꾸는 것이다.

아레나(리전, 범프 할당자). 큰 덩어리를 한 번 잡아 두고, 요청이 오면 포인터를 앞으로 밀기만 한다. 할당은 덧셈 한 번이라 거의 공짜이고, 해제는 개별로 하지 않는다 — 일이 끝나면 포인터를 처음으로 되돌려 통째로 버린다. 단편화가 없고, 시간이 일정하며, 해제를 잊을 수 없다. 대신 개별 해제를 포기한다.

이 방식은 “수명이 같은 것들”에 완벽하게 맞는다. 웹 서버의 요청 하나, 컴파일러의 함수 하나, 게임의 프레임 하나 — 시작과 끝이 분명한 작업 단위마다 아레나를 하나 두고 끝나면 리셋한다. 실제로 널리 쓰인다(아파치의 메모리 풀, PostgreSQL의 메모리 컨텍스트가 같은 착상이다).

풀(슬랩). 같은 크기의 조각만 다루는 할당자다. 미리 잘라 둔 칸들을 목록으로 관리하므로 할당·해제가 목록 조작 한 번이고, 내부 단편화도 없다. 노드가 수만 개인 자료구조나, 83장에서 본 임베디드의 고정 객체 관리에 맞는다.

할당자를 인자로 받기. 위 둘이 힘을 쓰려면 라이브러리가 “어디서 메모리를 얻을지”를 호출자에게 물어야 한다. 그래서 현대적인 C 라이브러리들은 할당 함수 묶음을 하나의 값으로 만들어 인자로 받는다. 59장에서 배운 함수 포인터의 표가 여기서 정확히 그 일을 한다.

표준 라이브러리의 지형을 걸었고, 그 밑의 창고까지 열어 보았다. 다음 부는 이 모든 함정과 비용을 설계로 다루려는 시도다 — 이 책이 기대 온 라이브러리, proven이다.