glibc부터 mimalloc까지

현대 소프트웨어에서 메모리 할당은 가장 빈번하게 호출되는 연산 중 하나이다. 게임 엔진에서 매 프레임마다 수천 개의 객체가 생성되고 소멸되며, 웹 서버는 수만 개의 동시 요청을 처리하면서 메모리를 할당하고 해제한다. 이러한 환경에서 메모리 할당자의 성능은 전체 시스템의 병목이 될 수 있다.

이 글에서는 malloc이라는 단순한 인터페이스 뒤에 숨겨진 정교한 설계를 탐구한다. Windows의 VirtualAlloc부터 시작해, glibc의 ptmalloc2, Facebook의 jemalloc, Google의 tcmalloc, 그리고 Microsoft Research의 mimalloc까지 각 할당자가 어떻게 다른 문제를 해결하는지 살펴본다.

메모리 할당의 계층 구조

현대 운영체제에서 메모리 할당은 여러 계층으로 이루어져 있다. 각 계층은 서로 다른 추상화 수준과 성능 특성을 가지며, 위로 갈수록 더 세밀한 제어를, 아래로 갈수록 더 큰 단위의 할당을 담당한다.

Windows 메모리 할당 스택

malloc/new               <- 애플리케이션 레벨 (바이트 단위)
    ↓
CRT Heap Manager         <- C 런타임 (서브페이지 관리)
    ↓
HeapAlloc/HeapFree       <- Windows Heap API (페이지 풀링)
    ↓
VirtualAlloc/VirtualFree <- 가상 메모리 API (페이지 단위)
    ↓
NtAllocateVirtualMemory  <- 커널 모드 (시스템 콜)
    ↓
Memory Manager           <- Page Frame Database (물리 메모리)

이 계층 구조가 존재하는 이유는 간단하다. 운영체제는 페이지 단위(보통 4KB)로만 메모리를 관리하는데, 애플리케이션은 16바이트나 64바이트 같은 작은 크기를 요청하기 때문이다.

VirtualAlloc: 가상 메모리의 출발점

Windows의 가장 저수준 메모리 할당 API인 VirtualAlloc을 이해하는 것이 메모리 관리의 핵심이다.

LPVOID VirtualAlloc(
    LPVOID lpAddress,        // NULL이면 시스템이 위치 결정
    SIZE_T dwSize,           // 바이트 단위 크기
    DWORD  flAllocationType, // MEM_RESERVE | MEM_COMMIT
    DWORD  flProtect         // PAGE_READWRITE 등
);

VirtualAlloc의 핵심은 예약(Reserve)과 커밋(Commit)의 분리이다. 이 두 개념의 차이를 이해하면 메모리 관리의 많은 부분이 명확해진다.

MEM_RESERVE는 주소 공간만 예약한다. 이때는 물리 메모리가 전혀 소비되지 않으며, 단지 해당 주소 범위를 다른 할당에서 사용하지 못하도록 막는 것뿐이다. 접근하면 Access Violation이 발생한다.

MEM_COMMIT은 실제로 물리 메모리를 할당한다(엄밀히는 페이지 파일에 공간을 예약하고, 접근 시 물리 메모리를 할당). 이제 해당 메모리에 읽기/쓰기가 가능하다.

// 1단계: 1GB 주소 공간 예약 (물리 메모리 0바이트)
LPVOID pReserved = VirtualAlloc(
    NULL,
    1024 * 1024 * 1024,  // 1GB
    MEM_RESERVE,
    PAGE_NOACCESS
);

// 2단계: 필요할 때만 4KB 커밋
LPVOID pCommitted = VirtualAlloc(
    pReserved,
    4096,
    MEM_COMMIT,
    PAGE_READWRITE
);

// 실제 물리 메모리 사용량: 4KB
// 예약된 주소 공간: 1GB

왜 이렇게 복잡한 구조일까? 몇 가지 강력한 활용 사례가 있다:

1. 희소 배열(Sparse Array): 1TB 주소 공간을 예약하고 실제로는 1GB만 사용하는 경우
2. 동적 확장: 배열 재할당 없이 커밋 영역만 늘려서 크기를 증가
3. 메모리 압박 완화: 필요한 시점에만 물리 메모리를 소비

64비트 시스템에서는 주소 공간이 사실상 무제한(이론적으로 128TB+)이므로, 예약은 매우 저렴한 연산이다.

페이지 크기와 서브페이지 할당의 필요성

VirtualAlloc의 가장 큰 제약은 페이지 단위로만 동작한다는 점이다.

// 16바이트만 필요한데...
char* small = (char*)VirtualAlloc(NULL, 16, MEM_COMMIT, PAGE_READWRITE);
// 실제로는 4096바이트 할당됨 (99.6% 낭비!)

x86/x64 아키텍처에서 기본 페이지 크기는 4KB이다. Large Page를 사용하면 2MB, Huge Page는 1GB까지 가능하지만, 작은 객체 할당에는 여전히 비효율적이다.

이것이 바로 HeapAlloc과 malloc이 필요한 이유이다. 이들은 VirtualAlloc으로 큰 페이지를 받아온 뒤, 내부적으로 작은 블록들로 분할해서 관리한다.

// Windows Heap API
HANDLE hHeap = GetProcessHeap();
void* p = HeapAlloc(hHeap, 0, 16);  // 16바이트만 할당

// 내부 구조 (개념적):
// VirtualAlloc(4KB) → [16B][16B][32B][64B][...] (Bucket 구조)

HeapAlloc은 다음과 같은 일을 한다:

• VirtualAlloc으로 큰 페이지들을 미리 할당
• 내부적으로 작은 블록들로 분할 관리
• Free 시 즉시 VirtualFree를 호출하지 않고 재사용 풀에 보관
• 메타데이터로 할당 상태 추적

glibc malloc (ptmalloc2): 멀티스레딩의 도전

glibc의 기본 할당자인 ptmalloc2(pthreads malloc version 2)는 Wolfram Gloger가 개발했으며, 대부분의 Linux 시스템에서 사용된다. ptmalloc2는 Doug Lea의 dlmalloc에 멀티스레드 지원을 추가한 것이다.

Chunk: 메모리 블록의 기본 단위

ptmalloc2의 핵심 데이터 구조는 chunk이다.

struct malloc_chunk {
    size_t      prev_size;  // 이전 청크가 free면 그 크기
    size_t      size;       // 현재 청크 크기 + 플래그 (하위 3비트)

    // 아래 필드는 free 청크만 사용
    // 할당된 청크는 이 공간을 유저 데이터로 사용
    struct malloc_chunk* fd;  // Forward: 다음 free 청크
    struct malloc_chunk* bk;  // Backward: 이전 free 청크

    // Large 청크만 사용
    struct malloc_chunk* fd_nextsize;
    struct malloc_chunk* bk_nextsize;
};

여기서 놀라운 최적화가 하나 숨어있다. size 필드의 하위 3비트는 플래그로 사용된다:

• P (PREV_INUSE, 0x01): 이전 청크가 사용 중
• M (IS_MMAPPED, 0x02): mmap으로 할당됨
• A (NON_MAIN_ARENA, 0x04): main arena가 아님

