malloc() 알고리즘 비교 — 아레나 아키텍처에서 NUMA·락프리 설계까지

본문

이 글은 malloc() 계열 메모리 할당자의 설계 변천사와 현대 할당자들의 특성을 정리한 비교 문서입니다. 저자는 먼저 멀티스레드 프로그램이 확장되지 않는 이유가 힙 병목에 있다고 지적합니다. 여러 스레드가 동시에 메모리를 할당·해제하면 할당자가 이를 직렬화하기 때문에, 할당을 집중적으로 사용하는 프로그램은 프로세서 수가 늘수록 오히려 느려진다는 것입니다. 그래서 libc의 malloc은 최악의 메모리 할당 API라고 단정하고, 가능하면 할당·해제 빈도를 줄이되 특히 패킷 수신 시마다 할당하는 것은 피해야 한다고 조언합니다. 예시로 Linux 커널의 skbuff 재활용 패치와 PF_RING을 들며, NIC에서 순환 버퍼로 할당 없이 복사하면 캡처 성능이 약 10% 향상되고 혼잡 문제도 줄어든다고 설명합니다.

프런트엔드와 백엔드의 설계 진화

malloc()의 기본 설계는 OS로부터 메모리 풀을 미리 할당해두고 애플리케이션이 작은 조각을 나눠 쓰게 하는 것입니다. 최초에는 스택 기반 할당에서 시작해, 링크드 리스트와 버킷-힙 방식으로 프라이빗 힙을 크기 클래스(size class)로 나누는 동적 할당 방식으로 발전했습니다. 2006년에는 OS 메모리 풀과 라이브러리 풀에 이어 세 번째 풀로 '아레나(arena)'가 도입됐는데, 이는 jemalloc의 용어로 서로 다른 속도의 메모리 뱅크나 NUMA 아키텍처, CPU 코어별 메모리를 다루기 위한 개념입니다.

프런트엔드(애플리케이션에 메모리를 나눠주는 쪽)의 진화 순서는 △링크드 리스트 빈 공간 관리 △버킷-힙 크기 클래스(객체 헤더 제거) △소유자 인코딩 △단일 코어 로컬 할당 버퍼(CLAB) △에포크 인코딩 △대형 크기 클래스의 mmap() 직접 할당 △락프리 객체의 안전한 회수를 위한 해저드 포인터(M.M. Michael, 2004) △CPU·코어·스레드별 아레나 풀 △스레드별 로컬 할당 버퍼(TLAB) △상수 시간 모듈로 동기화(FreeBSD madvise를 통한 조기 OS 반환) 순으로 정리됩니다.

백엔드(비어 있거나 조각난 메모리를 OS에 돌려줘 RSS를 줄이는 쪽)의 진화로는 Treiber 스택 기반 원격 f-list 인코딩(R.K. Treiber, 1986), 버디 알고리즘과 이진 버디 알고리즘, 스팬 기반 할당자인 BIPOP 테이블(S. Schneider, 2006), 준선형화 가능한 세그먼트 큐(Y. Afek, 2010), 멀티코어 분산 큐(A. Haas, 2013), k-FIFO 큐(T.A. Henzinger, 2013)를 나열합니다.

할당자별 특성 비교

글은 dlmalloc, ptmalloc2/3, glibc malloc, jemalloc, tcmalloc, mimalloc, Hoard, nedmalloc, phkmalloc, libumem, mtmalloc, snmalloc, 연구용 lockless malloc을 네 가지 표로 비교합니다. 설계 비교에서 jemalloc은 스레드-아레나 친화성으로 CAS 경합을 줄이고, tcmalloc은 CPU별 캐시를 두되 중앙 프리리스트가 남아 있으며, mimalloc은 원자 연산과 false sharing을 최소화하도록 설계됐고, snmalloc은 메시지 패싱 모델로 공유 CAS를 회피하는 NUMA 인지형 보안·확장성 중심 할당자로 평가됩니다.

CAS·원자 연산 경합 표에서는 dlmalloc이 전역 구조와 락 때문에 '매우 높음', ptmalloc/glibc가 아레나 락으로 인한 캐시라인 바운싱으로 '높음'인 반면, mimalloc과 snmalloc은 '매우 낮음'으로 분류됩니다. NUMA·지역성 표에서는 snmalloc과 Solaris의 libumem·mtmalloc이 명시적 NUMA 지원으로 cross-NUMA 트래픽 위험이 낮고, jemalloc은 선택적 NUMA 아레나 튜닝이 가능하며, glibc 계열은 OS 배치에 의존해 원격 접근 위험이 높다고 봅니다. 실용 성능 표에서는 tcmalloc이 소형 할당 처리량에서 '매우 높음', mimalloc과 snmalloc이 경합 하 지연에서 '탁월함', jemalloc이 전반적 균형과 파편화 제어에서 우수하다고 정리됩니다.

워크로드별 추천

추천표는 병목 유형별로 할당자를 매칭합니다. 고경합 멀티스레드는 jemalloc(멀티 아레나+스레드 친화성), 저지연·테일 지연 민감 환경은 mimalloc(낮은 원자 연산 수와 예측 가능한 패스트 패스), NUMA·멀티소켓 서버는 snmalloc, 소형 객체 중심 RPC/웹은 tcmalloc, 대형·혼합 크기는 파편화 관리가 뛰어난 jemalloc을 권합니다. false sharing에 민감하면 Hoard, 보안 강화가 목적이면 snmalloc이나 mimalloc secure, 디버깅·리크 탐지는 런타임 진단이 강한 libumem, 임베디드·저메모리 단일 스레드는 dlmalloc, 실시간·결정론적 요구는 mimalloc을 고르고 glibc malloc은 ABI 안정성이 필요한 레거시의 안전한 폴백으로 제시합니다. 글 말미에는 1961년 Maher의 다중프로세서 저장소 할당 문제부터 2024년 고성능 할당자 시뮬레이션까지 연대순 참고문헌을 나열해 사료적 가치를 더합니다.

Hacker News 반응

• @benjojo12 — 제 폰에서는 ERR_SSL_VERSION_OR_CIPHER_MISMATCH가 뜨네요.
• @Rygian — 여기서는 TLS_CHACHA20_POLY1305_SHA256(256비트 키, TLS 1.3)이 정상 협상됐습니다(Firefox esr 140.14.0).
• @Nnnes — 아카이브 링크를 공유하며, ChaCha/Poly만 협상 가능하게 해둔 독특한 SSL 설정이 의도된 것이라고 설명합니다. 특정 브라우저가 그것을 거부한다는 것을 보여주기 위한 쇼케이스이며, 그 브라우저가 Chromium일 것이라 추측하고 Windows의 Firefox와 내장 curl.exe도 접속을 거부한다고 덧붙입니다.
• @ncruces — 글이 Doug Lea의 malloc 이후 임베디드·저메모리·단일 스레드 할당 분야에서 수십 년간 아무 일도 없었던 것처럼 보이게 한다고 지적합니다. 자신의 최소 Wasm libc에 TLSF를 구현했는데, 파편화는 동등하면서 성능은 훨씬 일관되고 평균적으로 더 좋으며 코드 크기는 크게 줄었다고 보고합니다.
• @ligarota — 'SSL 설정하는 법' 글도 써달라고 요청합니다.

원문: egbert.net (via Hacker News) / 번역·요약: Trawling