Orderbook-Engine

A price-time-priority limit order book and matching engine in C++20, built the way a trading venue's hot path is actually built: flat arrays instead of node graphs, a pre-allocated object pool instead of malloc, a bitmap instead of a tree walk, and a wait-free ring instead of a mutex.

~25 ns per message, ~40 M messages/sec single-threaded, verified trade-for-trade against an independently written reference implementation over 12 M+ randomised commands, and clean under AddressSanitizer, UndefinedBehaviorSanitizer and ThreadSanitizer.

Mixed message stream	25.2 ns/msg — 39.7 M msg/s
Cancel / add / modify (mean)	21.8 ns / 24.1 ns / 46.1 ns
Tail latency	p99 125 ns, p99.9 208 ns
vs std::unordered_map + new/delete	1.60× faster through an identical matching path
Two-thread pipeline	16.3 M msg/s end to end, handoff p50 83 ns
Differential fuzz	12 M+ commands, 0 divergences

Measured on an Apple M5 (10 cores), Apple Clang 21, -O3. Reproduce with make bench.

---

Why these numbers and not others

Most order book benchmarks are self-flattery. Three things here are deliberate attempts not to fool myself, and they are the parts I would defend hardest:

The clock is measured, not assumed. On this machine cntvct_el0 costs 0.43 ns to read but only advances every ~18 ns; std::chrono::steady_clock costs ~14 ns, which against a 25 ns operation is a 56% observer effect. So the engine is timed with the raw counter, and the harness probes the counter's resolution and cost at startup and prints them. Because a single 25 ns operation is under the clock's floor, the benchmark refuses to print a p50 for one message — it reports means (where the rounding is unbiased and cancels out), tail percentiles from single-shot readings (which are far above the floor and therefore honest), and a separately labelled median over 32-message batches. A p50 of "25 ns" from a clock that ticks every 18 ns would be a number I could not defend.

