Pool Allocator 구현 — Fixed-Size Block과 O(1) 보장

1
ObjectPool<Order, 32> pool;
2

3
Order* o1 = pool.allocate();   // O(1)
4
Order* o2 = pool.allocate();
5
pool.deallocate(o1);            // O(1)
6

7
assert(pool.allocated() == 1);
8
assert(pool.available() == 31);

1
처음 상태:
2
storage: [block0][block1][block2][block3]
3
free_list_head → block0 → block1 → block2 → block3 → nullptr
4

5
block0 할당 후:
6
free_list_head → block1 → block2 → block3 → nullptr
7
반환된 block0의 메모리는 사용자가 사용
8

9
block0 해제 후:
10
free_list_head → block0 → block1 → block2 → block3 → nullptr
11
(또는 LIFO: block0 → block1 → block2 → ...)

1
template<typename T, size_t N>
2
class ObjectPool {
3
    // 각 슬롯 — T 또는 next pointer
4
    union Slot {
5
        alignas(T) std::byte storage[sizeof(T)];
6
        Slot* next;
7
    };
8

9
    Slot slots_[N];
10
    Slot* free_head_;
11
    size_t allocated_ = 0;
12

13
public:
14
    ObjectPool() {
15
        // 초기 free list 구성
16
        for (size_t i = 0; i < N - 1; ++i) {
17
            slots_[i].next = &slots_[i + 1];
18
        }
19
        slots_[N - 1].next = nullptr;
20
        free_head_ = &slots_[0];
21
    }
22

23
    T* allocate() noexcept {
24
        if (!free_head_) return nullptr;   // 고갈
25

26
        Slot* slot = free_head_;
27
        free_head_ = slot->next;
28
        ++allocated_;
29
        return reinterpret_cast<T*>(&slot->storage);
30
    }
31

32
    void deallocate(T* p) noexcept {
33
        if (!p) return;
34

35
        Slot* slot = reinterpret_cast<Slot*>(p);
36
        slot->next = free_head_;
37
        free_head_ = slot;
38
        --allocated_;
39
    }
40

41
    // 객체 생성 + 할당
42
    template<typename... Args>
43
    T* construct(Args&&... args) noexcept {
44
        T* p = allocate();
45
        if (p) new (p) T(std::forward<Args>(args)...);
46
        return p;
47
    }
48

49
    // 소멸 + 해제
50
    void destroy(T* p) noexcept {
51
        if (p) {
52
            p->~T();
53
            deallocate(p);
54
        }
55
    }
56

57
    size_t allocated() const { return allocated_; }
58
    size_t available() const { return N - allocated_; }
59
    bool empty() const { return allocated_ == 0; }
60
    bool full() const { return allocated_ == N; }
61
};

1
struct Order {
2
    int id;
3
    int quantity;
4
    float price;
5
    Order(int i, int q, float p) : id(i), quantity(q), price(p) {}
6
};
7

8
ObjectPool<Order, 32> order_pool;
9

10
void process_request(int id, int qty, float price) {
11
    auto* order = order_pool.construct(id, qty, price);
12
    if (!order) {
13
        log_error("order pool full");
14
        return;
15
    }
16

17
    // 처리
18
    process(order);
19

20
    order_pool.destroy(order);
21
}

1
template<typename T, size_t N>
2
class PoolUniquePtr {
3
    ObjectPool<T, N>* pool_;
4
    T* ptr_;
5

6
public:
7
    PoolUniquePtr(ObjectPool<T, N>* pool, T* ptr) : pool_(pool), ptr_(ptr) {}
8

9
    ~PoolUniquePtr() {
10
        if (ptr_) pool_->destroy(ptr_);
11
    }
12

13
    PoolUniquePtr(PoolUniquePtr&& other) noexcept
14
        : pool_(other.pool_), ptr_(other.ptr_) {
15
        other.ptr_ = nullptr;
16
    }
17

18
    PoolUniquePtr& operator=(PoolUniquePtr&& other) noexcept {
19
        if (this != &other) {
20
            if (ptr_) pool_->destroy(ptr_);
21
            pool_ = other.pool_;
22
            ptr_ = other.ptr_;
23
            other.ptr_ = nullptr;
24
        }
25
        return *this;
26
    }
27

28
    PoolUniquePtr(const PoolUniquePtr&) = delete;
29
    PoolUniquePtr& operator=(const PoolUniquePtr&) = delete;
30

31
    T* get() const { return ptr_; }
32
    T* operator->() const { return ptr_; }
33
    T& operator*() const { return *ptr_; }
34
    explicit operator bool() const { return ptr_ != nullptr; }
35
};
36

37
template<typename T, size_t N, typename... Args>
38
PoolUniquePtr<T, N> make_pool_unique(ObjectPool<T, N>& pool, Args&&... args) {
39
    return PoolUniquePtr<T, N>(&pool, pool.construct(std::forward<Args>(args)...));
40
}

1
ObjectPool<Order, 32> pool;
2

3
void process() {
4
    auto order = make_pool_unique(pool, 1, 100, 9.99f);
5
    if (!order) return;   // pool full
6

7
    order->process();
8
    // 자동 destroy
9
}

