Fixed-Size Memory Pool Allocator

Worked Solution

How to Think About It: The core challenge is achieving $O(1)$ alloc and free with zero runtime overhead. The standard library malloc is general-purpose -- it handles variable sizes, thread safety, fragmentation -- and all of that generality costs latency. On a trading hot path, you cannot afford even a single system call or lock acquisition. The key observation is that when all blocks are the same size, allocation becomes trivially simple: just maintain a stack (linked list) of free blocks. Pop to allocate, push to free. The clever trick is that free blocks are not in use, so you can store the linked list pointers inside the blocks themselves -- zero extra memory overhead.

Algorithm:

1. At startup, allocate one large contiguous region of block_size * num_blocks bytes using a single malloc call.
2. Partition this region into num_blocks chunks and thread them into a singly-linked free list. Each free block's first sizeof(pointer) bytes stores a pointer to the next free block.
3. alloc(): Pop the head of the free list and return it. If the list is empty, return nullptr (pool exhausted).
4. free(ptr): Push the returned block onto the head of the free list.

Both operations are a single pointer swap -- no branching, no searching, no system calls.

Code:

```cpp #include <cstdlib> #include <cstddef> #include <cstdint> #include <algorithm>

class MemoryPool { private: // When a block is free, its first bytes hold a pointer to the next free block. struct FreeBlock { FreeBlock* next; };

void* pool_; // base pointer to the contiguous allocation FreeBlock* free_head_; // head of the intrusive free list size_t block_size_; // size of each block (bytes) size_t num_blocks_; // total number of blocks

public: MemoryPool(size_t block_size, size_t num_blocks) : block_size_(std::max(block_size, sizeof(FreeBlock))), num_blocks_(num_blocks), free_head_(nullptr) { // One-time allocation -- the only malloc in the system. pool_ = std::malloc(block_size_ * num_blocks_);

// Thread all blocks into the free list. free_head_ = reinterpret_cast<FreeBlock*>(pool_); FreeBlock* current = free_head_; for (size_t i = 1; i < num_blocks_; ++i) { FreeBlock* next_block = reinterpret_cast<FreeBlock*>( static_cast<uint8_t*>(pool_) + i * block_size_ ); current->next = next_block; current = next_block; } current->next = nullptr; // sentinel }

~MemoryPool() { std::free(pool_); }

// O(1) allocation: pop the free list head. void* alloc() { if (!free_head_) return nullptr; // pool exhausted void* block = free_head_; free_head_ = free_head_->next; return block; }

// O(1) deallocation: push onto the free list head. void dealloc(void* ptr) { FreeBlock* block = reinterpret_cast<FreeBlock*>(ptr); block->next = free_head_; free_head_ = block; } }; ```

Key design details:

• Intrusive free list: The next pointer lives inside the free block itself, so there is zero memory overhead for bookkeeping. When the block is allocated and in use, the application data overwrites that pointer -- which is fine, because a block in use is not on the free list.
• Contiguous layout: All blocks sit in one malloc'd region. Sequential allocations from a fresh pool walk through memory linearly, which is cache-line friendly.
• LIFO reuse: free pushes to the head, alloc pops from the head. This means recently freed (and therefore cache-warm) blocks get reused first.
• No fragmentation: Every block is the same size, so there is no external fragmentation. The pool either has capacity or it does not.

Why this matters on a trading desk:

• A system malloc can take
  $-

  00 \, \mu s$ due to lock contention, page faults, or heap fragmentation. A pool allocator runs in under

  0 \, ns$ -- just two pointer operations.
• Deterministic latency is critical. malloc has unpredictable worst-case timing; the pool allocator's worst case is the same as its best case.
• In production, you would typically size the pool for peak capacity (e.g., max open orders), allocate at process startup, and never touch the system allocator again on the hot path.

Complexity: $O(1)$ time and $O(1)$ extra space for both alloc and dealloc. Initialization is $O(N)$ where $N$ is the number of blocks.

Answer: Use an intrusive singly-linked free list threaded through a pre-allocated contiguous block array. alloc pops the list head; free pushes to the list head. Both are $O(1)$ with zero memory overhead, no system calls, and deterministic latency.