The workload has the shape of a real one. Uniformly random prices spread orders evenly across the array, keep every level thin, and let the level sweep do no work — which makes any book look fast. This generator random-walks a mid, decays order distance from it geometrically, and runs a closed loop: it tracks its own resting orders, consumes fill feedback so its cancel stream targets orders that are genuinely live (100% cancel hit rate, as a real participant's would be), and leans between adds and cancels to hold a target quoted depth. Steady state is ~19,000 resting orders across 50+ price levels per side at a one-tick spread.

The comparison is like-for-like. The book is templated on its allocator and its id index, so the "1.60× faster" figure comes from running the same matching code over the same recorded message stream with only those two structures swapped. The generator itself never runs inside a timed region; streams are recorded first and replayed.

---

Build and run

No dependencies beyond a C++20 compiler.

make            # build everything into build/
make check      # unit tests + 2M-command differential fuzz + tool selftest
make bench      # the full benchmark suite
make demo       # the two-thread engine, prints a live book
make sanitize   # ASan + UBSan + TSan

CMake is provided as an alternative:

cmake -B build -DCMAKE_BUILD_TYPE=Release && cmake --build build && ctest --test-dir build

Build at -O3. Every hot structure is a header-only template whose point is that the trade callback, the allocator and the index all inline into the matching loop. At -O0 the engine is roughly an order of magnitude slower and the benchmark means nothing.

---

Design

Flat price levels, not a tree

Prices are integer ticks — never double, because a double cannot represent 0.01 exactly and a venue that rounds a price is a venue that mismatches. Because ticks are dense, the book is a flat array indexed by price - min_price, so finding a level is one subtraction and one cache line rather than an O(log n) walk through scattered std::map nodes. The cost is memory proportional to the price band, which for a sane instrument is a few hundred kilobytes — a trade the latency budget is glad to make.

A single level array serves both sides. That is safe because the book can never be crossed: an incoming order always matches before any remainder rests, so no price ever holds bids and asks simultaneously. Two bitmaps record which side owns which level, and validate() asserts the property rather than trusting it.

Intrusive FIFO per level

Orders at a price form an intrusive doubly-linked list, which gives price-time priority for free — match from the head, rest at the tail — and makes cancel O(1) from the middle, because the node carries its own neighbours. Order is pinned at 48 bytes by static_assert; growing it past 64 would double the cache misses of a level sweep, the hottest loop in the engine.

A bitmap for "what is the next non-empty price"

When the best level empties, the book must find the next one. Scanning the array a price at a time is O(ticks) of cache misses. One bit per level puts 64 prices in a register, so the search is a load and a ctz: 0.60 ns to find the next non-empty level across a 4096-price band.

An object pool, not the allocator

Nearly every message allocates or frees an order node. malloc on that path can take a lock, touch a cold arena, and in the tail call mmap. The pool pre-faults one slab and threads a free list through the unused slots: 0.53 ns for an allocate-plus-free pair versus 15.79 ns for new/delete — 30× faster. When it runs out it rejects, because an exchange under a quote storm refuses orders rather than growing without bound.

Open addressing with backward-shift deletion

Every cancel goes through an order-id lookup. std::unordered_map chains, so a hit is a bucket load plus a pointer chase into a separately allocated node — a cache miss on the critical path of the most latency-sensitive message an exchange handles. A flat open-addressed table keeps keys and values inline: 11.29 ns versus 38.65 ns for find + erase + insert, 3.4× faster.

Deletion uses backward shift rather than tombstones. Tombstones are the obvious choice and the wrong one: a book that cancels most of what it posts would fill the table with gravestones and degrade to a linear scan without ever growing.

Wait-free SPSC ring between feed and matching

The book is single-threaded by construction — exactly one thread ever touches it — which is what keeps atomics out of the matching path entirely. Messages cross from the feed thread over a wait-free ring. Two details do most of the work: head and tail sit on separate cache lines (this machine has 128-byte lines, and getting that constant wrong turns the padding into decoration and reintroduces false sharing), and each side caches its stale view of the other index so the common case touches no line the other core owns. One-way handoff measures 83 ns p50, 167 ns p99.

The fill channel back out is deliberately best-effort: a slow downstream consumer must never be able to stall matching, so drops are counted and reported rather than allowed to apply backpressure.

Exchange semantics that have one right answer

• Trades print at the maker's price; the difference from the taker's limit is price improvement, and it belongs to the taker.
• IOC trades what it can and kills the rest. FOK is decided before anything mutates, so an unfillable order leaves no partial fills to unwind.
• A modify that only shrinks quantity at the same price keeps its place in the queue; a reprice or a size increase goes to the back and may trade on the way in. This is what real venues do, and it is the detail most toy implementations get wrong.

---

Correctness

Unit tests pin the semantics above. The part I trust more is the differential fuzz: millions of randomised commands run through both this engine and a deliberately naive book (std::map of std::list, linear scans, no bitmaps, no pool) written to be obviously correct rather than fast. The two share no code on purpose — a common helper would hide a common bug — and the test demands identical trade streams, identical fill/rest/kill quantities, identical reject reasons, and identical top-of-book after every single command, not just at the end.

A structural validate() sweep runs periodically during the fuzz and checks every invariant that could rot silently: list links in both directions, level counts and quantity sums, bitmaps against emptiness, cached best prices against reality, index size against the lists, and that the book is not crossed.

$ make check
  2000000 commands, 1203445 trades, 15653802 volume, 19894 orders still resting
  ok   trade-for-trade agreement with the reference implementation
22367 checks, 0 failures
all checks passed

Clean under all three sanitizers (make sanitize) — which matters, because this code hands out raw pointers from a hand-rolled pool, unlinks them from intrusive lists, and shares memory across threads through hand-written atomics. Those are precisely the failures that stay silent in a release build.

---

Real market data

tools/capture_binance.py captures a live Binance L2 depth stream and writes the same binary format the synthetic generator writes, so replay cannot tell them apart:

pip install websockets
./tools/capture_binance.py --symbol btcusdt --seconds 60 --out btc.lobc
./build/replay btc.lobc

Level appears → add, quantity changes → modify, quantity hits zero → cancel. The converter has an offline --selftest and a --from-jsonl mode so a capture can be re-converted without touching the network. Struct offsets shared with C++ are pinned by static_assert on the C++ side, so the two languages cannot drift apart silently.

Modelling caveat, stated plainly: an L2 feed publishes aggregate depth, not individual orders, so each price level is modelled as one synthetic order. That is faithful to the book's shape but not to its queue — real price-time priority inside a level is simply not observable from L2 data. Rounding can also occasionally produce a crossed update, which the engine matches away; replay reports the resulting rejects broken down by cause rather than burying them in a total.

---

What this is not

• Not a real exchange. No order gateway, no session layer, no persistence, no risk checks, no self-trade prevention, no auctions or circuit breakers.
• Single instrument, single thread per book. Scaling out means sharding by symbol, which is how real venues do it, but that is not implemented here.
• No kernel bypass. A production system would be on a real NIC with kernel-bypass networking; the ring here is a thread-to-thread queue.
• The tail past p99.9 is the OS, not the engine. On macOS there is no affinity API — THREAD_AFFINITY_POLICY is a documented no-op on Apple Silicon — so the strongest available hint is a QoS class, which took handoff p99 from 4292 ns to 167 ns but leaves millisecond outliers when a thread is descheduled. A single preemption of the consumer poisons an entire ring's worth of samples, which is exactly why p99.9 looks the way it does. On Linux the same header pins with sched_setaffinity, and production would add isolcpus and nohz_full.

---

Layout

include/lob/
  types.hpp           value types, commands, exec results
  order.hpp           the 48-byte resting-order node
  order_book.hpp      the book and matching engine (templated on its structures)
  level_bitmap.hpp    occupancy bitmap over price levels
  pool_allocator.hpp  fixed-capacity object pool + a new/delete baseline
  order_index.hpp     open-addressed id map + a std::unordered_map baseline
  spsc_ring.hpp       wait-free single-producer/single-consumer ring
  clock.hpp           counter access, clock probing, exact percentiles
  affinity.hpp        core pinning on Linux, QoS hint on macOS
  flow_gen.hpp        closed-loop synthetic order flow
  reference_book.hpp  the naive book the fast one is fuzzed against
  stream.hpp          record a stream for deterministic replay
  wire.hpp            on-disk format, shared with the Python capture tool
src/    engine_demo.cpp    two-thread engine, prints a live book
tests/  test_lob.cpp       unit tests + differential fuzz
bench/  bench_lob.cpp      throughput, latency, component and pipeline benchmarks
tools/  gen_flow.cpp  replay.cpp  capture_binance.py