왜 하위 3비트를 플래그로 쓸 수 있을까? 모든 청크는 최소 16바이트이며 8바이트 정렬되기 때문에, 크기의 하위 3비트는 항상 0이다. 이 공간을 활용해 추가 메타데이터를 저장하는 것이다.

더 흥미로운 최적화는 메모리 재사용이다. 할당된 청크는 fd/bk 포인터를 유저 데이터 영역으로 덮어쓸 수 있다:

Free Chunk (최소 32바이트):          Allocated Chunk (16바이트도 가능):
+------------------+                +------------------+
| prev_size (8B)   |                | prev_size (8B)   |
| size | P|M|A (8B)|                | size | P|M|A (8B)|
| fd (8B)          |                | user data        |
| bk (8B)          |                | user data        |
| user data...     |                | user data...     |
+------------------+                +------------------+

할당 시에는 fd/bk가 필요 없으므로 이 공간을 유저에게 제공하고, 해제 시에는 유저 데이터를 덮어쓰고 fd/bk를 설정한다. 이로써 메타데이터 오버헤드를 최소화한다.

Arena: 멀티스레드 경합 해결

초기 malloc 구현은 단일 전역 힙을 사용했다. 이는 멀티스레드 환경에서 심각한 병목이 된다:

// 모든 스레드가 하나의 락을 놓고 경쟁
Thread 1: malloc() → 락 대기...
Thread 2: malloc() → 락 획득 → 할당 → 락 해제
Thread 3: malloc() → 락 대기...
Thread 4: free() → 락 대기...

ptmalloc2는 Arena라는 개념으로 이를 해결한다.

struct malloc_state {
    mutex_t mutex;  // 아레나별 락

    // Fastbins: 16~80바이트, LIFO
    mfastbinptr fastbinsY[NFASTBINS];

    // Unsorted bin: 최근 free된 청크들의 캐시
    mchunkptr bins[1];

    // Small bins: 16~512바이트 (64개)
    // Large bins: 512바이트~ (63개)
    mchunkptr bins[2..126];

    // Top chunk: 가장 큰 free 청크
    mchunkptr top;

    size_t system_mem;
    size_t max_system_mem;
};

각 스레드는 자신만의 arena를 가질 수 있다:

Thread 1 → Arena 0 (main)
Thread 2 → Arena 1
Thread 3 → Arena 2
Thread 4 → Arena 0 (재사용, 일부 경합 발생)

• Main Arena: 프로세스의 힙 영역(brk/sbrk 사용)
• Thread Arena: mmap으로 별도 할당
• 최대 개수: CPU 코어 수 * 2~8

Arena가 충분하면 각 스레드가 독립적으로 메모리를 할당할 수 있어 경합이 줄어든다. 하지만 스레드 수가 많으면 여전히 여러 스레드가 하나의 arena를 공유하게 된다.

Bin 체계: 크기별 분류와 최적화

ptmalloc2는 free된 청크들을 크기에 따라 여러 bin으로 분류한다. 각 bin은 서로 다른 할당 전략과 성능 특성을 가진다.

Fast Bins: 속도 최우선

Fast bins는 16~80바이트 크기의 작은 객체를 관리한다. 이 크기 범위는 프로그램에서 가장 빈번하게 할당되는 크기이다.

// Fast bin 구조 (단일 연결 리스트, LIFO)
fastbins[0] (16B): -> [16B] -> [16B] -> [16B] -> NULL
fastbins[1] (24B): -> [24B] -> [24B] -> NULL
fastbins[2] (32B): -> [32B] -> [32B] -> [32B] -> [32B] -> NULL
...
fastbins[9] (80B): -> [80B] -> NULL

Fast bins의 핵심 특징:
1. LIFO (Last In First Out): 가장 최근에 해제된 청크를 먼저 재사용 (캐시 지역성)
2. 단일 연결 리스트: fd 포인터만 사용, bk 불필요 (메모리 절약)
3. 병합 안함: 인접한 free 청크를 병합하지 않음 (속도 우선)

왜 병합하지 않을까? 작은 객체는 생성-소멸이 매우 빠르게 반복된다. 게임 엔진의 임시 벡터, 웹 서버의 요청 객체 등이 그 예이다. 이런 경우 병합 비용이 단편화 비용보다 크다.

// 예: 게임 엔진의 매 프레임마다
for (int frame = 0; frame < 1000000; frame++) {
    Vec3* temp = malloc(24);  // Fast bin에서 즉시 할당
    // ... 계산 ...
    free(temp);                // Fast bin에 즉시 반환
}
// 병합했다면 매번 인접 청크 확인 필요 (비싼 연산)

Fast bins는 주기적으로 consolidation(병합) 과정을 거쳐 단편화를 관리한다.

Tcache: Thread Local Cache

glibc 2.26부터 도입된 tcache는 혁명적인 개선이다.

typedef struct tcache_perthread_struct {
    uint16_t counts[TCACHE_MAX_BINS];        // 각 bin의 청크 개수
    tcache_entry *entries[TCACHE_MAX_BINS];  // LIFO 스택
} tcache_perthread_struct;

Tcache의 특성:

• Thread-local: 각 스레드마다 독립적 (TLS 사용)
• 락 없음: 경합 제로
• 64개 bin: 12~1032바이트 커버 (16바이트 간격)
• bin당 7개: 최대 7개 청크까지 캐싱

성능 비교를 보면 tcache의 효과가 명확하다:

// Tcache 없음 (glibc 2.25)
malloc(32):
  1. Arena 락 획득
  2. Fastbin 검색
  3. 청크 반환
  4. Arena 락 해제
// 약 100ns (락 경합 시 훨씬 느림)

// Tcache 있음 (glibc 2.26+)
malloc(32):
  1. TLS에서 tcache 획득 (락 없음)
  2. tcache->entries[bin] 검색
  3. 청크 반환
// 약 10ns (10배 향상!)

멀티스레드 환경에서 tcache는 대부분의 할당/해제를 arena 접근 없이 처리하므로, 스레드 수가 증가해도 성능이 선형적으로 유지된다.

Unsorted Bin: 재사용 최적화

Unsorted bin은 독특한 역할을 한다. 최근에 free된 청크들(fast bin과 tcache에 들어가지 못한)을 임시로 보관하는 "캐시"이다.

// free(ptr) 호출 시
if (tcache가 가득 참 && fastbin 크기 아님) {
    unsorted_bin에 삽입
}

// 다음 malloc() 시
1. Unsorted bin 순회
2. 요청 크기와 정확히 맞으면 즉시 반환
3. 맞지 않으면 적절한 small/large bin으로 정렬

이는 "방금 free한 메모리를 곧 다시 쓸 확률이 높다"는 시간적 지역성을 활용한 것이다. 특히 반복문 내에서 같은 크기의 객체를 할당-해제-재할당하는 패턴에서 효과적이다.

Small Bins과 Large Bins

Small bins는 512바이트까지의 청크를 관리하며, 각 bin은 정확한 크기를 담당한다:

bins[2] (16B): <-> [16B] <-> [16B] <-> [16B]
bins[3] (24B): <-> [24B] <-> [24B]
bins[4] (32B): <-> [32B] <-> [32B] <-> [32B]
...

• 이중 연결 리스트 (FIFO)
• 정확한 크기 매칭
• 인접 청크와 병합 수행

Large bins는 512바이트 이상의 청크를 관리하며, 크기 범위를 그룹화한다:

