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.
| Design | Throughput | Avg / op |
|---|---|---|
std::map + std::list | 7.0 M ops/s | 142 ns |
| Flat levels + intrusive FIFO + pool | 13.2 M ops/s | 76 ns |
Per-operation latency, measured with steady_clock around each call:
| Design | p50 | p99 | p99.9 |
|---|---|---|---|
std::map | 125 ns | 583 ns | 0.7–3.9 µs |
| Flat | 42 ns | 500 ns | 2.7–3.9 µs |
Reading the numbers honestly
- The p50 for the flat book is at the timer's floor. On Apple Silicon,
steady_clockadvances in steps of about 41.7 ns, so "42 ns" means "one tick or less". To resolve that properly you needrdtsc/cntvct_el0and 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:
- No allocation in steady state. The pool and freelist recycle slots, while the map design calls
malloc/freefor tree and list nodes on every new level and order. - 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. - 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_mapwith 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 statto 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.