1
template<typename T, size_t N>
2
class ThreadSafePool {
3
    Slot slots_[N];
4
    Slot* free_head_;
5
    SemaphoreHandle_t mutex_;   // FreeRTOS 예
6

7
public:
8
    ThreadSafePool() {
9
        // 초기화
10
        mutex_ = xSemaphoreCreateMutex();
11
    }
12

13
    T* allocate() noexcept {
14
        xSemaphoreTake(mutex_, portMAX_DELAY);
15
        T* result = nullptr;
16
        if (free_head_) {
17
            Slot* slot = free_head_;
18
            free_head_ = slot->next;
19
            result = reinterpret_cast<T*>(&slot->storage);
20
        }
21
        xSemaphoreGive(mutex_);
22
        return result;
23
    }
24

25
    void deallocate(T* p) noexcept {
26
        if (!p) return;
27
        xSemaphoreTake(mutex_, portMAX_DELAY);
28
        Slot* slot = reinterpret_cast<Slot*>(p);
29
        slot->next = free_head_;
30
        free_head_ = slot;
31
        xSemaphoreGive(mutex_);
32
    }
33
};

1
template<typename T, size_t N>
2
class LockFreePool {
3
    Slot slots_[N];
4
    std::atomic<Slot*> free_head_;
5

6
public:
7
    T* allocate() noexcept {
8
        Slot* head = free_head_.load(std::memory_order_acquire);
9
        while (head) {
10
            Slot* next = head->next;
11
            if (free_head_.compare_exchange_weak(
12
                    head, next,
13
                    std::memory_order_release,
14
                    std::memory_order_acquire)) {
15
                return reinterpret_cast<T*>(&head->storage);
16
            }
17
        }
18
        return nullptr;
19
    }
20

21
    void deallocate(T* p) noexcept {
22
        if (!p) return;
23
        Slot* slot = reinterpret_cast<Slot*>(p);
24
        Slot* head = free_head_.load(std::memory_order_relaxed);
25
        do {
26
            slot->next = head;
27
        } while (!free_head_.compare_exchange_weak(
28
            head, slot,
29
            std::memory_order_release,
30
            std::memory_order_relaxed));
31
    }
32
};

1
template<typename T, size_t N>
2
class InstrumentedPool {
3
    // ... 기본 pool
4

5
    size_t peak_allocated_ = 0;
6
    size_t total_allocations_ = 0;
7
    size_t failed_allocations_ = 0;
8

9
public:
10
    T* allocate() noexcept {
11
        ++total_allocations_;
12
        T* p = base_allocate();
13
        if (!p) {
14
            ++failed_allocations_;
15
        } else {
16
            if (allocated_ > peak_allocated_) peak_allocated_ = allocated_;
17
        }
18
        return p;
19
    }
20

21
    struct Stats {
22
        size_t allocated;
23
        size_t available;
24
        size_t peak;
25
        size_t total_allocs;
26
        size_t failed;
27
    };
28

29
    Stats get_stats() const {
30
        return {allocated_, N - allocated_, peak_allocated_,
31
                total_allocations_, failed_allocations_};
32
    }
33
};

1
template<typename T>
2
class HeapPool {
3
    void* storage_;
4
    Slot* free_head_;
5
    size_t capacity_;
6

7
public:
8
    explicit HeapPool(size_t n) : capacity_(n) {
9
        storage_ = std::malloc(sizeof(Slot) * n);
10
        // ... free list 초기화
11
    }
12

13
    ~HeapPool() { std::free(storage_); }
14
};

1
auto* p = pool.allocate();
2
pool.deallocate(p);
3
pool.deallocate(p);   // free list 순환 → 무한 루프 또는 corruption

1
auto* p = pool.allocate();
2
pool.deallocate(p);
3
p->method();   // p의 메모리는 next pointer로 변경됨

1
ObjectPool<HugeStruct, 10000> pool;   // sizeof(HugeStruct) * 10000

1
class MultiPool {
2
    ObjectPool<std::byte, 16> small_pool_;   // 16 byte 블록
3
    ObjectPool<std::byte, 64> medium_pool_;  // 64 byte
4
    ObjectPool<std::byte, 256> large_pool_;  // 256 byte
5

6
public:
7
    void* allocate(size_t n) {
8
        if (n <= 16) return small_pool_.allocate();
9
        if (n <= 64) return medium_pool_.allocate();
10
        if (n <= 256) return large_pool_.allocate();
11
        return nullptr;
12
    }
13
};

1
void deallocate(void* p, size_t n) {
2
    if (n <= 16) small_pool_.deallocate(static_cast<std::byte*>(p));
3
    else if (n <= 64) medium_pool_.deallocate(static_cast<std::byte*>(p));
4
    // ...
5
}

1
malloc/free (newlib-nano):
2
  alloc: 평균 ~120 cycles, max 800+ (worst case)
3
  free:  평균 ~80 cycles
4
  fragmentation: 시간에 따라 증가
5
  determinism: 낮음
6

7
ObjectPool<Order, 100>:
8
  alloc: 12 cycles (constant)
9
  free:  10 cycles (constant)
10
  fragmentation: 0
11
  determinism: 완벽