bins[64] (512~576B): <-> [512B] <-> [544B] <-> [576B]
bins[65] (576~640B): <-> [576B] <-> [600B] <-> [640B]
...

bin 내부에서는 크기 순으로 정렬되며(fd_nextsize/bk_nextsize 사용), best-fit 전략으로 가장 적합한 크기를 찾다.

malloc 할당 흐름

이제 실제 malloc() 호출 시 어떤 일이 일어나는지 전체 흐름을 살펴보자:

malloc(size) 호출
    ↓
[1] Tcache 확인 (size < 1032B && tcache 활성화)
    └→ Hit: 즉시 반환 (no lock, ~10ns)
    ↓
[2] Arena 락 획득
    ↓
[3] Fastbin 확인 (size <= 80B)
    └→ Hit: 반환 후 락 해제
    ↓
[4] Small bin 확인 (size < 512B)
    └→ 정확한 크기 있으면 반환
    ↓
[5] Unsorted bin 처리
    └→ 순회하면서:
       - 맞는 크기 발견 → 즉시 반환
       - 안 맞으면 적절한 bin으로 정렬
    ↓
[6] Large bin 확인 (size >= 512B)
    └→ Best-fit 검색
    ↓
[7] Top chunk 분할
    └→ top이 충분하면 분할해서 반환
    ↓
[8] 시스템 메모리 요청
    └→ brk() 또는 mmap() 호출

대부분의 경우 1단계(tcache)나 3단계(fastbin)에서 처리되므로, 평균 할당 시간은 수십 나노초에 불과한다.

멀티스레딩 한계

ptmalloc2의 arena 시스템은 개선이지만 완벽하지 않다. 스레드 수가 arena 수를 초과하면 경합이 발생한다:

// 32코어 서버, 100개 스레드
// 최대 Arena: 32 * 8 = 256개
// 하지만 초기에는 순차적으로 생성...

Thread 1-32: 각자 arena 생성 (빠름)
Thread 33: Arena 0 재사용 → Thread 1과 경합!
Thread 34: Arena 1 재사용 → Thread 2와 경합!

Tcache가 대부분의 경우를 커버하지만, tcache 미스 시에는 여전히 arena 락이 병목이 된다. 이것이 jemalloc과 tcmalloc 같은 대안 할당자가 등장한 배경이다.

jemalloc: 단편화와 확장성의 균형

jemalloc은 Jason Evans가 FreeBSD를 위해 개발했으며, 현재 Facebook, Firefox, Redis, Rust 표준 라이브러리 등에서 사용된다.

설계 철학

jemalloc의 핵심 목표는 두 가지이다:
1. 메모리 단편화 최소화: 장기 실행 서버에서 메모리 누수 방지
2. 멀티스레드 확장성: 스레드 수가 증가해도 성능 유지

이를 위해 세 가지 핵심 아이디어를 사용한다:

• 크기 클래스 기반 할당: 정교한 크기 분류로 내부 단편화 최소화
• Thread-local 캐싱: 대부분의 할당을 락 없이 처리
• Active Memory 추적: 메모리 사용량을 능동적으로 관리

계층 구조: Tcache, Arena, Extent

Application → 할당 요청

계층	구성 요소	특징
1. Tcache	Thread Local 캐시	락 없음, 가장 빠름
	- 크기 클래스별 캐시	대부분의 할당 여기서 처리
	- 최대 200개 객체
↓	(캐시 미스)
2. Arena	per-thread/shared	최소한의 경합
	- Bins (크기 클래스별)
	- Extents (메모리 영역)
↓	(메모리 부족)
3. Base Allocator	OS 메모리 할당	큰 단위 할당
	- mmap() / VirtualAlloc()
	- 2MB aligned extents

Extent: 메모리 영역 관리자

Extent는 jemalloc의 독특한 개념이다. 큰 메모리 블록(보통 2MB)을 관리하는 단위이다.

struct extent_t {
    void*        e_addr;        // 시작 주소 (2MB 정렬)
    size_t       e_size;        // 크기 (페이지 배수)
    arena_t*     e_arena;       // 소속 arena

    // Slab 정보 (작은 객체용)
    slab_data_t  e_slab_data;

    // 상태 플래그
    bool         e_committed;   // 물리 메모리 커밋 여부
    bool         e_zeroed;      // 0 초기화 여부

    // Red-Black Tree 노드 (빠른 검색)
    rb_node_t    e_size_node;   // 크기 기준 트리
    rb_node_t    e_addr_node;   // 주소 기준 트리
};

Extent는 다음 두 가지 용도로 사용된다:
1. Slab으로 분할: 작은 객체들을 담는 컨테이너
2. 직접 할당: 큰 객체(1MB+)는 extent를 통째로 사용

Slab: 동일 크기 객체 컨테이너

Slab은 하나의 크기 클래스 객체들만 담는다. 예를 들어 64바이트 slab은 64바이트 객체만 포함한다.

[2MB Extent 구조]

영역	내용	설명
Bitmap (32KB)	01101001...	각 비트 = 객체 할당 상태 (0=free, 1=allocated)
Data	[64B][64B][64B]...[64B]	실제 객체들, 32704개 객체 수용

Bitmap을 사용하면 free slot을 매우 빠르게 찾을 수 있다:

// Free slot 찾기 (CTZ: Count Trailing Zeros)
unsigned long bitmap = slab->bitmap[idx];
int free_bit = __builtin_ctzl(~bitmap);  // 하드웨어 명령어, O(1)
void* ptr = slab->base + free_bit * size_class;

Intel의 CTZ 명령어는 한 사이클에 실행되므로, 비트맵 검색은 극도로 빠르다.

Tcache: Thread Local Cache

jemalloc의 tcache는 ptmalloc2보다 더 정교하다.

struct tcache_t {
    struct {
        void*    stack[TCACHE_NSLOTS];  // LIFO 스택 (보통 20개)
        uint16_t ncached;               // 현재 캐시된 개수
        uint16_t low_water;             // GC 임계값
    } bins[NBINS];  // 크기 클래스별

    uint64_t prof_accum;  // 프로파일링 카운터
};

동작 방식:

void* malloc(size_t size) {
    size_t binind = size_to_bin(size);
    tcache_bin_t* bin = &tcache->bins[binind];

    if (bin->ncached > 0) {
        // Fast path: O(1), 락 없음
        return bin->stack[--bin->ncached];
    }

    // Slow path: arena에서 배치로 리필 (20개 정도)
    arena_batch_fill(bin, binind);
    return bin->stack[--bin->ncached];
}

void free(void* ptr) {
    size_t binind = ptr_to_bin(ptr);
    tcache_bin_t* bin = &tcache->bins[binind];

    if (bin->ncached < TCACHE_NSLOTS) {
        // Fast path: O(1), 락 없음
        bin->stack[bin->ncached++] = ptr;
        return;
    }

    // 캐시 가득 차면 arena로 플러시
    arena_batch_flush(bin, binind);
}

배치 전송(batch transfer)이 핵심이다. 한 번에 여러 객체를 이동함으로써 arena 락 획득 횟수를 1/N로 줄이다.

232개 크기 클래스: 단편화 최소화

jemalloc은 232개의 정교한 크기 클래스를 사용한다. 이는 무작위로 정한 것이 아니라, 내부 단편화를 최소화하도록 설계되었다.

