malloc 성능: 빠른 경로와 느린 경로가 지연을 바꾸는 이유

malloc() 호출은 같은 크기를 요청해도 매번 같은 비용으로 끝나지 않는다. thread-local cache에서 즉시 재사용하는 호출이 있는 반면, arena lock·free chunk 탐색·새 mapping·page fault까지 이어지는 호출도 있다.

그래서 malloc 성능을 “O(1)이니 빠르다”로 요약하면 중요한 질문을 놓친다. C API는 malloc()의 시간 복잡도를 보장하지 않으며, 실제 지연은 allocator 구현과 당시 상태에 달려 있다.

O(1)은 malloc의 성능 보증이 아니다

Big-O는 입력 크기가 커질 때 연산량이 어떻게 증가하는지를 표현한다. 특정 호출의 실제 nanosecond, lock 대기, cache miss, system call 횟수를 보장하지 않는다.

더구나 malloc 전체를 하나의 O(1) 연산이라고 일반화할 수도 없다. 적합한 cached chunk를 pop하는 경로는 매우 짧을 수 있지만, 다른 size class를 찾거나 allocator state를 정리하는 경로는 더 많은 작업을 한다. allocator가 새 memory를 확보해야 하면 kernel interface까지 내려간다.

빠른 경로는 이미 있는 chunk의 재사용이다

현재 glibc에서 작은 요청의 일부는 thread-local tcache에서 충족될 수 있다. 이 경우 공용 arena lock을 잡거나 kernel에 새 mapping을 요청하지 않고 free chunk를 재사용한다.

malloc(size)
    ↓
tcache 등에 적합한 chunk 있음
    ↓
metadata 갱신 후 pointer 반환

다만 “같은 크기니까 항상 tcache hit”는 아니다. tcache가 비어 있거나 해당 크기·설정의 대상이 아니면 공용 allocator 경로로 넘어간다.

느린 경로는 하나가 아니라 여러 층이다

다음 원인은 서로 다른 지연을 만든다.

• tcache miss 뒤 arena 자료구조 탐색과 refill
• 여러 thread가 같은 arena를 사용할 때 lock contention
• 적합한 free chunk를 만들기 위한 split 또는 allocator 내부 정리
• arena 확장이나 anonymous mmap()을 위한 system call
• 반환받은 virtual page를 처음 쓰면서 발생하는 page fault와 zero-fill

여기서 allocation call latency와 memory first-touch latency를 분리해야 한다. malloc() 자체는 virtual range를 빨리 반환했지만, 실제 page를 처음 쓰는 loop에서 major한 비용이 보일 수 있다. 반대로 allocator lock 대기 때문에 malloc() 안에서 지연될 수도 있다.

void *p = malloc(bytes);   /* allocation-call latency */
if (p == NULL) {
    /* handle allocation failure */
}
memset(p, 0, bytes);       /* first-touch 비용이 드러날 수 있는 구간 */

이 예제는 production benchmark가 아니다. compiler 최적화, NUMA policy, transparent huge pages, cgroup memory 상태에 따라 결과가 달라지므로 실제 workload와 같은 조건에서 계측해야 한다.

단편화와 지연을 바로 인과로 묶지 않는다

free space가 여러 크기로 흩어지면 reuse가 어려워지고 탐색이나 새 영역 확보가 늘 수 있다. 하지만 latency spike가 보였다는 이유만으로 곧바로 fragmentation을 원인으로 확정할 수는 없다.

같은 시점의 CPU scheduling, page fault, reclaim, cgroup pressure, lock contention도 확인해야 한다. allocator profile과 kernel metric이 같은 시간축에서 함께 움직이는지 보고 인과를 좁힌다.

평균 하나보다 분포와 조건을 기록한다

malloc latency를 비교할 때는 최소한 다음을 고정하거나 함께 기록한다.

항목	이유
allocation 크기 분포	size class와 mmap 경로가 달라질 수 있음
thread 수	arena contention과 tcache 동작에 영향
allocator·glibc version	내부 정책과 기본 tunable이 달라짐
warm-up·first-touch 여부	cache와 page fault 비용을 분리해야 함
cgroup·NUMA 조건	reclaim과 placement가 지연을 바꿀 수 있음

결과는 평균만 두지 않고 p50·p95·p99·maximum과 sample 수를 함께 둔다. 숫자를 얻기 전에는 “몇 배 느리다” 같은 값을 추정해 쓰지 않는다.

운영에서 계측할 때의 경계

allocator tracing과 stack sampling은 호출 빈도가 높은 process에서 overhead와 대량 event를 만들 수 있다. 먼저 test 환경에서 sampling rate와 buffer 크기를 검증하고, production에서는 PID·시간·allocation size 범위를 제한한다. raw stack에는 symbol name이나 request context 같은 민감 정보가 섞일 수 있으므로 저장·공유 범위도 정한다.

glibc의 내부 구조는 arena·chunk·tcache·bin 설명, allocator가 kernel에서 새 영역을 확보하는 경로는 brk와 mmap의 역할, allocation 이후 RSS 해석은 free와 RSS의 관계로 연결된다.

참고 자료

• GNU C Library: The GNU Allocator
• GNU C Library: Memory Allocation Tunables
• Linux man-pages: malloc(3)
• Linux man-pages: mmap(2)
• Linux kernel: Memory Management