메모리 할당자 설계 원리와 구현

개요

메모리 할당자는 동적 메모리 요청(malloc/new)을 처리하는 시스템입니다. 기본 할당자는 범용적이지만 게임처럼 성능이 중요한 환경에서는 목적에 맞는 커스텀 할당자로 GC 압력, 단편화, 캐시 미스를 줄일 수 있습니다.

---

1. 메모리 단편화

외부 단편화: 충분한 총 여유 메모리가 있지만 연속 공간이 부족
  [USED][FREE:10][USED][FREE:10][USED]
  → 15바이트 할당 불가 (각 FREE가 10바이트)

내부 단편화: 요청보다 큰 블록 할당으로 내부 공간 낭비
  8바이트 요청 → 16바이트 정렬로 할당 → 8바이트 낭비

---

2. 선형/스택 할당자 (가장 빠름)

class LinearAllocator {
    uint8_t* memory;
    size_t size;
    size_t offset = 0;

public:
    explicit LinearAllocator(size_t bytes)
        : memory(new uint8_t[bytes]), size(bytes) {}

    ~LinearAllocator() { delete[] memory; }

    void* Allocate(size_t bytes, size_t alignment = alignof(std::max_align_t)) {
        size_t aligned = (offset + alignment - 1) & ~(alignment - 1);
        if (aligned + bytes > size) return nullptr; // 공간 부족

        offset = aligned + bytes;
        return memory + aligned;
    }

    // 할당 해제: 전체 리셋만 가능
    void Reset() { offset = 0; }

    size_t Used() const { return offset; }
};

// 사용 예 (프레임당 임시 메모리)
LinearAllocator frameAlloc(4 * 1024 * 1024); // 4MB

void* data = frameAlloc.Allocate(1024);
// ... 프레임 끝에서:
frameAlloc.Reset(); // 전체 해제, O(1)

---

3. 풀 할당자 (고정 크기 빠른 할당)

template<typename T, size_t PoolSize = 1024>
class PoolAllocator {
    union Block {
        alignas(T) uint8_t data[sizeof(T)];
        Block* next;
    };

    Block pool[PoolSize];
    Block* freeList = nullptr;

public:
    PoolAllocator() {
        // 모든 블록을 프리 리스트에 연결
        for (size_t i = 0; i < PoolSize - 1; i++)
            pool[i].next = &pool[i + 1];
        pool[PoolSize - 1].next = nullptr;
        freeList = &pool[0];
    }

    T* Allocate() {
        if (!freeList) return nullptr;
        Block* block = freeList;
        freeList = freeList->next;
        return reinterpret_cast<T*>(block->data);
    }

    void Free(T* ptr) {
        Block* block = reinterpret_cast<Block*>(ptr);
        block->next = freeList;
        freeList = block;
    }
};

// 사용 — Enemy 풀
PoolAllocator<Enemy> enemyPool;
Enemy* e = enemyPool.Allocate();
new(e) Enemy(); // placement new로 생성자 호출
// ...
e->~Enemy();
enemyPool.Free(e);

---

4. 슬랩 할당자

// 크기별 풀을 유지 (8B, 16B, 32B, 64B, ...)
class SlabAllocator {
    static constexpr size_t BINS[] = {8,16,32,64,128,256,512,1024,2048,4096};
    std::vector<uint8_t*> freeLists[10]; // 각 크기별 프리 리스트

    int GetBinIndex(size_t size) {
        for (int i = 0; i < 10; i++)
            if (size <= BINS[i]) return i;
        return -1; // 너무 크면 시스템 malloc 사용
    }

public:
    void* Allocate(size_t size) {
        int bin = GetBinIndex(size);
        if (bin < 0) return malloc(size);

        if (!freeLists[bin].empty()) {
            void* ptr = freeLists[bin].back();
            freeLists[bin].pop_back();
            return ptr;
        }

        // 새 슬래브 할당
        return malloc(BINS[bin]);
    }

    void Free(void* ptr, size_t size) {
        int bin = GetBinIndex(size);
        if (bin < 0) { free(ptr); return; }

        freeLists[bin].push_back(static_cast<uint8_t*>(ptr));
    }
};

---

5. 커스텀 new/delete

// 클래스별 커스텀 할당자
class GameObject {
    static PoolAllocator<GameObject> pool;

public:
    static void* operator new(size_t size) {
        return pool.Allocate();
    }

    static void operator delete(void* ptr) {
        pool.Free(static_cast<GameObject*>(ptr));
    }
};

PoolAllocator<GameObject> GameObject::pool;

// 사용 — 풀에서 할당
auto* obj = new GameObject(); // pool.Allocate() 호출
delete obj;                   // pool.Free() 호출

---

6. 정렬 메모리

// SIMD 명령에는 16 또는 32바이트 정렬 필요
void* AllocAligned(size_t size, size_t alignment) {
    size_t totalSize = size + alignment - 1 + sizeof(void*);
    void* raw = malloc(totalSize);

    uintptr_t rawAddr = reinterpret_cast<uintptr_t>(raw) + sizeof(void*);
    uintptr_t alignedAddr = (rawAddr + alignment - 1) & ~(alignment - 1);

    // 원본 포인터 저장 (해제에 필요)
    reinterpret_cast<void**>(alignedAddr)[-1] = raw;

    return reinterpret_cast<void*>(alignedAddr);
}

void FreeAligned(void* ptr) {
    void* raw = reinterpret_cast<void**>(ptr)[-1];
    free(raw);
}

// C++17: std::aligned_alloc
void* simd_buf = std::aligned_alloc(32, 256); // 32바이트 정렬
std::free(simd_buf);

---

7. 게임 메모리 전략

// 게임 메모리 계층
class GameMemory {
    LinearAllocator frameAlloc;    // 프레임 임시 (매 프레임 리셋)
    LinearAllocator levelAlloc;    // 레벨 데이터 (레벨 전환 시 리셋)
    PoolAllocator<Particle> particles; // 파티클 풀
    SlabAllocator general;         // 일반 할당

public:
    void* AllocateFrameTemp(size_t size) {
        return frameAlloc.Allocate(size);
    }

    void EndFrame() { frameAlloc.Reset(); }
    void EndLevel() { levelAlloc.Reset(); }
};

---

정리

할당자	할당	해제	적합한 용도
선형	O(1)	O(1) 일괄	프레임 임시, 레벨 데이터
풀	O(1)	O(1)	고정 크기 객체 (파티클, 적)
슬랩	O(1)	O(1)	다양한 크기의 잦은 할당
범용(malloc)	O(log N)	O(log N)	일반 목적

참고 자료

• Game Programming Patterns — Object Pool
• jemalloc — Facebook 메모리 할당자