Small 크기 클래스 (8B ~ 14KB)

Tiny (8B 간격):    8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128
Small (16B 간격):  144, 160, 176, 192, 208, 224, 240, 256
Medium (32B 간격): 288, 320, 352, 384, 416, 448, 480, 512
...

각 그룹은 간격이 다릅니다. 작은 크기일수록 간격이 좁고, 큰 크기일수록 간격이 넓어집니다. 이는 다음 공식을 따릅니다:

예를 들어 100바이트를 요청하면 112바이트 클래스를 할당하므로, 낭비는 12바이트(10.7%)이다.

Large와 Huge 크기 클래스

Large (16KB ~ 4MB):

16KB, 20KB, 24KB, 28KB, 32KB
40KB, 48KB, 56KB, 64KB
80KB, 96KB, 112KB, 128KB
...
2MB, 2.5MB, 3MB, 3.5MB, 4MB

Huge (4MB+):

• 페이지 크기의 배수로 할당
• mmap 직접 호출
• tcache/arena 거치지 않음

Active Memory 추적과 Decay-Based Purging

jemalloc의 가장 독특한 기능은 메모리 상태 추적이다.

struct arena_t {
    size_t nactive;  // 사용 중인 페이지

    // 4단계 메모리 상태
    extent_tree_t extents_dirty;     // 해제됨, 빠른 재사용
    extent_tree_t extents_muzzy;     // 부분 해제
    extent_tree_t extents_retained;  // 완전 해제
};

메모리는 다음 4단계 상태를 거칩니다:

1. Active: 현재 사용 중
2. Dirty: 해제되었지만 물리 메모리는 유지 (빠른 재할당 가능)
3. Muzzy: MADV_FREE 적용, OS가 메모리 압박 시 회수 가능
4. Retained: 완전 해제, 주소 공간만 유지

Decay-based purging은 시간 기반으로 메모리를 단계적으로 해제한다:

// 설정 예
decay_dirty_ms: 10000    // dirty → muzzy: 10초 후
decay_muzzy_ms: 10000    // muzzy → retained: 10초 후

이는 다음과 같은 효과를 낸다:

• 단기 메모리 스파이크를 dirty로 처리 (빠른 재사용)
• 장기 미사용 메모리는 자동으로 OS에 반환
• RSS(Resident Set Size) 지속적 증가 방지

장기 실행 서버(Redis, Cassandra 등)에서 jemalloc을 선호하는 이유가 바로 이 기능 때문이다.

tcmalloc: Google의 극한 최적화

tcmalloc(Thread-Caching Malloc)은 Google이 개발한 할당자로, Gmail, YouTube 등 수많은 Google 서비스에서 사용된다.

3층 아키텍처: Front/Middle/Back-End

tcmalloc은 명확한 3층 구조를 가진다:

계층	역할	구성 요소	평균 속도
Front-End	빠른 할당	ThreadCache (전통), Per-CPU Cache (최신)	~50ns
↓	(캐시 미스)
Middle-End	배치 전송	TransferCache, CentralFreeList	~150ns
↓	(객체 부족)
Back-End	페이지 관리	PageHeap, HugePageAwareAllocator	~1000ns

각 층은 서로 다른 책임을 가지며, 대부분의 할당은 Front-End에서 처리된다.

Front-End: Per-CPU Cache의 혁신

ThreadCache (전통적 방식)

class ThreadCache {
private:
    FreeList list_[kNumClasses];  // 86개 크기 클래스
    size_t size_;                  // 현재 캐시 총 크기
    size_t max_size_;              // 동적 조절되는 최대 크기

public:
    void* Allocate(size_t cl) {
        FreeList* list = &list_[cl];
        if (!list->empty()) {
            return list->Pop();  // O(1)
        }
        return FetchFromCentral(cl);  // 중앙에서 배치로 가져옴
    }
};

ThreadCache는 TLS(Thread-Local Storage)에 저장되어 락 없이 접근 가능하다. 하지만 한 가지 문제가 있다:

CPU 0: Thread A가 실행 중 → ThreadCache A 사용
   ↓ (OS가 스레드를 다른 CPU로 이동)
CPU 1: Thread A가 실행 중 → ThreadCache A는 CPU 0에!
                           → 캐시 미스 발생

Per-CPU Cache (OSDI 2021의 혁신)

Google은 2021년 OSDI 논문에서 Per-CPU Cache를 발표했다.

class PerCPUCache {
private:
    struct Slab {
        void* objects[64];   // 객체 포인터 배열
        uint8_t begin;       // 시작 인덱스
        uint8_t end;         // 끝 인덱스
    };

    // CPU 개수 * 크기 클래스 개수
    Slab slabs_[kNumCPUs][kNumClasses];

public:
    void* Allocate(size_t cl) {
        int cpu = GetCurrentCPU();  // rseq로 빠르게 획득
        Slab* slab = &slabs_[cpu][cl];

        if (slab->begin != slab->end) {
            return slab->objects[slab->begin++];  // O(1), 락 없음
        }

        return SlowPath(cl);
    }
};

핵심 기술은 rseq(restartable sequences)이다. Linux 4.18 커널부터 지원되는 기능으로, CPU 마이그레이션을 감지하고 원자적 연산을 보장한다:

// rseq 개념 (의사코드)
do {
    cpu = current_cpu();
    // 여기서 CPU 바뀌면 자동으로 재시작
    result = slabs_[cpu][cl].pop();
} while (cpu_changed);

성능 개선은 놀랍다:

단일 스레드:
  ThreadCache:   70ns
  Per-CPU Cache: 50ns  (29% 향상)

멀티스레드 (64 threads):
  ThreadCache:   ~300ns  (경합 증가)
  Per-CPU Cache: ~55ns   (거의 변화 없음!)

스레드가 어느 CPU로 이동하든 해당 CPU의 캐시를 바로 사용할 수 있으므로, 캐시 미스가 극적으로 줄어든다.

Middle-End: 배치 전송 최적화

TransferCache: 락 획득 최소화

TransferCache는 Front-End와 Back-End 사이에서 배치 전송을 담당한다.

class TransferCache {
private:
    static constexpr int kMaxCapacity = 64;

    struct Entry {
        void* objects[kMaxCapacity];
        int count;
    };

    Entry slots_[kNumSlots];
    std::atomic<int> used_slots_;
    SpinLock lock_;

public:
    int RemoveRange(void** batch, int n) {
        SpinLockHolder h(&lock_);  // 한 번만 락 획득

        int total = 0;
        for (int i = 0; i < used_slots_ && total < n; ++i) {
            Entry& e = slots_[i];
            int to_move = std::min(e.count, n - total);
            memcpy(&batch[total], e.objects, to_move * sizeof(void*));
            total += to_move;
            e.count -= to_move;
        }
        return total;
    }
};

ThreadCache가 비면 TransferCache에서 한 번에 N개(보통 32~64개)를 가져옵니다. 이로써:

• 락 획득 횟수: N번 → 1번
• 캐시 지역성 향상: 연속적 메모리 접근
• Contention 감소: 락 보유 시간 단축

CentralFreeList: 글로벌 풀

CentralFreeList는 각 크기 클래스별로 존재하며, 실제 메모리 풀을 관리한다.

