[시스템 프로그래밍 #3] 커스텀 할당자 패턴

REIN·2025년 12월 20일
BuddyAllocatorC++PoolAllocatorarena게임엔진메모리풀시스템 프로그래밍

게임 개발 초급 CS

목록 보기
5/18

성능과 제어를 위한 메모리 관리 전략

일반 목적 할당자인 malloc과 free는 범용성을 위해 설계되었다. 어떤 크기의 메모리든, 어떤 패턴으로든 할당하고 해제할 수 있다. 하지만 이러한 범용성은 대가를 치른다. 게임 엔진에서 매 프레임 수천 개의 파티클을 생성하고 삭제할 때, 실시간 시스템에서 밀리초 단위의 지연도 허용되지 않을 때, malloc의 오버헤드는 무시할 수 없는 병목이 된다.

이번 글에서는 도메인 특화 할당자(Domain-Specific Allocator)의 세계를 탐험한다. 각 할당자는 특정 사용 패턴을 가정하고, 그 제약을 활용하여 극적인 성능 향상을 달성한다.

왜 malloc은 느린가?

먼저 malloc이 내부적으로 무엇을 하는지 살펴보자.

/* glibc malloc의 단순화된 흐름 */
void* malloc(size_t size) {
    /* 1. Arena 선택: 멀티스레드 환경에서 경합 최소화 */
    mstate ar_ptr = arena_get();

    /* 2. Arena 뮤텍스 획득: 커널 컨텍스트 스위치 가능 */
    __libc_lock_lock(ar_ptr->mutex);

    /* 3. 적합한 bin 탐색
     *    - Fastbin (16-80 bytes)
     *    - Smallbin (< 512 bytes)
     *    - Largebin (>= 512 bytes)
     *    - Unsorted bin (최근 해제된 청크)
     */
    void* ptr = _int_malloc(ar_ptr, size);

    /* 4. 뮤텍스 해제 */
    __libc_lock_unlock(ar_ptr->mutex);

    return ptr;
}

이 과정에서 발생하는 비용:

  • Mutex 락: 멀티스레드 경합 시 커널 스케줄링 (~1000+ cycles)
  • Bin 탐색: 분기 예측 실패, 캐시 미스
  • 메타데이터 관리: 각 청크마다 헤더/푸터 저장
  • 병합(Coalescing): 인접 free 청크 병합 오버헤드

평균적으로 malloc 호출은 100ns~10us가 소요된다. 60fps 게임에서 프레임당 16ms 버짓을 고려하면, 수천 번의 할당만으로도 상당한 시간을 소비하게 된다.

1. Arena Allocator: 가장 빠른 할당

Arena allocator(또는 Linear allocator)는 가장 단순하면서도 강력한 전략이다. 핵심 아이디어는 포인터를 증가시키기만 하는 것이다.

동작 원리

typedef struct Arena {
    uint8_t*  base;       /* 메모리 블록 시작 주소 */
    size_t    size;       /* 전체 크기 */
    size_t    offset;     /* 현재 사용 오프셋 (bump pointer) */
} Arena;

void* arena_alloc(Arena* a, size_t alloc_size, size_t align) {
    /* 정렬 조정 */
    size_t aligned_offset = ALIGN_UP(a->offset, align);

    /* 공간 확인 */
    if (aligned_offset + alloc_size > a->size) {
        return NULL;  /* Out of memory */
    }

    /* 포인터 bump: 이게 전부다! */
    void* ptr = a->base + aligned_offset;
    a->offset = aligned_offset + alloc_size;

    return ptr;
}

성능 특성:

  • 할당: O(1)O(1) - 덧셈 2개, 비교 1개, 포인터 산술
  • 해제: 개별 해제 불가능
  • 전체 리셋: O(1)O(1) - 오프셋을 0으로 설정

이것이 얼마나 빠른지 측정해보겠다.

/* 벤치마크: 백만 개 할당 */
#include <time.h>

void benchmark_malloc() {
    clock_t start = clock();
    void* ptrs[1000000];

    for (int i = 0; i < 1000000; i++) {
        ptrs[i] = malloc(64);
    }

    clock_t end = clock();
    printf("malloc: %.3f ms\n",
           (double)(end - start) * 1000 / CLOCKS_PER_SEC);

    for (int i = 0; i < 1000000; i++) {
        free(ptrs[i]);
    }
}

void benchmark_arena() {
    Arena arena = arena_create(64 * 1000000);
    clock_t start = clock();

    for (int i = 0; i < 1000000; i++) {
        arena_alloc(&arena, 64, 16);
    }

    clock_t end = clock();
    printf("arena: %.3f ms\n",
           (double)(end - start) * 1000 / CLOCKS_PER_SEC);

    arena_destroy(&arena);
}

실측 결과 (Intel i7-12700K):

  • malloc: ~150ms
  • arena: ~5ms

30배 차이이다. Arena는 락도, 분기도, 메타데이터도 없다. 순수한 포인터 산술만으로 할당을 완료한다.

완전한 구현

정렬(alignment)을 올바르게 처리하는 완전한 구현이다.

/* 정렬 매크로 */
#define ALIGN_UP(n, align) (((n) + (align) - 1) & ~((align) - 1))
#define DEFAULT_ALIGNMENT 16

/* Arena 생성 */
Arena* arena_create(size_t capacity) {
    Arena* a = malloc(sizeof(Arena));
    if (!a) return NULL;

    a->base = malloc(capacity);
    if (!a->base) {
        free(a);
        return NULL;
    }

    a->size = capacity;
    a->offset = 0;
    return a;
}

/* Arena 해제 */
void arena_destroy(Arena* a) {
    if (!a) return;
    free(a->base);
    free(a);
}

/* 전체 리셋: 모든 할당을 한 번에 해제 */
void arena_reset(Arena* a) {
    a->offset = 0;

    /* 디버그 모드: 메모리 초기화로 use-after-free 감지 */
    #ifdef DEBUG
    memset(a->base, 0xCD, a->offset);
    #endif
}

/* 정렬된 할당 */
void* arena_alloc_aligned(Arena* a, size_t size, size_t align) {
    size_t aligned_offset = ALIGN_UP(a->offset, align);

    if (aligned_offset + size > a->size) {
        return NULL;
    }

    void* ptr = a->base + aligned_offset;
    a->offset = aligned_offset + size;

    return ptr;
}

/* 편의 함수: 기본 정렬 */
#define arena_alloc(a, size) arena_alloc_aligned(a, size, DEFAULT_ALIGNMENT)

Temporary Arena Memory Pattern

Arena의 진정한 힘은 중첩된 스코프 관리에서 나타난다. Savepoint 패턴을 사용하면 부분적인 해제가 가능하다.

typedef struct Temp_Arena_Memory {
    Arena*  arena;
    size_t  saved_offset;
} Temp_Arena_Memory;

Temp_Arena_Memory temp_arena_begin(Arena* a) {
    Temp_Arena_Memory temp;
    temp.arena = a;
    temp.saved_offset = a->offset;
    return temp;
}

void temp_arena_end(Temp_Arena_Memory temp) {
    temp.arena->offset = temp.saved_offset;
}

이 패턴의 강력함을 실제 예제로 확인해보자.

/* 프레임 단위 할당: 게임 엔진의 전형적인 패턴 */
void game_frame_update(Arena* frame_arena, Arena* permanent_arena) {
    /* 프레임 시작: 이전 프레임 데이터 전체 삭제 */
    arena_reset(frame_arena);

    /* 임시 계산용 메모리 */
    Temp_Arena_Memory temp = temp_arena_begin(frame_arena);

    /* View-Projection 행렬 계산 */
    float* view_matrix = arena_alloc(frame_arena, 16 * sizeof(float));
    float* proj_matrix = arena_alloc(frame_arena, 16 * sizeof(float));
    calculate_matrices(view_matrix, proj_matrix);

    /* 컬링용 frustum */
    Frustum* frustum = arena_alloc(frame_arena, sizeof(Frustum));
    build_frustum(view_matrix, proj_matrix, frustum);

    /* 보이는 객체만 렌더링 리스트에 추가 */
    RenderCommand* commands =
        arena_alloc(permanent_arena, MAX_OBJECTS * sizeof(RenderCommand));
    int command_count = cull_and_build_commands(frustum, commands);

    /* 계산 완료: frustum, 행렬 메모리 즉시 해제 */
    temp_arena_end(temp);

    /* 렌더링 커맨드는 permanent에 있으므로 살아있음 */
    submit_render_commands(commands, command_count);
}

이 패턴을 파싱에 적용하면 더욱 명확해진다.

/* 컴파일러 프론트엔드 예제 */
AST* parse_file(const char* filename, Arena* arena) {
    Temp_Arena_Memory temp = temp_arena_begin(arena);

    /* 토큰 버퍼: 파싱 중에만 필요 */
    Token* tokens = arena_alloc(arena, MAX_TOKENS * sizeof(Token));
    int token_count = tokenize(filename, tokens);

    /* AST 노드들: 파싱 후에도 유지되어야 함 */
    AST* ast = parse_tokens(tokens, token_count, arena);

    /* 토큰 버퍼만 해제, AST는 유지 */
    temp_arena_end(temp);

    return ast;
}

핵심 통찰: temp_arena_end()는 offset을 복원한다. temp 이전에 할당된 AST는 영향을 받지 않고, temp 이후에 할당된 tokens만 해제된다.

언제 Arena를 사용할까?

시나리오왜 적합한가
프레임 데이터60fps에서 매 16ms마다 생성/삭제
파싱토큰, AST 노드 등 단계별 수명
레벨 로딩레벨 전환 시 전체 데이터 폐기
문자열 빌더JSON 생성, 로그 메시지 조합
임시 계산행렬 연산, 중간 버퍼

장점:

  • 극도로 빠른 할당 (~5ns, CPU 사이클 10개 이하)
  • 캐시 친화적 (순차 메모리 접근)
  • 단편화 완전 제거
  • 메모리 누수 걱정 없음

단점:

  • 개별 해제 불가능 (전체 또는 savepoint 단위)
  • 최대 사용량 기준으로 메모리 예약 필요

2. Pool Allocator: 고정 크기 객체의 재사용

Pool allocator는 동일한 크기의 객체를 빠르게 할당하고 해제한다. 게임 엔진의 파티클 시스템, ECS 아키텍처의 컴포넌트, 네트워크 패킷 버퍼 등에 이상적이다.

Free List 기반 설계

Pool의 핵심은 인플레이스 free list이다. Free 블록은 사용되지 않으므로, 블록 자체를 linked list 노드로 활용한다.

typedef struct Pool {
    uint8_t*  memory;        /* 전체 메모리 블록 */
    void*     free_list;     /* 다음 free 블록 포인터 */
    size_t    chunk_size;    /* 각 블록 크기 */
    size_t    chunk_count;   /* 전체 블록 수 */
} Pool;

Pool* pool_create(size_t chunk_size, size_t chunk_count) {
    /* 최소 크기 보장: 포인터를 저장할 공간 필요 */
    if (chunk_size < sizeof(void*)) {
        chunk_size = sizeof(void*);
    }

    /* 정렬 조정 */
    chunk_size = ALIGN_UP(chunk_size, DEFAULT_ALIGNMENT);

    Pool* pool = malloc(sizeof(Pool));
    pool->memory = malloc(chunk_size * chunk_count);
    pool->chunk_size = chunk_size;
    pool->chunk_count = chunk_count;

    /* Free list 초기화: 각 블록을 linked list로 연결 */
    pool->free_list = NULL;
    for (size_t i = 0; i < chunk_count; i++) {
        void* chunk = pool->memory + i * chunk_size;
        *(void**)chunk = pool->free_list;  /* 블록 첫 8바이트에 next 포인터 */
        pool->free_list = chunk;
    }

    return pool;
}

메모리 레이아웃을 시각화하면:

초기 상태 (모두 free):

free_list →Block 0 →Block 1 →Block 2
↓[ptr][ptr][NULL]

Block 0 할당 후: free_list → Block 1 → Block 2 → NULL

Block 1 할당 후: free_list → Block 2 → NULL

Block 0 해제 후 (LIFO): free_list → Block 0 → Block 2 → NULL

할당과 해제

void* pool_alloc(Pool* pool) {
    if (pool->free_list == NULL) {
        return NULL;  /* Pool 고갈 */
    }

    /* Free list 헤드 꺼내기 */
    void* ptr = pool->free_list;
    pool->free_list = *(void**)ptr;

    return ptr;
}

void pool_free(Pool* pool, void* ptr) {
    if (ptr == NULL) return;

    /* Free list 헤드에 추가 (LIFO) */
    *(void**)ptr = pool->free_list;
    pool->free_list = ptr;
}

void pool_destroy(Pool* pool) {
    if (!pool) return;
    free(pool->memory);
    free(pool);
}

두 함수 모두 포인터 조작 3개 이하로 완료된다. 분기, 락, 메타데이터 탐색이 전혀 없다.

실전 예제: 파티클 시스템

typedef struct Particle {
    float position[3];
    float velocity[3];
    float color[4];
    float lifetime;
    float size;
} Particle;

/* 파티클 풀 생성: 최대 10,000개 */
Pool* particle_pool = pool_create(sizeof(Particle), 10000);

/* 파티클 발생 */
void emit_particle(float x, float y, float z) {
    Particle* p = pool_alloc(particle_pool);
    if (!p) {
        /* Pool 고갈: 가장 오래된 파티클 재사용 등의 전략 */
        return;
    }

    p->position[0] = x;
    p->position[1] = y;
    p->position[2] = z;
    p->lifetime = 5.0f;
    p->size = 1.0f;
}

/* 파티클 업데이트 */
void update_particles(Particle** active_particles, int* count, float dt) {
    for (int i = 0; i < *count; i++) {
        Particle* p = active_particles[i];
        p->lifetime -= dt;

        if (p->lifetime <= 0.0f) {
            /* 수명 종료: Pool에 반환 */
            pool_free(particle_pool, p);

            /* 배열에서 제거 (swap-and-pop) */
            active_particles[i] = active_particles[*count - 1];
            (*count)--;
            i--;
        } else {
            /* 위치 업데이트 */
            p->position[0] += p->velocity[0] * dt;
            p->position[1] += p->velocity[1] * dt;
            p->position[2] += p->velocity[2] * dt;
        }
    }
}

캐시 지역성의 위력

Pool allocator의 숨겨진 장점은 캐시 지역성이다. 모든 Particle이 연속된 메모리에 있으므로:

/* malloc 버전: 포인터가 힙 전체에 흩어짐 */
Particle** particles_malloc = malloc(10000 * sizeof(Particle*));
for (int i = 0; i < 10000; i++) {
    particles_malloc[i] = malloc(sizeof(Particle));  /* 임의 위치 */
}

/* 업데이트: 캐시 미스 빈번 */
for (int i = 0; i < 10000; i++) {
    update_particle(particles_malloc[i]);  /* 각 접근마다 캐시 미스 가능 */
}

/* Pool 버전: 모든 파티클이 연속됨 */
Particle* particles_pool = (Particle*)particle_pool->memory;

/* 업데이트: 순차 접근, 프리페칭 효과 */
for (int i = 0; i < 10000; i++) {
    update_particle(&particles_pool[i]);  /* 캐시 라인 공유 */
}

실측 성능 (Intel i7-12700K, 10,000개 파티클):

  • malloc 버전: ~2000 cycles (캐시 미스율 30%)
  • Pool 버전: ~500 cycles (캐시 미스율 5%)

4배 차이는 순전히 메모리 레이아웃에서 비롯된다.

언제 Pool을 사용할까?

시나리오왜 적합한가
파티클 시스템수천 개의 동일 구조체 생성/소멸
ECS 컴포넌트TransformComponent, RenderComponent 등
네트워크 패킷송수신 버퍼 재사용
이벤트 큐Event 객체 할당
물리 시뮬레이션RigidBody, Collider 객체

장점:

  • O(1)O(1) 할당/해제
  • 단편화 완전 제거
  • 캐시 지역성 극대화
  • 메모리 버짓 명확 (chunk_size × chunk_count)

단점:

  • 크기 고정
  • Pool 고갈 시 할당 실패

3. Stack Allocator: LIFO 제약의 활용

Stack allocator는 LIFO(Last-In-First-Out) 순서로만 해제할 수 있다. 이 제약이 강해 보이지만, 많은 알고리즘이 자연스럽게 LIFO 패턴을 따른다.

마커 기반 롤백

가장 실용적인 Stack allocator는 마커(savepoint)를 사용한다.

typedef struct Stack_Allocator {
    uint8_t*  base;
    size_t    size;
    size_t    offset;
} Stack_Allocator;

typedef size_t Stack_Marker;

/* 마커 저장 */
Stack_Marker stack_get_marker(Stack_Allocator* sa) {
    return sa->offset;
}

/* 마커로 롤백 */
void stack_free_to_marker(Stack_Allocator* sa, Stack_Marker marker) {
    sa->offset = marker;
}

/* 할당 */
void* stack_alloc(Stack_Allocator* sa, size_t size, size_t align) {
    size_t aligned_offset = ALIGN_UP(sa->offset, align);

    if (aligned_offset + size > sa->size) {
        return NULL;
    }

    void* ptr = sa->base + aligned_offset;
    sa->offset = aligned_offset + size;

    return ptr;
}

실전 예제: A* 경로 탐색

/* A* 알고리즘의 임시 메모리 할당 */
Path* find_path(Grid* grid, Point start, Point goal,
                Stack_Allocator* stack) {
    Stack_Marker marker = stack_get_marker(stack);

    /* Open/Closed set: 탐색 중에만 필요 */
    AStarNode* open_set = stack_alloc(stack,
        grid->width * grid->height * sizeof(AStarNode), 16);
    bool* closed_set = stack_alloc(stack,
        grid->width * grid->height * sizeof(bool), 16);

    /* A* 알고리즘 실행 */
    int path_length = astar_search(grid, start, goal,
                                   open_set, closed_set);

    /* 경로 결과: 영구 메모리에 복사 */
    Path* result = malloc(sizeof(Path) + path_length * sizeof(Point));
    memcpy(result->points, /* ... */);

    /* 임시 메모리 전체 해제 */
    stack_free_to_marker(stack, marker);

    return result;
}

헤더 기반 LIFO 검증

순서 위반을 감지하려면 각 할당마다 헤더를 추가한다.

typedef struct Alloc_Header {
    size_t prev_offset;
    size_t padding;
} Alloc_Header;

void* stack_alloc_with_header(Stack_Allocator* sa, size_t size, size_t align) {
    size_t current_offset = sa->offset;
    size_t header_size = sizeof(Alloc_Header);

    /* 헤더 + 정렬 패딩 계산 */
    size_t aligned_offset = ALIGN_UP(current_offset + header_size, align);
    size_t padding = aligned_offset - current_offset - header_size;

    if (aligned_offset + size > sa->size) {
        return NULL;
    }

    /* 헤더 저장 */
    Alloc_Header* header = (Alloc_Header*)(sa->base + current_offset);
    header->prev_offset = sa->prev_offset;
    header->padding = padding;

    /* 오프셋 업데이트 */
    sa->prev_offset = current_offset;
    sa->offset = aligned_offset + size;

    return sa->base + aligned_offset;
}

void stack_free_with_check(Stack_Allocator* sa, void* ptr) {
    if (ptr == NULL) return;

    /* 헤더 복원 */
    Alloc_Header* header = (Alloc_Header*)((uint8_t*)ptr - sizeof(Alloc_Header));

    /* LIFO 검증 */
    size_t expected_offset = (uint8_t*)ptr - sa->base;
    if (expected_offset != sa->prev_offset + sizeof(Alloc_Header) + header->padding) {
        fprintf(stderr, "ERROR: Stack allocator out-of-order free!\n");
        abort();
    }

    /* 오프셋 복원 */
    sa->offset = header->prev_offset;
    sa->prev_offset = header->prev_offset;
}

언제 Stack을 사용할까?

  • 함수 스코프 할당: 함수 진입 시 마커, 종료 시 롤백
  • 재귀 알고리즘: DFS, 백트래킹 등
  • 레벨 로딩: 섹션별 할당/해제
  • AI 경로 탐색: Open/Closed set, 임시 계산

4. Buddy Allocator: 2의 거듭제곱 분할

Buddy allocator는 외부 단편화를 줄이면서 다양한 크기를 지원한다. Linux 커널의 물리 페이지 할당자가 대표적인 예이다.

분할과 병합 메커니즘

메모리를 2의 거듭제곱 크기로 재귀적으로 분할한다.

초기: 1MB 블록
[                    1MB                    ]

64KB 할당 요청:
1MB -> 512KB + 512KB
512KB -> 256KB + 256KB
256KB -> 128KB + 128KB
128KB -> 64KB(할당) + 64KB(free)

결과:
[64KB][64KB][128KB][256KB][512KB]
 사용  free   free   free   free

구조체 정의

#define MAX_ORDER 20  /* 2^20 = 1MB */

typedef struct Buddy_Allocator {
    uint8_t* base;
    size_t   size;
    void*    free_lists[MAX_ORDER + 1];  /* 각 order별 free list */
} Buddy_Allocator;

/* 크기를 order로 변환 */
static int size_to_order(size_t size) {
    int order = 0;
    size_t s = 1;
    while (s < size) {
        s <<= 1;
        order++;
    }
    return order;
}

/* Buddy 주소 계산: XOR 트릭 */
static void* get_buddy(void* block, int order, uint8_t* base) {
    size_t offset = (uint8_t*)block - base;
    size_t buddy_offset = offset ^ (1ULL << order);
    return base + buddy_offset;
}

핵심 통찰: Buddy 주소는 XOR로 계산된다. 블록 A와 그 buddy B는 order 비트만 다르다.

Example: order=3 (8바이트 블록)
Block A offset: 0b00010000 (16)
Buddy B offset: 0b00011000 (24)  <- 3번째 비트만 flip
XOR: 16 ^ 8 = 24

할당 알고리즘

void* buddy_alloc(Buddy_Allocator* ba, size_t size) {
    int order = size_to_order(size);

    /* 적합한 블록 찾기 */
    int current_order = order;
    while (current_order <= MAX_ORDER && ba->free_lists[current_order] == NULL) {
        current_order++;
    }

    if (current_order > MAX_ORDER) {
        return NULL;  /* Out of memory */
    }

    /* 블록 꺼내기 */
    void* block = ba->free_lists[current_order];
    ba->free_lists[current_order] = *(void**)block;

    /* 분할 (splitting) */
    while (current_order > order) {
        current_order--;
        size_t buddy_size = 1ULL << current_order;
        void* buddy = (uint8_t*)block + buddy_size;

        /* Buddy를 free list에 추가 */
        *(void**)buddy = ba->free_lists[current_order];
        ba->free_lists[current_order] = buddy;
    }

    return block;
}

병합(Coalescing) 메커니즘

void buddy_free(Buddy_Allocator* ba, void* ptr, size_t size) {
    int order = size_to_order(size);

    /* Buddy 병합 시도 */
    while (order < MAX_ORDER) {
        void* buddy = get_buddy(ptr, order, ba->base);

        /* Free list에서 buddy 찾기 */
        void** prev = &ba->free_lists[order];
        void* current = *prev;
        bool found = false;

        while (current != NULL) {
            if (current == buddy) {
                /* Buddy 제거 */
                *prev = *(void**)current;
                found = true;
                break;
            }
            prev = (void**)current;
            current = *(void**)current;
        }

        if (!found) break;  /* Buddy가 사용 중 */

        /* 병합: 낮은 주소를 유지 */
        if (buddy < ptr) ptr = buddy;
        order++;
    }

    /* Free list에 추가 */
    *(void**)ptr = ba->free_lists[order];
    ba->free_lists[order] = ptr;
}

Linux 커널의 Buddy System

Linux는 물리 페이지 할당에 Buddy system을 사용한다.

/* include/linux/mmzone.h */
struct free_area {
    struct list_head  free_list[MIGRATE_TYPES];
    unsigned long     nr_free;
};

struct zone {
    struct free_area  free_area[MAX_ORDER];
    /* ... */
};

/* mm/page_alloc.c */
struct page *__alloc_pages(gfp_t gfp_mask, unsigned int order,
                          int preferred_nid, nodemask_t *nodemask);

주요 특징:

  • Order 0~10 (4KB ~ 4MB)
  • MIGRATE_TYPES: 단편화 방지 전략
    • UNMOVABLE: 커널 데이터
    • MOVABLE: 사용자 페이지
    • RECLAIMABLE: 페이지 캐시
  • Compaction: 물리 메모리 조각 모음

Buddy allocator는 외부 단편화를 크게 줄인다. 50% 규칙: 평균적으로 내부 단편화는 28% 정도이다 (2의 거듭제곱 제약 때문).

5. Slab Allocator: 객체 캐싱

Slab allocator는 Pool allocator를 확장하여 생성자/소멸자 비용을 회피한다.

객체 캐싱 원리

일반 Pool:

할당 -> 객체 생성자 호출 -> 사용 -> 소멸자 호출 -> 해제

Slab:

[초기화]
모든 객체에 생성자 호출 (한 번만)

[런타임]
할당 -> 사용 -> 해제 (생성자/소멸자 호출 없음!)
       ↑____________________________↓

핵심 아이디어: Free 상태 객체도 "구성된(constructed)" 상태를 유지한다.

구현

typedef struct Slab {
    void*      objects;       /* 객체 배열 */
    void*      free_list;     /* Free 객체 리스트 */
    size_t     object_size;
    size_t     object_count;
    void     (*ctor)(void*);  /* 생성자 */
    void     (*dtor)(void*);  /* 소멸자 */
} Slab;

Slab* slab_create(size_t object_size, size_t count,
                  void (*ctor)(void*), void (*dtor)(void*)) {
    Slab* slab = malloc(sizeof(Slab));
    slab->objects = malloc(object_size * count);
    slab->object_size = object_size;
    slab->object_count = count;
    slab->ctor = ctor;
    slab->dtor = dtor;

    /* Free list 초기화 + 생성자 호출 */
    slab->free_list = NULL;
    for (size_t i = 0; i < count; i++) {
        void* obj = (uint8_t*)slab->objects + i * object_size;

        /* 생성자 호출: 초기화 완료 */
        if (slab->ctor) {
            slab->ctor(obj);
        }

        *(void**)obj = slab->free_list;
        slab->free_list = obj;
    }

    return slab;
}

void* slab_alloc(Slab* slab) {
    if (slab->free_list == NULL) return NULL;

    void* obj = slab->free_list;
    slab->free_list = *(void**)obj;

    /* 생성자 재호출 없음! */
    return obj;
}

void slab_free(Slab* slab, void* obj) {
    /* 소멸자 호출하지 않음! */
    *(void**)obj = slab->free_list;
    slab->free_list = obj;
}

void slab_destroy(Slab* slab) {
    /* 모든 객체의 소멸자 호출 */
    if (slab->dtor) {
        for (size_t i = 0; i < slab->object_count; i++) {
            void* obj = (uint8_t*)slab->objects + i * slab->object_size;
            slab->dtor(obj);
        }
    }

    free(slab->objects);
    free(slab);
}

실전 예제: SSL 연결 풀

typedef struct Connection {
    int socket_fd;
    SSL_CTX* ssl_ctx;
    char buffer[4096];
} Connection;

void connection_ctor(void* ptr) {
    Connection* conn = ptr;
    conn->socket_fd = -1;

    /* 비용 큰 초기화: TLS context 생성 */
    conn->ssl_ctx = SSL_CTX_new(TLS_method());
    SSL_CTX_set_options(conn->ssl_ctx, SSL_OP_NO_SSLv2 | SSL_OP_NO_SSLv3);
    SSL_CTX_set_cipher_list(conn->ssl_ctx, "HIGH:!aNULL:!MD5");

    memset(conn->buffer, 0, sizeof(conn->buffer));
}

void connection_dtor(void* ptr) {
    Connection* conn = ptr;
    if (conn->ssl_ctx) {
        SSL_CTX_free(conn->ssl_ctx);  /* 비용 큰 정리 */
    }
}

/* Slab 생성 */
Slab* conn_slab = slab_create(sizeof(Connection), 100,
                              connection_ctor, connection_dtor);

/* 연결 처리 */
void handle_client(int client_fd) {
    /* 할당: SSL_CTX_new() 재호출 안 함! */
    Connection* conn = slab_alloc(conn_slab);
    conn->socket_fd = client_fd;

    /* SSL 핸드셰이크 및 데이터 처리 */
    process_connection(conn);

    /* 해제: SSL_CTX_free() 호출 안 함! */
    close(conn->socket_fd);
    slab_free(conn_slab, conn);
}

성능 측정:

  • SSL_CTX_new() + 설정: ~500us
  • 연결 100개 처리 시:
    • malloc 버전: 50ms (생성자/소멸자 100번)
    • Slab 버전: 5ms (생성자/소멸자 1번)

10배 차이는 초기화 비용 회피에서 나온다.

Linux kmem_cache

Linux 커널의 slab allocator는 inode, dentry, task_struct 등 커널 객체에 사용된다.

/* include/linux/slab.h */

struct kmem_cache *kmem_cache_create(
    const char *name,
    unsigned int size,
    unsigned int align,
    slab_flags_t flags,
    void (*ctor)(void *)  /* 생성자 */
);

void *kmem_cache_alloc(struct kmem_cache *cachep, gfp_t flags);
void kmem_cache_free(struct kmem_cache *cachep, void *objp);
void kmem_cache_destroy(struct kmem_cache *cachep);

실제 사용 예시:

/* fs/inode.c */
static struct kmem_cache *inode_cachep;

void __init inode_init_early(void) {
    inode_cachep = kmem_cache_create(
        "inode_cache",
        sizeof(struct inode),
        0,
        (SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD),
        init_once  /* 생성자: inode 초기화 */
    );
}

struct inode *alloc_inode(struct super_block *sb) {
    /* init_once()는 이미 호출됨 */
    struct inode *inode = kmem_cache_alloc(inode_cachep, GFP_KERNEL);
    return inode;
}

게임 엔진에서의 실제 사용

이론을 실전으로 옮겨보자. 전형적인 게임 엔진의 메모리 레이아웃이다.

메모리 아키텍처

typedef struct Game_Memory {
    /* 영구 데이터: 레벨 전환까지 유지 */
    Arena  permanent_arena;    /* 256MB: 메시, 텍스처, 애니메이션 */

    /* 임시 데이터: 매 프레임 리셋 */
    Arena  transient_arena;    /* 128MB: 행렬, 중간 계산 */

    /* 객체 풀 */
    Pool   entity_pool;        /* 16MB: 최대 100,000 엔티티 */
    Pool   particle_pool;      /* 32MB: 최대 1,000,000 파티클 */
    Pool   render_cmd_pool;    /* 8MB: 렌더링 커맨드 */

    /* 스택 */
    Stack_Allocator ai_stack;  /* 16MB: AI 경로 탐색 임시 버퍼 */
} Game_Memory;

/* 초기화: 게임 시작 시 한 번 */
Game_Memory* init_game_memory(void) {
    Game_Memory* mem = malloc(sizeof(Game_Memory));

    mem->permanent_arena = arena_create(256 * 1024 * 1024);
    mem->transient_arena = arena_create(128 * 1024 * 1024);
    mem->entity_pool = pool_create(sizeof(Entity), 100000);
    mem->particle_pool = pool_create(sizeof(Particle), 1000000);
    mem->render_cmd_pool = pool_create(sizeof(RenderCommand), 50000);
    mem->ai_stack = stack_create(16 * 1024 * 1024);

    /* 총 메모리: 456MB (예측 가능!) */
    return mem;
}

프레임 루프

void game_frame(Game_Memory* mem, float dt) {
    /* 1. 프레임 시작: 임시 메모리 리셋 */
    arena_reset(&mem->transient_arena);

    /* 2. 카메라 행렬 계산 (transient) */
    Temp_Arena_Memory temp = temp_arena_begin(&mem->transient_arena);

    float* view_matrix = arena_alloc(&mem->transient_arena, 16 * sizeof(float));
    float* proj_matrix = arena_alloc(&mem->transient_arena, 16 * sizeof(float));
    calculate_camera_matrices(view_matrix, proj_matrix);

    /* 3. 엔티티 업데이트 (pool에서 할당/해제) */
    for (int i = 0; i < active_entity_count; i++) {
        Entity* entity = active_entities[i];
        update_entity(entity, dt);

        if (entity->should_spawn_particle) {
            Particle* p = pool_alloc(&mem->particle_pool);
            if (p) {
                init_particle(p, entity->position);
            }
        }
    }

    /* 4. AI 경로 탐색 (stack) */
    for (int i = 0; i < ai_agent_count; i++) {
        Stack_Marker marker = stack_get_marker(&mem->ai_stack);

        Path* path = find_path_astar(&mem->ai_stack,
                                     agents[i].position,
                                     agents[i].target);

        execute_path(agents[i], path);

        stack_free_to_marker(&mem->ai_stack, marker);
    }

    /* 5. 렌더링 커맨드 생성 (render_cmd_pool) */
    for (int i = 0; i < visible_object_count; i++) {
        RenderCommand* cmd = pool_alloc(&mem->render_cmd_pool);
        if (cmd) {
            build_render_command(cmd, visible_objects[i]);
        }
    }

    /* 6. 렌더링 */
    render_scene();

    /* 7. 렌더링 커맨드 풀 리셋 */
    pool_reset(&mem->render_cmd_pool);  /* 모든 커맨드 해제 */

    /* 8. 임시 메모리 해제 */
    temp_arena_end(temp);
}

레벨 로딩

void load_level(const char* level_name, Game_Memory* mem) {
    /* 이전 레벨 데이터 전체 삭제 */
    arena_reset(&mem->permanent_arena);

    /* 레벨 파일 파싱 */
    Temp_Arena_Memory temp = temp_arena_begin(&mem->permanent_arena);

    char* level_json = arena_alloc(&mem->permanent_arena, 10 * 1024 * 1024);
    load_file(level_name, level_json);

    JSON* parsed = parse_json(level_json, &mem->permanent_arena);

    /* 메시 로딩 (permanent에 영구 저장) */
    for (int i = 0; i < parsed->mesh_count; i++) {
        Mesh* mesh = arena_alloc(&mem->permanent_arena, sizeof(Mesh));
        load_mesh(parsed->meshes[i], mesh, &mem->permanent_arena);
    }

    /* JSON 파싱 데이터 해제, 메시는 유지 */
    temp_arena_end(temp);
}

디버깅과 프로파일링

/* 디버그 래퍼 */
typedef struct Arena_Stats {
    Arena base;
    const char* name;
    size_t peak_usage;
    size_t total_allocated;
    size_t allocation_count;
} Arena_Stats;

void* arena_alloc_debug(Arena_Stats* a, size_t size,
                       const char* file, int line) {
    void* ptr = arena_alloc(&a->base, size);

    a->total_allocated += size;
    a->allocation_count++;

    if (a->base.offset > a->peak_usage) {
        a->peak_usage = a->base.offset;
    }

    #ifdef VERBOSE_DEBUG
    printf("[%s] Alloc %zu bytes at %s:%d (peak: %zu / %zu = %.1f%%)\n",
           a->name, size, file, line,
           a->peak_usage, a->base.size,
           100.0 * a->peak_usage / a->base.size);
    #endif

    return ptr;
}

/* 프레임 종료 시 통계 출력 */
void print_memory_stats(Game_Memory* mem) {
    printf("=== Memory Statistics ===\n");
    printf("Permanent: %zu / %zu (%.1f%%)\n",
           mem->permanent_arena.offset,
           mem->permanent_arena.size,
           100.0 * mem->permanent_arena.offset / mem->permanent_arena.size);
    printf("Transient: %zu peak / %zu (%.1f%%)\n",
           mem->transient_stats.peak_usage,
           mem->transient_arena.size,
           100.0 * mem->transient_stats.peak_usage / mem->transient_arena.size);
    printf("Entity pool: %d / %d used\n",
           pool_used_count(&mem->entity_pool),
           mem->entity_pool.chunk_count);
}

출력 예시:

=== Memory Statistics ===
Permanent: 187,432,960 / 268,435,456 (69.8%)
Transient: 8,388,608 peak / 134,217,728 (6.2%)
Entity pool: 3,456 / 100,000 used
Particle pool: 12,789 / 1,000,000 used
Render cmd pool: 1,234 / 50,000 used

할당자 선택 가이드

사용 패턴권장 할당자시간 복잡도공간 오버헤드
프레임 단위 생성/삭제ArenaO(1)O(1) 할당, O(1)O(1) 리셋0%
같은 크기, 빈번한 재사용PoolO(1)O(1) 할당/해제8 bytes/chunk
스코프 기반 LIFOStackO(1)O(1) 할당/롤백0-16 bytes/alloc
다양한 크기, 병합 필요BuddyO(log⁡n)O(\log n) 할당/해제~28% 내부 단편화
초기화 비용 큼SlabO(1)O(1) 할당/해제생성자 1회만
예측 불가능한 패턴mallocO(log⁡n)O(\log n) - O(n)O(n)메타데이터 16-32 bytes

성능 비교: 실측 데이터

테스트 환경: Intel i7-12700K, 64GB RAM, Ubuntu 22.04

백만 개 할당 벤치마크

/* 64 바이트 객체를 100만 개 할당 */
void benchmark_allocators() {
    /* malloc */
    clock_t start = clock();
    void* ptrs[1000000];
    for (int i = 0; i < 1000000; i++) {
        ptrs[i] = malloc(64);
    }
    clock_t end = clock();
    printf("malloc: %.2f ms\n", (end - start) * 1000.0 / CLOCKS_PER_SEC);
    for (int i = 0; i < 1000000; i++) free(ptrs[i]);

    /* Arena */
    Arena arena = arena_create(64 * 1000000);
    start = clock();
    for (int i = 0; i < 1000000; i++) {
        arena_alloc(&arena, 64);
    }
    end = clock();
    printf("Arena: %.2f ms\n", (end - start) * 1000.0 / CLOCKS_PER_SEC);

    /* Pool */
    Pool* pool = pool_create(64, 1000000);
    start = clock();
    for (int i = 0; i < 1000000; i++) {
        pool_alloc(pool);
    }
    end = clock();
    printf("Pool: %.2f ms\n", (end - start) * 1000.0 / CLOCKS_PER_SEC);
}

결과:

할당자할당 시간해제 시간총 시간
malloc152 ms98 ms250 ms
Arena4.2 ms0.001 ms4.2 ms
Pool8.7 ms6.3 ms15 ms

캐시 지역성 테스트

/* 10,000개 파티클 업데이트 */
typedef struct Particle {
    float pos[3], vel[3];
    float lifetime;
} Particle;

/* malloc 버전 */
Particle** particles_malloc = malloc(10000 * sizeof(Particle*));
for (int i = 0; i < 10000; i++) {
    particles_malloc[i] = malloc(sizeof(Particle));
}

/* Pool 버전 */
Pool* pool = pool_create(sizeof(Particle), 10000);
Particle* particles_pool = (Particle*)pool->memory;

/* 업데이트 벤치마크 */
for (int iter = 0; iter < 1000; iter++) {
    for (int i = 0; i < 10000; i++) {
        update_particle(particles_malloc[i]);  /* 캐시 미스 빈번 */
    }
}

for (int iter = 0; iter < 1000; iter++) {
    for (int i = 0; i < 10000; i++) {
        update_particle(&particles_pool[i]);  /* 순차 접근 */
    }
}

결과 (perf stat 측정):

버전시간캐시 미스율IPC
malloc2.3초28.3%1.2
Pool0.6초4.7%3.1

Pool 버전이 3.8배 빠르다. 캐시 미스율을 1/6로 줄인 결과이다.

하이브리드 전략

실제 게임 엔진은 여러 할당자를 조합한다. Unreal Engine의 메모리 아키텍처를 단순화하면:

/* Unreal Engine 스타일 (단순화) */
class FMemoryManager {
public:
    /* 일반 목적 */
    FMallocBinned2  binned_malloc;     /* jemalloc 스타일 */

    /* 스레드별 임시 메모리 */
    TLS_VARIABLE FMemStack  thread_stack;

    /* 객체 풀 */
    TObjectPool<AActor>     actor_pool;
    TObjectPool<UComponent> component_pool;

    /* 대용량 할당 (>1MB) */
    FMallocAnsi  large_malloc;         /* mmap 직접 호출 */

    void* Malloc(size_t size, uint32 alignment) {
        if (size > LARGE_ALLOC_THRESHOLD) {
            return large_malloc.Malloc(size);
        } else {
            return binned_malloc.Malloc(size, alignment);
        }
    }
};

전략:

  • 일반 할당: jemalloc 스타일 binned allocator
  • 임시 할당: 스레드 로컬 스택
  • 대용량: mmap 직접 사용 (커널 overhead 상쇄)
  • 자주 사용되는 타입: 전용 풀

마치며

커스텀 할당자는 제약을 활용하여 성능을 획득하는 전형적인 시스템 프로그래밍 기법이다.

할당자제약보상
Arena개별 해제 불가10배 빠른 할당
Pool크기 고정단편화 제거, 캐시 효율
StackLIFO 순서스코프 관리, 메모리 누수 방지
Buddy2의 거듭제곱병합 가능, 외부 단편화 감소
Slab타입 고정생성자/소멸자 회피

일반 목적 할당자(malloc)는 모든 경우를 처리해야 하므로 최적화 여지가 제한된다. 하지만 우리가 사용 패턴을 알고 있다면, 그 지식을 활용하여 극적인 성능 향상을 달성할 수 있다.

게임 엔진, 실시간 시스템, 임베디드 소프트웨어에서는 필수 기법이다. 다음과 같은 이점을 제공한다:

  1. 10~100배 빠른 할당/해제
  2. 캐시 효율 2~5배 향상
  3. 단편화 제거
  4. 예측 가능한 메모리 사용
  5. 정밀한 프로파일링과 디버깅

메모리 관리는 성능의 기초이다. 올바른 할당자를 선택하는 것은 알고리즘 최적화만큼이나 중요하다.

더 읽을거리

핵심 자료

  1. Ginger Bill's Memory Allocation Strategies

  2. Game Programming Patterns - Object Pool

  3. Linux Kernel Memory Management

  4. SLUB: The Unqueued Slab Allocator

게임 엔진 사례

  1. Game Engine Architecture (3rd Edition) - Jason Gregory

    • Chapter 5.2: Memory Management
    • Naughty Dog, Insomniac Games의 실제 사례

  2. EASTL (Electronic Arts Standard Template Library)

추가 학습 자료

  1. Writing a Memory Allocator - Dmitry Soshnikov

  2. jemalloc Design Document

  3. mimalloc: Free List Sharding in Action

  4. The Memory Management Reference

profile
REIN
RL Researcher, Video Game Developer
이전 포스트

Memory Architecture

다음 포스트

[시스템 프로그래밍 #3.5] 커스텀 할당자 보충 설명

0개의 댓글