Custom Memory Allocators for an Order Matching Engine in C++

TL;DR. I wrote four memory allocators from scratch in C++17 (Linear, Stack, Pool and Free-List) behind one interface, and used them in a small price-time-priority limit order book, so that the matching path never calls new or malloc. In a fair benchmark against glibc's new/delete (1M allocate/free operations, median of 7 runs, -O2), the pool allocator is about 2.5× faster and the linear allocator about 15× faster, while a general-purpose free list barely beats glibc. My first benchmark claimed 16×; this post also explains why that number was wrong.

Code: stym01/Custom-Allocator-HFT-Engine

A matching engine creates and destroys lots of small, same-sized objects: every resting order is allocated when it enters the book and freed when it fills. In this post I walk through the four allocators, how the order book uses them, and what a fair benchmark against new/delete actually shows.

What new and malloc really cost

new calls operator new, which on Linux calls glibc's malloc. malloc is a user-space library, not part of the operating system: it hands out pieces of large memory regions it obtained earlier with brk or mmap, and only asks the kernel for more when those run out. For small objects glibc keeps per-thread caches (tcache) and size-class bins, so a typical allocate/free pair costs tens of nanoseconds and involves no system call.

So why write your own? Because a general-purpose allocator:

• has to handle every size and every free order, so it keeps metadata and searches bins;
• has occasional slow paths (growing the heap with a system call, consolidating free chunks) that make latency less predictable;
• places consecutive objects wherever there is room, which can hurt cache locality.

When every object has the same size and you know how long objects live, a specialised allocator can be simpler and faster.

One interface, four allocators

All four allocators share a small interface: Init grabs one large block up front, Allocate and Deallocate hand out and take back pieces of it, and Reset returns the allocator to empty. Swapping one allocator for another is then a one-line change, which is what makes side-by-side benchmarks easy.

• Linear keeps one pointer and moves it forward on each allocation (after padding for alignment). Individual frees do nothing; Reset moves the pointer back to the start. It is perfect for scratch memory with a clear lifetime, such as "everything allocated while handling one message".
• Stack works like Linear but writes a one-byte header before each block recording its alignment padding, so the most recent allocation can be freed by moving the pointer back. Frees must happen in reverse order.
• Pool splits its memory into equal-sized chunks and keeps the free ones in a linked list.
• Free List is general-purpose: free blocks sit in a list sorted by address, allocation takes the first block that fits (splitting off the remainder), and freeing merges the block with free neighbours so memory does not fragment into useless slivers.

The pool allocator

This is the allocator the order book depends on. The free list is stored inside the free blocks themselves, so the pool needs no extra memory for bookkeeping: allocating pops the head of the list, and freeing pushes the block back.

void* Allocate(size_t size, size_t alignment = 8) override {
    if (m_free_list_head == nullptr) {
        return nullptr;
    }
    FreeHeader* free_block = m_free_list_head;
    m_free_list_head = m_free_list_head->next;

    m_used_memory += m_chunk_size;
    m_num_allocations++;
    return (void*)free_block;
}

void Deallocate(void* ptr) override {
    FreeHeader* header = (FreeHeader*)ptr;
    header->next = m_free_list_head;
    m_free_list_head = header;

    m_used_memory -= m_chunk_size;
    m_num_allocations--;
}

The chunk size is rounded up to the alignment when the pool is created, so every chunk starts on an aligned address, and Reset threads all chunks into the list in address order.

The order book that uses it

The engine keeps two sides: buy orders sorted highest price first, and sell orders sorted lowest price first. An incoming order trades against the best opposite price for as long as the prices cross, partially or fully filling resting orders; whatever quantity is left rests in the book.

// An incoming buy order matches against the cheapest sellers first
while (sellSideHead != nullptr && sellSideHead->price <= price && quantity > 0) {
    int tradeQty = std::min(quantity, sellSideHead->quantity);
    quantity -= tradeQty;
    sellSideHead->quantity -= tradeQty;

    if (sellSideHead->quantity == 0) {          // fully filled: back to the pool
        Order* filled = sellSideHead;
        sellSideHead = sellSideHead->next;
        filled->~Order();
        orderPool->Deallocate(filled);
    }
}

Resting orders are constructed in pool memory with placement new, and handed back to the pool when they fill, so the matching path never calls new or malloc:

void* mem = orderPool->Allocate(sizeof(Order));
Order* newOrder = new (mem) Order(id, type, price, quantity);

// ... later, when the order is completely filled
filled->~Order();
orderPool->Deallocate(filled);

Each incoming message is decoded into scratch memory from a Linear allocator, which is reset once the message has been processed. In this project the messages are generated by an in-process simulation loop; there is no network I/O.

Benchmark

The benchmark performs 1,000,000 allocations of a 16-byte object followed by 1,000,000 frees for each allocator. Each allocator is initialised outside the timed region, the workload is repeated 7 times, and the median is reported. Returned pointers are folded into a volatile sink so the compiler cannot optimise the loops away. The Linear allocator can't free individual blocks, so it does 1M allocations followed by one Reset().

Environment: WSL2 (Ubuntu 24.04), g++ 13.3, -O2.

My first version of this benchmark showed a 16x win for the pool (117 ms vs 7.35 ms). That run was an unoptimised Windows build, each allocator was timed only once, and the default Windows heap is much slower than glibc's. Re-running it properly (optimised build, repeated runs, median) gives the table above: the pool is about 2.5x faster than new/delete, and only the linear allocator, which gives up individual frees, reaches about 15x.

What I learned

• Measure against a strong baseline. glibc's malloc is already fast for small objects; a general-purpose free-list allocator barely beats it.
• Methodology matters as much as the code. Optimisation level, repeated runs and a warm heap changed the headline number from 16x to 2.5x.
• The wins come from constraints. Fixed sizes (pool), LIFO lifetimes (stack) and bulk frees (linear) are what make an allocator fast.

Known limitations and next steps

The allocators are benchmarked; the matching engine itself is still a teaching-sized model, and I know exactly where it falls short:

• The book is a sorted linked list per side, so inserting a resting order is O(n) in the number of resting orders. The next step is price levels in a sorted map (or a tick-indexed array) with a FIFO queue per level.
• Prices are double. Real engines use integer ticks, so that equal prices compare equal exactly.
• Trades are printed with std::cout inside the matching loop. A real engine logs to a ring buffer and does the I/O off the hot path.
• There is no cancel or modify yet. O(1) cancels need an order-id → order index.
• The matcher is not benchmarked yet, only the allocators. Next: replay a message file and record per-message latency percentiles (p50/p99).

The code is on GitHub.