class CentralFreeList {
private:
    SpinLock lock_;

    Span* nonempty_;  // 사용 가능한 객체 있는 span
    Span* empty_;     // 모든 객체 할당된 span

    size_t size_class_;
    size_t object_size_;
};

Span은 여러 페이지의 집합이며, 동일 크기 객체들을 담는다:

Span (8 pages = 32KB, 64바이트 객체용):

내용	설명
[64B][64B][64B]...[64B]	512개 객체
FreeList	빈 슬롯 추적

Back-End: PageHeap와 HugePage

PageHeap: Span 관리자

PageHeap는 페이지 단위로 메모리를 관리한다.

class PageHeap {
private:
    // 1~255 페이지: 배열 인덱싱 (O(1))
    SpanList free_[kMaxPages];

    // 256+ 페이지: 트리 구조 (O(log n))
    std::set<Span*, SpanSizeOrder> large_;

    HugePageAwareAllocator huge_allocator_;

public:
    Span* New(Length n) {
        // 1. 정확한 크기 검색
        if (n < kMaxPages && !free_[n].empty()) {
            return free_[n].Pop();
        }

        // 2. 더 큰 span 분할
        for (Length s = n + 1; s < kMaxPages; ++s) {
            if (!free_[s].empty()) {
                Span* span = free_[s].Pop();
                return Carve(span, n);  // n페이지만 떼어내고 나머지 반환
            }
        }

        // 3. Large span 검색
        auto it = large_.lower_bound(n);
        if (it != large_.end()) {
            return Carve(*it, n);
        }

        // 4. 시스템에서 새로 할당
        return AllocLarge(n);
    }

    void Delete(Span* span) {
        // 인접 span과 병합 (coalescing)
        Span* prev = GetDescriptor(span->first_page - 1);
        if (prev && prev->IsFree()) {
            span = Merge(prev, span);
        }

        Span* next = GetDescriptor(span->first_page + span->num_pages);
        if (next && next->IsFree()) {
            span = Merge(span, next);
        }

        PrependToFreeList(span);
    }
};

병합(coalescing)은 외부 단편화를 방지한다. 인접한 free span들을 하나로 합쳐서 큰 할당에 대응한다.

HugePageAwareAllocator: TLB 최적화

tcmalloc의 최신 버전은 HugePage(2MB 페이지)를 적극 활용한다.

TLB(Translation Lookaside Buffer)는 가상 주소를 물리 주소로 변환하는 캐시이다. TLB 미스는 100+ 사이클의 페이지 테이블 워킹을 발생시킨다.

Intel x64 TLB:
  L1 DTLB: 64 entries (4KB) = 256KB 커버
  L2 STLB: 1024 entries (4KB) = 4MB 커버
  L2 STLB: 32 entries (2MB) = 64MB 커버

2MB 페이지를 사용하면:

• 하나의 TLB entry가 512배 더 많은 메모리를 커버
• TLB 미스율 극적 감소
• 메모리 집약적 워크로드에서 10-30% 성능 향상

tcmalloc은 2MB 단위로 메모리를 할당하고, 내부적으로 작은 객체들로 분할한다:

[2MB HugePage]

객체 크기	수용량
64B objects	32,768개
256B objects	8,192개
4KB pages (small alloc)	512개

성능 벤치마크

OSDI 2021 논문에서 발표된 벤치마크:

단일 스레드 (malloc + free 1회 평균):
  ptmalloc2:  300ns
  jemalloc:   120ns
  tcmalloc:    50ns (Per-CPU mode)

멀티스레드 (64 threads, 높은 경합):
  ptmalloc2: 2400ns (8배 느림, 락 경합)
  jemalloc:   180ns (1.5배 느림)
  tcmalloc:    55ns (거의 동일!)

메모리 효율 (RSS):
  ptmalloc2: 1.00x (기준)
  jemalloc:  0.85x (15% 절감)
  tcmalloc:  0.90x (10% 절감)

tcmalloc은 멀티스레드 확장성에서 압도적이며, 특히 Per-CPU mode는 스레드 수에 거의 영향을 받지 않다.

mimalloc: Free List Sharding 혁명

mimalloc은 Microsoft Research의 Daan Leijen과 Ben Zorn이 2019년 발표한 할당자이다. 기존 할당자와 완전히 다른 접근 방식을 사용한다.

핵심 아이디어: Page-Local Free List

전통적인 할당자(tcmalloc, jemalloc)는 크기 클래스별로 전역 free list를 유지한다:

전역 Free List (64바이트):
[obj1@page1] -> [obj2@page3] -> [obj3@page1] -> [obj4@page5] -> ...

이 구조의 문제점:
1. False Sharing: 여러 스레드가 같은 캐시 라인을 수정
2. 캐시 지역성 나쁨: 객체들이 여러 페이지에 분산
3. 크로스 스레드 해제: 다른 스레드가 해제 시 락 필요

mimalloc의 해결책은 각 페이지가 자신만의 free list를 소유하는 것이다:

Page 1 (스레드 A 소유):
  local:  [obj1] -> [obj2] -> [obj3] -> NULL
  thread: [obj7] (다른 스레드가 free한 것)

Page 2 (스레드 B 소유):
  local:  [obj4] -> [obj5] -> NULL
  thread: NULL

Page 구조

typedef struct mi_page_s {
    // 슬롯 정보
    uint8_t  block_size;      // 객체 크기
    uint16_t capacity;        // 총 슬롯 개수
    uint16_t reserved;        // 할당된 개수

    // 두 개의 free list (핵심!)
    mi_block_t* local_free;   // 로컬 스레드 free list
    mi_block_t* thread_free;  // 다른 스레드 free list (atomic)

    uint8_t* page_start;      // 페이지 시작 주소
    mi_heap_t* heap;          // 소속 힙 (스레드 소유)

    mi_page_t* next;
    mi_page_t* prev;

    // 동기화 (thread_free용 단일 CAS)
    std::atomic<uintptr_t> thread_freed;

    bool is_zero : 1;
    bool is_committed : 1;
} mi_page_t;

두 개의 free list가 핵심이다:

• local_free: 페이지 소유 스레드만 접근 (락 없음)
• thread_free: 다른 스레드가 free한 객체 (atomic CAS)

할당 흐름

void* mi_malloc(size_t size) {
    // 1. 현재 스레드 힙 (TLS)
    mi_heap_t* heap = mi_heap_get_default();

    // 2. 크기 클래스
    size_t bin = mi_bin_index(size);

    // 3. 현재 페이지
    mi_page_t* page = heap->pages[bin];

    // 4. Local free list (락 없음, 빠름!)
    if (page->local_free != NULL) {
        mi_block_t* block = page->local_free;
        page->local_free = block->next;
        return block;
    }

    // 5. Thread free list 수확
    if (page->thread_free != NULL) {
        mi_page_collect_free(page);  // thread_free → local_free 이동
        // 재시도
        if (page->local_free != NULL) {
            mi_block_t* block = page->local_free;
            page->local_free = block->next;
            return block;
        }
    }

    // 6. 새 페이지 필요
    return mi_malloc_generic(heap, size);
}

대부분의 경우 4단계(local_free)에서 처리되므로, 평균 할당 시간은 40~50ns이다.

크로스 스레드 해제: 단일 CAS의 마법

