Trade against it in your browser → The engine is compiled to WebAssembly: send limit orders and cancels into a live book, watch the depth ladder and the queue at each price in time priority, run random order flow, and run the benchmark below inside the browser.
A limit order book and matching engine in C++, built to the two rules in Aleksey Kladov's Static Allocation, Constant Work: no dynamic memory allocation after initialization, and do the same amount of work whether the system is empty or full.
The first version of this project was a pool of pre-allocated Order objects behind a
std::map price ladder. It was fast on an empty book, and it had no cancel path, which
turned out to be the only reason it had no use-after-free. This version is a rewrite
around the idea that an order is never created or destroyed, only moved between states.
Static allocation. The maximum number of resting orders and the price ladder are fixed at startup:
./nano_match --orders-max 1000000 --price-max 65535Everything the process will ever need is acquired in OrderBook's constructor: the
order slab, both ladders, the occupancy bitmaps, the id index, the trade buffer. After
the constructor returns there is no path through the engine that reaches the allocator.
No new, no malloc, no vector growth, no std::map node, no exception. If the machine
cannot supply the memory, the process fails to start, on a quiet system, at deploy time,
rather than at 09:30:00 with a queue building behind it.
This is why the old std::map had to go. The pool bypassed new for orders and then
the book called new behind its back, once per new price level, on the matching path.
Overload is a rejected request, never a resize and never a crash. limit() returns
Status::rejected_book_full and the book is left byte-for-byte as it was found.
Constant work. There is no collection of "live" orders and no collection of "active"
price levels to iterate. The order slab is a flat array of orders_max + 1 orders, all
of which always exist; each price level is a fixed struct in a flat array indexed by
price, occupied or empty but never created or destroyed. Work per request depends on how
much the request actually trades, not on how full the book is.
The one place that could still degrade with book state is finding the new best price
when the touch level empties. A linear scan of the ladder for that is O(price_range) in
exactly the worst circumstance; a thin book in a fast market. LevelBitmap replaces it
with a hierarchy of bitmaps (one bit per price, then one bit per word of those, and so
on to a single word), so the search is a handful of word loads at any ladder size.
There is no allocate and no free. There is a fixed population of orders that are always one of three states, and every transition between them is a named function that asserts what it is transitioning from:
acquire() rest()
reserved ──────────────> in flight ──────> resting (bid | ask)
^ │ │
│ release() │ │ unlink()
└────────────────────────┴──────────────────┘
reserved is the neutral order, the equivalent of Order.reserved in the post: the no-op
the slab is initialised to. The number of orders in the system never changes, and
assert_invariants() checks that: every order is either reserved or linked into exactly
one price level, and the two counts add up to the slab size.
This is what makes a cancel path safe. The bug the post describes (a cancelled order released back to the pool while still linked into its price level, so the next allocation hands that memory to a new order and the stale link still resolves) needs three things to be true at once. Here, all three are gone:
- The link would have to be a pointer.
nextandprevare slot indices into the slab. A stale index is a defined read of a liveOrderwhosestatean assert can check. A stale pointer is undefined behaviour, which nothing can check. - Release would have to be silent.
retire()asserts the links are clear and that the order is no longer reachable by id;release()asserts the slot is not already reserved.unlink()andretire()are called in that order and are never separated. - A cancel would have to name a slot. It names a client order id, resolved through
IdIndex. An id that is not resting is already filled, already cancelled, never issued, is rejected. There is no way to phrase "cancel slot 7" and reach whichever order happens to live in slot 7 now.
Asserts stay compiled in at -O3. An assert that only runs in debug builds is an assert
that never runs, because the build under load is the release build. They measure as free
(below).
./sim drives the engine with a random mix of adds, cancels, multi-level sweeps, and
malformed requests, against a book deliberately sized small (24 slots, 40 ticks) so it
spends most of its life saturated. Two independent oracles run after every operation:
OrderBook::assert_invariants()The engine's own full sweep of every level and every slot. Catches structural corruption: a level naming a reserved slot, a back link that disagrees with its forward link, a cached best price that has drifted.- A reference book built from
std::mapandstd::deque. Far too slow to ship and far too simple to be wrong. Catches behavioural divergence: a fill that should not have happened, a queue served out of time priority, a wrong rejection.
Everything is a pure function of the seed, so a failure reproduces exactly:
./sim --seeds 1000 --steps 4000 # 4M operations, ~11s
./sim --seed 743 --steps 4000 # reproduce oneThe run reports which outcomes it reached and fails if any path was never exercised,
because a simulation that never drives the book into a state proves nothing about it.
That check paid for itself immediately: it showed that a status I had just added,
residual_dropped, was never reached in four million operations. It is not a coverage
gap, it is unreachable, and the proof is now an assert in order_book.cpp. A taker only
leaves a remainder if every maker it touched was consumed whole, and consuming a maker
whole frees a slot, so a full book at that point implies nothing traded.
To check the harness can actually see failures, five bugs were introduced deliberately. All five were caught inside the first 25 steps of seed 1:
| Mutation | Caught by |
|---|---|
| cancel releases the slot without unlinking (the original bug) | assert_invariants |
| orders linked at the head of a level, breaking time priority | reference model |
| emptied level does not re-derive the touch | assert_invariants |
| taker overfilled at a level | reference model |
| filled maker left in the id index | retire assert |
The fourth is the interesting one: the quantity underflow wrapped, so filled + remaining == qty still held and the asserts stayed quiet. Only the reference model saw
it. That is the argument for having both oracles rather than either.
git clone https://github.com/apollo-2006/nano_match.git
cd nano_match
./build.sh # builds ./nano_match and ./sim
./sim # 200 seeds
./nano_match
./nano_match --orders-max 4000000 --price-max 1000000 --prefetch 0 --no-latencybuild.sh compiles the benchmark at -O3 -march=native -flto with asserts on, and the
simulation with -DNANO_SLOW_ASSERTS, which additionally enables the O(book) invariant
sweeps.
AMD Ryzen 9 5900XT, g++ 16.2, -O3 -march=native -flto, pinned to one core, best of five,
4M requests per phase (--requests 4000000), one million order population over a 65,536
tick ladder. Phase 2 runs the identical load against a book already filled to its
configured limit.
Requests are generated into a fixed ring outside the timed region, so the rng is not part of the measurement and the submission loop has the lookahead a real sequencer has.
throughput p50 p99 p99.9 (ns/request)
phase 1, cold book 11.97 M req/s 50 190 550
phase 2, at the limit 9.84 M req/s 50 450 790
Which is the point of the exercise. A book holding a million resting orders costs 18% less throughput than an empty one and the same p50, 50ns, either way. The stated limit is a real limit, not a number that holds until the day it matters.
Three caveats. Per-request timing costs ~20ns of steady_clock per sample, included
above; --no-latency skips it and reports 21.7 / 16.0 M req/s for the same two
phases. The clock ticks in 10ns steps on this host, so the latency columns are quantized
to 10ns. And p100 is tens of microseconds, which is not the engine: the harness measures a
bare pair of steady_clock calls first and prints its p100 too, and it is the same order
of magnitude. Those are scheduler preemptions on a desktop, and an isolated core is the
only way to measure past them.
An earlier version of this table, measured with g++ 13.3 on the same machine with other work running, read 6.82 / 5.96 M req/s at a p50 of 83ns. Same code; the compiler upgrade and a quiet core account for the difference.
OrderBook::prefetch(id) warms the id index for a request that has not been submitted
yet. A sequencer reading from a ring buffer knows its next several requests, so this
costs nothing real:
phase 1 phase 2
--prefetch 0 8.34 M req/s 7.36 M req/s p50 100 / 100 ns
--prefetch 16 11.97 M req/s 9.84 M req/s p50 50 / 50 ns
+44% throughput and p50 halved, for a hint. The workload is latency-bound on a single structure; the id table is 32 MiB, every probe is a dependent random access, and there is not enough independent work in one request to hide it. Lookahead turns a serialised chain of misses into overlapping ones.
Two things that did not work, both instructive:
- Prefetching the price level too wipes out the entire gain. The ladder is 3 MiB and largely cache-resident, so warming it only evicts the one structure that actually misses.
- Prefetching one order ahead inside the matching loop does nothing. There is no distance between the hint and the use: a trade is a few cycles of arithmetic, not enough to cover a miss.
Also worth knowing: the earlier version of this benchmark generated each request inline, inside the timed loop, and reported higher throughput than the current one does with lookahead off. The rng was independent work that the out-of-order engine was using to hide the cache misses. The old number was flattering itself.
Against the original engine, measured by removing one thing at a time. These rows are from the redesign, with g++ 13.3, and were not re-run; they are comparable to each other, not to the tables above.
| Configuration | Throughput |
|---|---|
original: std::map ladder, 64-byte orders, no cancel |
22.5 M req/s |
| this engine, minus the id index (so: also no cancel) | 22.8 M req/s |
| this engine, minus asserts only | ~ shipped |
| this engine, as shipped, no lookahead | 8.1 M req/s |
| this engine, as shipped, lookahead 16 | 11.0 M req/s |
(These rows use --no-latency, so they are comparable to each other and higher than the
instrumented table above.)
Always-on asserts cost nothing measurable: they are dozens of branches on values already
in registers, and turning them all off lands inside run-to-run noise. -flto is worth
12%, because the book is its own translation unit and limit() wants to inline into the
submission loop.
Everything else is the id index, which is the honest cost of the feature this whole
redesign exists to make safe: cancel by client order id. Two or three probes into a table
far larger than L3, per request, each one a dependent random access. It is not the
table's footprint, sizing --orders-max so the index fits in L3 recovers 28% and no
more. It is the serialised pointer chase, which is why lookahead helps and shrinking does
not.
Lookahead closes about half the gap to the no-index ceiling. Closing the rest means not looking orders up at all: have the engine assign the order id so that it encodes the slot, return it as a handle, and let the gateway own the client-id mapping. Cancel then costs one array index and a generation compare. That is generational indices, arrived at from the other direction and it is an API change, since callers would have to keep the handle the engine hands back.
web/book_web.cpp wraps OrderBook for JavaScript and web/build.sh compiles it with
the unmodified engine using Emscripten. The page's benchmark runs the same two phases
inside WebAssembly. Expect roughly the phase 1 speed of a native build with lookahead off,
a larger drop at the limit, and no gain from lookahead at all: __builtin_prefetch has
no WebAssembly instruction to become, so the hint compiles away.
GitHub Actions builds both native binaries, runs ./sim, builds the demo and publishes it
to Pages on every push to main.
web/build.sh # needs em++ on PATH
python3 -m http.server -d web/dist # then open http://localhost:8000include/types.hpp typedefs, Slot, the assert macros
include/order.hpp 32-byte Order, the State tag, the neutral order
include/order_slab.hpp the fixed population; acquire/release and conservation
include/id_index.hpp OrderId -> Slot, open addressed, backward-shift deletion
include/level_bitmap.hpp hierarchical occupancy bitmap over the price ladder
include/order_book.hpp the book
src/order_book.cpp matching, the state transitions, the invariant sweep
src/main.cpp benchmark harness
tests/simulation.cpp deterministic simulation against a reference model
build.sh both binaries
web/ WebAssembly bindings and the demo page
- The ladder is dense. Memory is O(price_max), not O(occupied levels), which suits an instrument with a bounded tick range and does not suit a sparse one.
- Limit orders only. No market, IOC, FOK, stop, or iceberg types, and no amend.
- No self-trade prevention. Nothing stops a participant matching their own order.
- Single threaded. One sequencer. No feed handler, no concurrent access. The extra slot in the slab assumes exactly one order in flight at a time.
- Trades are reported but not persisted.
trades()is valid until the next request; there is no journal and no recovery. - Prices are
uint32_tin minor units, and must index the ladder directly.
The design here follows Aleksey Kladov's Static Allocation, Constant Work, written in
reply to a question about whether an object pool is a tagged union whose tag nobody
tracks. The static allocation rule, the constant work rule, the neutral reserved
order, and the practice of asserting state at every transition and then subjecting the
asserts to deterministic simulation are all his. The bugs are mine.
MIT. See LICENSE.
Abir Deol · abirdeol.tech