writing

Your order book should not be a std::map

A flat, price-indexed order book with intrusive FIFO queues and pooled orders against the textbook std::map design: same workload, same fills, 1.9× the throughput. Includes the numbers, the caveats, and where the time actually goes.

5 min readShivanshu Pathak

The textbook limit order book is a std::map<Price, std::list<Order>> per side. It's correct, it's short, and it's what most people write first. It's also a poor fit for how a book is actually used. This post compares it with a flat design on an identical workload and explains where the difference comes from.

The workload

A book is not a general-purpose sorted container. Real order flow has a shape:

  • Activity clusters near the touch. Most adds and cancels land within a few ticks of the best bid and ask.
  • Cancels dominate. On most venues, far more orders are cancelled than filled.
  • Matching only ever touches the best level. You never need "the 40th price level" in a hurry.

The benchmark generates 2,000,000 operations: 60% adds placed 1–26 ticks from the mid, 30% cancels of a random live order, and 10% market orders that sweep the opposite side. Both books replay exactly the same sequence, and both report the same total filled quantity (10,077,178), which is a cheap end-to-end check that the matching logic agrees.

Design A: the textbook book

std::map<uint32_t, std::list<O>, std::greater<uint32_t>> bids;
std::map<uint32_t, std::list<O>> asks;
std::unordered_map<uint64_t, Loc> index;   // order id -> (side, price, list iterator)

Every new price level allocates a red-black tree node. Every order allocates a list node. Finding the best level means following pointers to the leftmost leaf. Each of those pointer hops can be a cache miss, and every allocation is a trip into malloc.

Design B: flat levels, intrusive FIFO, pooled orders

struct O   { uint64_t id; uint32_t qty, next, prev, px; uint8_t side; };
struct Lvl { uint32_t head = NIL, tail = NIL; };

std::vector<O> pool;            // all orders live here; links are 32-bit indices
std::vector<uint32_t> freelist; // recycled slots, so steady state does no allocation
Lvl lv[2][N];                   // one FIFO per (side, price tick), indexed directly
uint32_t best[2];               // best bid / best ask level index
  • Price → level is an array index, not a tree search. Prices are integers in ticks, and the band of active prices is narrow.
  • Each level is an intrusive doubly-linked FIFO threaded through the pool. Price-time priority falls out naturally: append at the tail, match from the head.
  • Cancel is O(1): look up the slot, unlink, and push it onto the freelist.
  • Indices instead of pointers halve the link size, and keep orders packed in one contiguous allocation.
  • Best price is a cursor. When a level empties, it walks to the next non-empty level, which is usually one or two steps away.

Results

Apple M1 Pro, macOS, Apple clang 21, -O2. Threads are not pinned (macOS doesn't support hard affinity). Throughput is the median of 5 runs with no timers inside the loop.

DesignThroughputAvg / op
std::map + std::list7.0 M ops/s142 ns
Flat levels + intrusive FIFO + pool13.2 M ops/s76 ns

Per-operation latency, measured with steady_clock around each call:

Designp50p99p99.9
std::map125 ns583 ns0.7–3.9 µs
Flat42 ns500 ns2.7–3.9 µs

Reading the numbers honestly

  • The p50 for the flat book is at the timer's floor. On Apple Silicon, steady_clock advances in steps of about 41.7 ns, so "42 ns" means "one tick or less". To resolve that properly you need rdtsc/cntvct_el0 and many operations per sample.
  • The tails are noisy and close. p99.9 moved between runs, sometimes by 5×. Both books still route every add and cancel through std::unordered_map, whose occasional rehash and node allocation dominate the tail. That's the next thing to replace, with a pre-sized open-addressing table or order IDs that index the pool directly.
  • No pinning, no isolated cores. On a Linux box with isolcpus, a pinned thread, and huge pages, the tail would tighten. I'd rather publish the macOS numbers with that caveat than tune the environment until the chart looks good.

Where the time goes

The flat book wins because it does less of what CPUs are bad at:

  1. No allocation in steady state. The pool and freelist recycle slots, while the map design calls malloc/free for tree and list nodes on every new level and order.
  2. Fewer dependent loads. Finding the best ask is lv[1][best[1]]: one indexed load. In a red-black tree it's a chain of pointer dereferences, each waiting on the last.
  3. Better locality. Orders sit in one contiguous vector with 32-bit links, so neighbouring levels and recently touched orders tend to share cache lines.

What I'd change for production

  • Replace unordered_map with a pre-sized open-addressing table, or use exchange-assigned IDs as pool indices.
  • Recentre the price array as the market drifts, or use a two-level bitmap to find the next non-empty level in O(1) for sparse books.
  • Measure with cycle counters and report a full HDR histogram rather than three percentiles.
  • Run on Linux with pinned cores and perf stat to show cache-miss and branch-miss counts per operation.

Reproduce it

The full benchmark is a single file: order_book_bench.cpp.

clang++ -std=c++20 -O2 -o book order_book_bench.cpp && ./book

Your numbers will differ by machine. If they don't match the shape of mine, I'd like to know why.