Implement a Fixed-Block Memory Pool / Custom Arena Allocator
In modern C++, we never guess what the compiler does. We look directly at byte offsets, CPU registers, and object ownership lifetimes.
A Bump/Arena Allocator simply advances an offset pointer (ptr += size) on each allocation and cannot deallocate individual objects; it frees all allocated memory at once when the entire arena scope is reset (ideal for per-frame or per-request scratch buffers). A Free-List Object Pool supports individual O(1) allocations AND deallocations in arbitrary order by recycling freed slots via an embedded linked list.
Modifying freeHead_ simultaneously from multiple threads causes data races and corrupted free-lists. To make it thread-safe:
- Lock-Free CAS Loop: Use
std::atomic<Slot*> freeHead_withcompare_exchange_weak(note: beware of the ABA problem, which requires tagged pointers / 128-bit CAS). - Thread-Local Pools (
thread_local): Give each worker thread its own privateFixedObjectPool. This achieves $100%$ zero lock contention and maximum cache locality without atomics.
In placement new (mem) T(...), if T's constructor throws, C++ guarantees that the constructor does not complete and stack unwinding begins. However, because placement new was used, the compiler does NOT automatically deallocate mem! To prevent memory leaks, you must wrap placement new in a try/catch block that catches the exception, calls deallocate(mem), and re-throws.
Interviewer's lens
Memory pools and arena allocators are among the most heavily tested systems programming topics in High-Frequency Trading (HFT), game engine development, and real-time audio systems. Interviewers ask candidates to implement an object pool from scratch because it reveals whether you understand hardware cache latency, memory alignment, placement new, and zero-cost data structures. Weak candidates propose a std::vector<bool> or an external array of pointers to track allocated slots—wasting memory and adding O(N) search overhead. Senior candidates immediately implement an embedded free-list (union Slot) that stores the nextFree pointer directly inside the unused payload bytes of free slots, achieving O(1) allocation and deallocation in 2 CPU instructions with strictly 0 bytes of metadata overhead.
Under the hood & memory layout
General-purpose heap allocators (malloc/new) are non-deterministic: they search complex boundary-tag free-lists (first-fit/best-fit), acquire global arena mutexes across threads, cause heap fragmentation, and trigger OS page faults via brk/mmap. A Fixed-Block Memory Pool pre-allocates a contiguous block of N slots upfront. The key architectural breakthrough is the Embedded Free-List: when a slot is actively holding a live object T, its bytes contain the fields of T; when the object is destroyed, those exact same bytes are repurposed to hold a single 8-byte pointer Slot* nextFree linking to the next available free slot. Because an object is either alive OR free (never both simultaneously), the memory overhead for tracking free blocks is identically 0 bytes. Allocation pops freeHead_ in 2 instructions; deallocation pushes the returned address onto freeHead_ in 2 instructions. Because the free-list operates in LIFO (Last-In, First-Out) order, the most recently freed slot is recycled first, guaranteeing that the slot's memory is already warm in the CPU's L1 data cache.
A single contiguous block of aligned memory. Eliminates OS heap fragmentation and keeps all objects packed within sequential hardware memory pages.
Defined as union Slot { alignas(T) std::byte storage[sizeof(T)]; Slot* nextFree; }. When active, storage holds T. When inactive, nextFree overlaps storage[0..7].
Decouples raw memory allocation from object initialization. allocate() supplies the uninitialized byte address; new (mem) T(...) runs the constructor in-place. destroy() calls ptr->~T() without releasing memory back to the OS.
Freeing an object pushes it to freeHead_. The subsequent create() immediately pops that same slot, reusing the cache line while still hot in L1 cache (~1ns access latency).
Core concepts & syntax traps
Why General-Purpose new / delete Is Prohibited in Low-Latency Loops
Why General-Purpose new / delete Is Prohibited in Low-Latency Loops
Standard new and delete delegate to the OS allocator (such as ptmalloc, jemalloc, or tcmalloc). In high-frequency trading (HFT) and game tick loops, general-purpose heap allocation is strictly forbidden for three fundamental reasons:
- Unbounded Latency: Allocators maintain free-lists sorted by size classes. When fragmentation occurs, searching for a suitable block takes unpredictable time (O(K) free-list walks).
- Multithreaded Lock Contention: Allocators share arenas across threads. Under high concurrency, threads stall waiting for internal allocator mutex locks.
- OS System Calls & Page Faults: If heap arenas run dry, the allocator issues
mmaporbrksyscalls, dropping into kernel space and incurring virtual memory page faults.
A custom memory pool eliminates all three bottlenecks by pre-allocating memory up front, performing zero syscalls and zero locks on the hot path.
// PROHIBITED in HFT order routing hot path:
Order* o = new Order(id, price, qty); // Heap lock + non-deterministic latency!
// REQUIRED: O(1) deterministic pool allocation
Order* o = pool.create(id, price, qty); // 3 CPU instructions, 0 locksPre-allocate memory pools at startup to ensure zero locks, zero page faults, and deterministic O(1) latency on hot paths.
The Embedded Free-List: Zero-Byte Metadata Overhead via union
The Embedded Free-List: Zero-Byte Metadata Overhead via union
How do we maintain a linked list of free slots without wasting 8 extra bytes per slot for a next pointer? By utilizing a union!
When a slot is allocated to the user, the memory contains the live payload of T. When the user destroys the object, that slot is empty. We cast the newly freed memory to Slot* and write the address of the current freeHead_ into its first 8 bytes! Because a slot is never active and free at the same time, the nextFree pointer requires strictly 0 bytes of auxiliary storage.
union Slot {
// Ensure slot is at least as large as a pointer and aligned to T
alignas(T) alignas(Slot*) std::byte storage[sizeof(T) >= sizeof(Slot*) ? sizeof(T) : sizeof(Slot*)];
Slot* nextFree;
};
// Allocate: pop freeHead_
Slot* slot = freeHead_;
freeHead_ = freeHead_->nextFree;
// Deallocate: push onto freeHead_
slot->nextFree = freeHead_;
freeHead_ = slot;An embedded free-list reuses the dead payload memory of free slots to store next pointers with 0 bytes overhead.
Separating Memory Allocation from Construction: Placement new & Explicit ~T()
Separating Memory Allocation from Construction: Placement new & Explicit ~T()
In standard C++, new T(...) performs two distinct operations: (1) calls operator new to allocate raw bytes, and (2) invokes T's constructor. Conversely, delete ptr calls T's destructor and then invokes operator delete to return bytes to the OS.
In a memory pool, we must decouple these two steps:
- Construction:
void* mem = pool.allocate(); T* obj = new (mem) T(args...);uses placement new (#include <new>) to constructTdirectly inside pre-allocated storage without invoking the OS allocator. - Destruction: We call the destructor explicitly via
ptr->~T(), and then return the raw memory slot back to the pool viapool.deallocate(ptr). Never calldelete ptron pool memory!
template <typename... Args>
T* create(Args&&... args) {
void* mem = allocate();
if (!mem) return nullptr;
return new (mem) T(std::forward<Args>(args)...); // In-place construction
}
void destroy(T* ptr) noexcept {
if (!ptr) return;
ptr->~T(); // Explicit destructor
deallocate(static_cast<void*>(ptr)); // Return slot to free-list
}Always separate memory management from object lifetime using placement new and explicit destructor calls (~T()).
LIFO Allocation Order & Hardware L1 Cache Warmth
LIFO Allocation Order & Hardware L1 Cache Warmth
Because deallocate() pushes freed slots onto the front of freeHead_ and allocate() pops from the front, the embedded free-list naturally behaves as a LIFO (Last-In, First-Out) stack.
This provides a massive hardware performance advantage: when an object is destroyed and another object is immediately allocated, the pool reuses the exact same memory address that was just written to. That cache line is already resident in the CPU's L1 data cache, avoiding cache misses and memory bus traffic.
void* addr1 = pool.allocate();
pool.deallocate(addr1);
void* addr2 = pool.allocate();
// addr1 == addr2 is GUARANTEED! (LIFO stack reuse)
// The CPU accesses hot L1 cache instead of cold main RAM.LIFO free-list recycling keeps memory allocations warm in CPU L1 cache, drastically reducing cache misses.
Unlock Live Implementation & Interview Scenarios
The C++23 production code, live coding steps, scenario twist solutions, and common UB traps are part of Brute2Best Pro. Module 1 is completely free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.