mimalloc의 가장 혁신적인 부분은 단일 CAS 연산으로 크로스 스레드 해제를 처리하는 것이다.

void mi_free(void* ptr) {
    // 1. 포인터 → 페이지 변환 (O(1), 비트 마스킹)
    mi_page_t* page = mi_ptr_page(ptr);

    // 2. 소유 스레드 확인
    mi_heap_t* heap = page->heap;

    if (mi_heap_is_mine(heap)) {
        // Case 1: 같은 스레드 (락 없음)
        mi_block_t* block = (mi_block_t*)ptr;
        block->next = page->local_free;
        page->local_free = block;
    } else {
        // Case 2: 다른 스레드 (단일 CAS!)
        mi_block_t* block = (mi_block_t*)ptr;
        uintptr_t tfree;

        do {
            tfree = mi_atomic_load_relaxed(&page->thread_freed);
            block->next = (mi_block_t*)(tfree & ~0x3);
        } while (!mi_atomic_cas_weak_release(
            &page->thread_freed,
            tfree,
            (uintptr_t)block
        ));
    }
}

왜 단일 CAS인가?

• Lock-free: 락 오버헤드 제로
• 최소 경합: CAS 1회로 완료, 재시도 확률 낮음
• 확장성: 스레드 수가 증가해도 성능 저하 없음

비교:

jemalloc/tcmalloc (크로스 스레드 free):
  1. 글로벌 락 획득
  2. Free list에 추가
  3. 락 해제
  → ~100ns, 경합 시 더 느림

mimalloc:
  1. 단일 CAS
  → ~20ns, 경합 거의 없음

포인터에서 페이지 찾기: O(1) 매직

mimalloc이 빠른 또 다른 이유는 포인터로부터 페이지 메타데이터를 O(1)에 찾는 기법이다.

static inline mi_page_t* mi_ptr_page(void* ptr) {
    // 페이지는 64KB로 정렬됨
    uintptr_t addr = (uintptr_t)ptr;
    uintptr_t page_addr = addr & ~(MI_PAGE_SIZE - 1);

    // 페이지 시작에 메타데이터 포인터 저장
    return *(mi_page_t**)page_addr;
}

64KB 정렬을 통해 비트 마스킹만으로 페이지 시작 주소를 계산한다. 이는 다음과 같은 장점이 있다:

• 해시 테이블 불필요 (jemalloc은 extent 트리 검색)
• 캐시 미스 최소화
• 예측 가능한 성능

캐시 지역성과 False Sharing 제거

Page-local free list의 가장 큰 이점은 캐시 지역성이다.

전통적 할당자:
  Thread A malloc:
    [obj1@page1] -> [obj5@page3] -> [obj2@page1] -> [obj9@page5]
  → 페이지 점프, 캐시 미스 많음

mimalloc:
  Thread A malloc:
    [obj1@page1] -> [obj2@page1] -> [obj3@page1] -> [obj4@page1]
  → 같은 페이지, 캐시 히트!

또한 False Sharing이 제거된다:

전통적 할당자:
  [캐시 라인: obj1 | obj2]
  Thread A: obj1 수정 → 캐시 무효화
  Thread B: obj2 수정 → 캐시 무효화
  → 핑퐁 효과

mimalloc:
  Page 1 (Thread A 전용): [obj1 | obj2]
  Page 2 (Thread B 전용): [obj3 | obj4]
  → 독립적, 경합 없음

성능 벤치마크

MSR 논문의 벤치마크 결과:

단일 스레드 (ns per operation):
  mimalloc:    45ns  (최고)
  tcmalloc:    50ns
  jemalloc:    65ns
  ptmalloc2:  280ns

멀티스레드 (32 threads, 높은 경합):
  mimalloc:    52ns  (확장성 최고!)
  tcmalloc:    58ns
  jemalloc:    95ns
  ptmalloc2: 1200ns

메모리 효율 (오버헤드):
  mimalloc:   1.03x  (3% 오버헤드)
  jemalloc:   1.08x
  tcmalloc:   1.12x
  ptmalloc2:  1.25x

크로스 스레드 해제 (한 스레드 할당, 다른 스레드 해제):
  mimalloc:    55ns  (압도적!)
  tcmalloc:   120ns
  jemalloc:   150ns
  ptmalloc2:  800ns

mimalloc은 모든 측면에서 최고 또는 최고에 근접한 성능을 보이다. 특히 크로스 스레드 해제에서 압도적이다.

가상 메모리 최적화: Large Page와 Memory Mapping

할당자 알고리즘도 중요하지만, 운영체제의 가상 메모리 기능을 어떻게 활용하느냐도 성능에 큰 영향을 미칩니다.

Large Page: TLB 효율의 극대화

TLB의 역할

가상 메모리 시스템에서 모든 메모리 접근은 가상 주소를 물리 주소로 변환해야 한다. 이 변환 정보는 TLB(Translation Lookaside Buffer)에 캐시된다.

메모리 접근 프로세스:
  1. TLB 검색
     → Hit: 1 cycle (빠름!)
     → Miss: Page Table Walk (~100 cycles)
  2. 물리 주소로 접근

Intel x64 CPU의 전형적인 TLB:

L1 DTLB: 64 entries (4KB pages)
  → 64 * 4KB = 256KB 커버

L2 STLB: 1536 entries (4KB pages)
  → 1536 * 4KB = 6MB 커버

L2 STLB: 32 entries (2MB pages)
  → 32 * 2MB = 64MB 커버

Large Page의 효과

1GB 메모리를 순회하는 경우:

4KB pages:
  필요한 TLB entries: 1GB / 4KB = 262144
  실제 TLB entries: 1536
  TLB miss rate: 99.4%
  → 거의 모든 접근에서 page table walk

2MB pages:
  필요한 TLB entries: 1GB / 2MB = 512
  실제 TLB entries: 32
  TLB miss rate: 93.75%

  하지만!
  Hot working set이 64MB 이하면:
    필요한 entries: 64MB / 2MB = 32
    TLB miss rate: 거의 0%

Large Page는 다음과 같은 경우 효과적이다:

• 큰 데이터 구조 (데이터베이스 버퍼 풀, 메모리 캐시)
• 순차 접근 패턴
• 장기간 유지되는 메모리

Windows에서 Large Page 사용

// 1. Large Page 크기 확인
SIZE_T largePageSize = GetLargePageMinimum();  // 보통 2MB

// 2. 권한 필요 (SeLockMemoryPrivilege)
// 관리 도구 → 로컬 보안 정책 → "Lock pages in memory"

// 3. 할당
void* ptr = VirtualAlloc(
    NULL,
    100 * 1024 * 1024,  // 100MB (2MB 배수로 자동 라운딩)
    MEM_COMMIT | MEM_RESERVE | MEM_LARGE_PAGES,
    PAGE_READWRITE
);

if (ptr == NULL) {
    // 실패 가능 (권한 없음, 메모리 단편화 등)
    DWORD error = GetLastError();
}

제약사항:

• 관리자 권한 필요 (보안 정책 설정)
• 2MB 단위로만 할당
• Swap 불가 (항상 물리 메모리에 상주)
• 메모리 단편화 시 할당 실패 가능

성능 향상:

데이터베이스 버퍼 풀 (4GB):
  4KB pages: TLB miss ~80%, 처리량 100 req/s
  2MB pages: TLB miss ~5%,  처리량 130 req/s
  → 30% 향상

