< cd ..|~/blog/memory-pool-allocator|RO

Understanding Memory Pool Allocators

author: kunaldate: 2026-02-13
tags: ["cpp", "performance", "systems", "memory-management"]

Memory management is one of the most critical aspects of C++ programming. While `new` and `delete` (and their underlying `malloc` and `free`) are general-purpose and convenient, they come with a cost: performance overhead from system calls and memory fragmentation over time.

For high-performance applications like game engines, real-time systems, or high-frequency trading platforms, these costs can be prohibitive. Enter the **Memory Pool Allocator**.

In this post, we'll explore a clean, efficient implementation of a fixed-size memory pool allocator in C++.

##The Problem with General Allocation

When you call `new`, the operating system (or the allocator runtime) has to: 1. Search the heap for a free block of sufficient size. 2. Update internal bookkeeping structures. 3. Ideally, return a pointer.

This process is generally $O(n)$ or $O(\log n)$ depending on the implementation, but more importantly, it's *unpredictable*. Furthermore, allocating objects of varying sizes scatters them across the heap, leading to **fragmentation** and poor **cache locality**.

##The Solution: A Fixed-Size Pool

A Memory Pool (or Object Pool) pre-allocates a large, contiguous chunk of memory and divides it into fixed-size "blocks".

Because the blocks are all the same size and contiguous: 1. **Allocation is $O(1)$**: We just take the next available block. 2. **Deallocation is $O(1)$**: We just put the block back. 3. **Cache Friendliness**: Objects are stored close together in memory. 4. **No External Fragmentation**: The pool is one solid block.

##The Secret Sauce: Intrusive Linked Lists

You might wonder: *How do we track which blocks are free without using extra memory?*

The clever trick is to use the **free memory itself**. When a block is not being used by the application, we can use that memory to store a pointer to the *next* free block. This is called an **intrusive linked list**.

Let's look at the `Block` definition in `allocator.h`:

typedef struct Block {
    Block* next;
#ifdef DEBUG
    bool is_free;
    uint32_t pool_id;
#endif
} Block;

When a block is free, it acts as a node in our linked list. When it's allocated, the user overwrites this data with their own object. We only need `sizeof(Block)` to be at least `sizeof(void*)` (plus debug info if enabled).

##Implementation Details

###Initialization

The allocator starts by reserving a large chunk of memory and setting up the free list.

m_MemoryPool->memory = std::malloc(m_MemoryPool->block_size * block_count);
char* start = reinterpret_cast<char*>(m_MemoryPool->memory);

for (size_t i = 0; i < block_count; i++) { // Calculate address of the current block Block* block = reinterpret_cast<Block*>(start + (i * block_size)); // Point it to the current head of the free list block->next = m_MemoryPool->free_list; // Update the head m_MemoryPool->free_list = block; } ```

This effectively links all blocks together: `Block[N] -> Block[N-1] -> ... -> Block[0] -> nullptr`.

###Allocation: $O(1)$

Allocation is incredibly simple. We just "pop" the head of the free list.

void* Allocator::allocate() {
    if (m_MemoryPool->free_list == nullptr) {
        return nullptr; // Out of memory
    }
    
    // Take the first block
    Block* block = m_MemoryPool->free_list;
    
    // Move head to the next block
    m_MemoryPool->free_list = block->next;
    
    return block;
}

No searching, no system calls. Just a few pointer assignments.

###Deallocation: $O(1)$

Freeing memory is just as fast. We "push" the block back onto the head of the free list.

void Allocator::free(void* ptr) {
    if (ptr == nullptr) return;
    
    // Safety checks skipped for brevity...
    
    Block* block = static_cast<Block*>(ptr);
    
    // Point this block to the current head
    block->next = m_MemoryPool->free_list;
    
    // Make this block the new head
    m_MemoryPool->free_list = block;
}

##Safety Features

One common criticism of manual memory management is safety. This implementation leads by example with robust debug checks (`#ifdef DEBUG`):

1. **Double Free Detection**: A boolean flag `is_free` inside the block prevents freeing the same memory twice. ```cpp if (block->is_free) { std::cerr << "Double free error\n"; std::abort(); } ```

2. **Ownership Validation**: A `pool_id` ensures that a pointer being freed actually belongs to *this* allocator, preventing cross-allocator mix-ups. ```cpp if (block->pool_id != m_PoolId) { std::cerr << "Invalid free (wrong allocator)\n"; std::abort(); } ```

##Trade-offs and Conclusion

  • -This allocator is not a silver bullet.
  • -**Fixed Size**: It only works efficiently for objects of a specific size. You might need multiple allocators for different object types.
  • -**Manual Management**: It doesn't call constructors or destructors automatically (though `placement new` can solve this).

However, for its intended use case—managing frequently created and destroyed objects of uniform size—it offers unbeatable performance and predictability.

Implementing a memory pool is a great exercise in understanding how our tools work under the hood. It peels back the abstraction of `new` and shows that sometimes, a custom solution is the right tool for the job.

NORMAL MODE
memory-pool-allocator100%
Understanding Memory Pool Allocators