Linux Transparent Huge Pages

Linux는 더 편리한 방법을 제공한다:

# 커널이 자동으로 4KB → 2MB 병합
echo always > /sys/kernel/mm/transparent_hugepage/enabled

# 또는 애플리케이션에서 힌트
madvise(ptr, size, MADV_HUGEPAGE);

애플리케이션 코드 변경 없이 커널이 자동으로 최적화한다. 다만 다음 주의사항이 있다:

• 메모리 압축(compaction) 오버헤드
• latency spike 가능성
• Redis 등 일부 애플리케이션은 비활성화 권장

Memory Mapped File: 제로 카피 I/O

전통적 파일 I/O의 비효율

// 전통적 방식: 데이터가 2번 복사됨
char buffer[4096];
read(fd, buffer, 4096);    // 커널 버퍼 → 유저 버퍼
process(buffer);
write(fd2, buffer, 4096);  // 유저 버퍼 → 커널 버퍼

각 read/write는 다음을 수반한다:
1. 시스템 콜 오버헤드
2. 메모리 복사
3. 컨텍스트 스위칭

Memory Mapped I/O

// 파일 → 가상 메모리 직접 매핑
void* ptr = mmap(NULL, file_size, PROT_READ | PROT_WRITE,
                 MAP_SHARED, fd, 0);

// 메모리처럼 접근
struct Record {
    int id;
    char name[256];
};

Record* records = (Record*)ptr;
records[100].id = 999;  // 자동으로 디스크에 기록!

munmap(ptr, file_size);

장점:

• 제로 카피: 커널 버퍼와 유저 버퍼가 동일
• Lazy Loading: 접근하는 페이지만 로드 (페이지 폴트 기반)
• 간단한 코드: 파일을 배열처럼 사용

Windows 구현

// 1. 파일 열기
HANDLE hFile = CreateFileW(
    L"data.bin",
    GENERIC_READ | GENERIC_WRITE,
    0, NULL, OPEN_ALWAYS,
    FILE_ATTRIBUTE_NORMAL, NULL
);

// 2. 파일 매핑 객체 생성
HANDLE hMapFile = CreateFileMappingW(
    hFile, NULL,
    PAGE_READWRITE,
    0, 1ULL << 30,  // 1GB (파일보다 크면 확장)
    NULL
);

// 3. 가상 주소 공간에 매핑
void* pView = MapViewOfFile(
    hMapFile,
    FILE_MAP_ALL_ACCESS,
    0, 0, 0  // 전체 매핑
);

// 4. 사용
Data* data = (Data*)pView;
data[1000000].value = 42;

// 5. 플러시 (선택적, 보통 자동)
FlushViewOfFile(data, sizeof(Data) * 1000000);

// 6. 정리
UnmapViewOfFile(pView);
CloseHandle(hMapFile);
CloseHandle(hFile);

Copy-on-Write 매핑

Private 매핑은 흥미로운 활용이 가능하다:

void* pPrivate = MapViewOfFile(
    hMapFile,
    FILE_MAP_COPY,  // COW 매핑
    0, 0, 0
);

// 읽기: 파일 내용 직접 접근
int x = ((int*)pPrivate)[0];

// 쓰기: 페이지 복사본 생성, 파일은 그대로
((int*)pPrivate)[0] = 999;

사용 사례:

• 프로세스 Fork: 부모 프로세스 메모리를 자식에게 COW로 공유
• 실행 파일 로딩: DLL/EXE를 여러 프로세스가 공유, 수정 시 복사
• 스냅샷: 원본 파일을 건드리지 않고 수정 버전 생성

실제 데이터베이스 활용:

• LMDB: 전체 데이터베이스를 mmap, 극도로 빠른 읽기
• SQLite: 큰 테이블에 mmap 사용 옵션
• MongoDB: WiredTiger 엔진이 mmap 활용

Commit/Decommit 패턴: 동적 메모리 관리

동적 배열 구현

class DynamicArray {
private:
    void* base_;
    size_t reserved_;   // 예약된 크기 (주소 공간)
    size_t committed_;  // 커밋된 크기 (물리 메모리)
    size_t used_;       // 실제 사용 크기

public:
    DynamicArray(size_t max_size) {
        // 1GB 주소 공간 예약 (물리 메모리 0)
        base_ = VirtualAlloc(
            NULL, max_size,
            MEM_RESERVE,
            PAGE_NOACCESS
        );
        reserved_ = max_size;
        committed_ = 0;
        used_ = 0;
    }

    void Grow(size_t new_size) {
        if (new_size > committed_) {
            // 64KB 단위로 커밋 확장
            size_t new_commit = RoundUp(new_size, 64 * 1024);

            VirtualAlloc(
                (char*)base_ + committed_,
                new_commit - committed_,
                MEM_COMMIT,
                PAGE_READWRITE
            );

            committed_ = new_commit;
        }
        used_ = new_size;
    }

    void Shrink() {
        // 사용률 25% 이하면 절반 decommit
        if (used_ < committed_ / 4) {
            size_t new_commit = committed_ / 2;

            VirtualFree(
                (char*)base_ + new_commit,
                committed_ - new_commit,
                MEM_DECOMMIT
            );

            committed_ = new_commit;
        }
    }

    ~DynamicArray() {
        VirtualFree(base_, 0, MEM_RELEASE);
    }
};

Commit Granularity

Windows는 64KB 단위 커밋을 권장한다:

#define COMMIT_GRANULARITY (64 * 1024)

// 이유:
// 1. VirtualAlloc 내부 최적화 단위
// 2. 페이지 테이블 갱신 비용 최소화
// 3. 메모리 단편화 방지

작은 단위로 커밋하면:

• 시스템 콜 횟수 증가
• 페이지 테이블 관리 복잡도 증가

큰 단위로 커밋하면:

• 메모리 낭비 증가

64KB는 좋은 균형점이다.

Decommit 전략

// Immediate Decommit (메모리 압박 시)
void FreeBlock(void* ptr, size_t size) {
    if (IsMemoryPressure()) {
        VirtualFree(ptr, size, MEM_DECOMMIT);
    }
}

// Delayed Decommit (성능 우선)
class DelayedDecommit {
private:
    struct Entry {
        void* ptr;
        size_t size;
        std::chrono::time_point<steady_clock> time;
    };

    std::vector<Entry> pending_;

public:
    void Add(void* ptr, size_t size) {
        pending_.push_back({ptr, size, now()});

        // 10초 이상 된 것들만 decommit
        auto cutoff = now() - std::chrono::seconds(10);

        for (auto it = pending_.begin(); it != pending_.end();) {
            if (it->time < cutoff) {
                VirtualFree(it->ptr, it->size, MEM_DECOMMIT);
                it = pending_.erase(it);
            } else {
                ++it;
            }
        }
    }
};

성능 비교:

벤치마크: 100MB 배열 생성 → 사용 → 해제 → 재생성

malloc/free:
  할당: 50ms (페이지 폴트)
  해제: 5ms
  재할당: 50ms (다시 페이지 폴트)

Reserve/Commit/Decommit:
  초기 예약: 0.1ms
  커밋: 20ms
  decommit: 10ms
  재커밋: 15ms (페이지 테이블 재사용)

Reserve/Commit (decommit 안함):
  초기 예약: 0.1ms
  커밋: 20ms
  재사용: 0ms (이미 커밋됨, 매우 빠름!)

권장 전략:
1. 예측 가능한 크기: Reserve/Commit, decommit 최소화
2. 변동 심한 크기: Delayed decommit (10초 타임아웃)
3. 메모리 제약: Immediate decommit

할당자 선택 가이드

특성 비교표

특성	ptmalloc2	jemalloc	tcmalloc	mimalloc
단일 스레드	280ns	120ns	70ns	45ns
멀티 스레드	1200ns	180ns	55ns	52ns
크로스 스레드 해제	800ns	150ns	120ns	55ns
메모리 효율	1.25x	1.08x	1.12x	1.03x
단편화 제어	약함	강함	중간	매우 강함
확장성	낮음	높음	매우 높음	매우 높음
HugePage 지원	제한적	있음	적극적	있음
프로파일링	없음	상세	상세	기본

사용 권장

ptmalloc2 (glibc 기본)

적합한 경우:
  - 범용 애플리케이션
  - 이식성 중요
  - 특별한 최적화 불필요

주의사항:
  - 멀티스레드 성능 낮음
  - 장기 실행 시 단편화 증가

jemalloc

적합한 경우:
  - 장기 실행 서버 (Redis, Cassandra)
  - 메모리 단편화 민감
  - RSS 제어 중요
  - Firefox, Rust 등 이미 검증됨

사용 예:
  export LD_PRELOAD=/usr/lib/libjemalloc.so
  ./my_server

tcmalloc

적합한 경우:
  - 고성능 웹 서버
  - 멀티코어 시스템 (32+ cores)
  - HugePage 활용 가능
  - Google 서비스급 스케일

사용 예:
  export LD_PRELOAD=/usr/lib/libtcmalloc.so
  export TCMALLOC_PERCPU_CACHE=1  # Per-CPU mode

mimalloc

적합한 경우:
  - 최신 멀티코어 시스템
  - 최고 성능 요구
  - 크로스 스레드 해제 빈번
  - 게임 엔진, 실시간 시스템

사용 예:
  // CMake
  find_package(mimalloc REQUIRED)
  target_link_libraries(myapp mimalloc)

실전 벤치마킹

실제 워크로드에서 테스트하는 것이 중요하다:

// 간단한 벤치마크 프레임워크
#include <chrono>

void benchmark_allocator(int num_threads, int iterations) {
    auto start = std::chrono::high_resolution_clock::now();

    #pragma omp parallel for num_threads(num_threads)
    for (int t = 0; t < num_threads; t++) {
        for (int i = 0; i < iterations; i++) {
            void* ptr = malloc(64);
            // ... 사용 ...
            free(ptr);
        }
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);

    std::cout << "Total: " << duration.count() << " ns\n";
    std::cout << "Per op: " << duration.count() / (num_threads * iterations) << " ns\n";
}

각 할당자로 컴파일해서 비교:

# ptmalloc2 (기본)
g++ bench.cpp -fopenmp -o bench_glibc
./bench_glibc

# jemalloc
g++ bench.cpp -fopenmp -ljemalloc -o bench_jemalloc
./bench_jemalloc

# tcmalloc
g++ bench.cpp -fopenmp -ltcmalloc -o bench_tcmalloc
./bench_tcmalloc

# mimalloc
g++ bench.cpp -fopenmp -lmimalloc -o bench_mimalloc
./bench_mimalloc

마치며

메모리 할당은 단순해 보이지만 그 내부는 수십 년간의 연구와 최적화가 집약된 정교한 시스템이다. 이 글에서 살펴본 내용을 요약하면:

1. 계층 구조: VirtualAlloc → HeapAlloc → malloc, 각 계층은 다른 추상화 제공
2. ptmalloc2: Arena + Bin + Tcache, 멀티스레드 대응의 고전적 접근
3. jemalloc: 크기 클래스 + Extent + Decay, 단편화 제어의 정석
4. tcmalloc: Per-CPU + 3층 구조 + HugePage, 극한의 성능 추구
5. mimalloc: Page-local Free List + 단일 CAS, 혁신적 설계

현대 할당자들은 다음 공통 전략을 사용한다:

• Thread-local 캐싱으로 락 회피
• 크기 클래스로 단편화 최소화
• 배치 전송으로 경합 감소
• Large Page로 TLB 효율 향상

하지만 각자 다른 trade-off를 선택했다:

• jemalloc: 메모리 효율 우선
• tcmalloc: 극한 성능 우선
• mimalloc: 균형과 혁신

여러분의 애플리케이션에 어떤 할당자가 적합한지는 실제 워크로드 벤치마킹을 통해 결정해야 한다.

더 읽을거리

공식 문서

1. Microsoft Learn - VirtualAlloc
   https://learn.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualalloc
   Windows 가상 메모리 API 공식 문서

2. glibc malloc 소스 코드
   https://sourceware.org/git/?p=glibc.git;a=blob;f=malloc/malloc.c
   ptmalloc2 구현 전체 (14,000+ 라인)

3. glibc Malloc Internals Wiki
   https://sourceware.org/glibc/wiki/MallocInternals
   Arena, bin, chunk 구조 상세 설명

학술 논문

4. Jason Evans (2006). "A Scalable Concurrent malloc(3) Implementation for FreeBSD"
   BSDCan 2006
   https://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf
   jemalloc 초기 설계 논문

5. Emery D. Berger, et al. (2000). "Hoard: A Scalable Memory Allocator for Multithreaded Applications"
   ASPLOS 2000
   False sharing, 캐시 지역성 문제 분석

6. Google (2021). "Beyond malloc efficiency to fleet efficiency: a hugepage-aware memory allocator"
   OSDI 2021
   https://research.google/pubs/pub50370/
   tcmalloc Per-CPU mode, HugePage 최적화

7. Daan Leijen, Benjamin Zorn, Leonardo de Moura (2019). "Mimalloc: Free List Sharding in Action"
   MSR-TR-2019-18
   https://www.microsoft.com/en-us/research/publication/mimalloc-free-list-sharding-in-action/
   mimalloc 설계 철학과 벤치마크

온라인 리소스

8. tcmalloc Design Documentation
   https://google.github.io/tcmalloc/design.html
   Front/Middle/Back-end 아키텍처 상세

9. jemalloc Documentation
   https://jemalloc.net/
   크기 클래스, extent, slab 설명

10. mimalloc GitHub Repository
    https://github.com/microsoft/mimalloc
    벤치마크 결과, API 문서, 최신 업데이트

추가 읽을거리

11. Ulrich Drepper (2007). "What Every Programmer Should Know About Memory"
    https://people.freebsd.org/~lstewart/articles/cpumemory.pdf
    캐시, TLB, 가상 메모리 심층 분석 (필독!)

12. Intel (2023). "Intel 64 and IA-32 Architectures Optimization Reference Manual"
    https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
    Large Page, 캐시 최적화 기법

13. Linux Kernel Documentation - Transparent Huge Pages
    https://www.kernel.org/doc/html/latest/admin-guide/mm/transhuge.html
    THP 동작 원리와 설정

14. Windows Internals, 7th Edition (Part 1)
    Mark Russinovich, et al.
    Chapter 5: Memory Management