A limit order book built for the two things exchange-adjacent systems are actually judged on: how long an update takes, and whether the same input always produces the same output.
Header-only C++17, no dependencies, no allocation on the hot path.
make test # correctness + replay determinism
make bench # latency and throughput
Most order-book samples optimise for looking clever. This one optimises for the two properties a trading system is debugged on at 3am:
- Determinism. A capture is a byte array. Replaying it twice produces a
bit-identical fill stream, verified by a digest over
(taker, maker, price, qty)in order. When two runs disagree, the input is identical by construction, so the bug is in the book. No hash-order iteration, no floating point in the matching path, no clock reads inside the book. - A flat cost model. Add and cancel are O(1). Cancel matters most: in real equity feeds most orders never trade, they are cancelled, so a cancel that searches is a cancel that dominates your latency profile.
| Concern | Choice | Cost |
|---|---|---|
| Price lookup | Dense ladder indexed by tick | ~4.8 MB for 200k ticks, O(1) address arithmetic |
| Queue at a price | Intrusive doubly-linked list over a slab | O(1) insert and unlink, no per-order allocation |
| Best bid/ask | 64-bit occupancy bitmap + clz/ctz scan |
O(levels/64) worst case, one word in practice |
| Order id → slot | Open-addressed table, fixed capacity | No rehash mid-run, deterministic probe order |
| Book full | Explicit reject counter | A visible reject beats silent slab corruption |
A tree would be asymptotically tidier and slower: every update would pay pointer chasing and branch misprediction to save memory that is not scarce.
Quantity reductions via amend keep queue position, matching real venue
behaviour; increases go to the back. That distinction is tested, because getting
it wrong silently changes fill order for every order behind you.
Apple M4 Max, Apple clang 17, -O2, single thread, process not pinned.
The user-space monotonic clock here has a 41 ns floor — coarser than one book update. Timing a single operation against it measures the clock, not the book. So two separate things are reported and not blurred together:
Amortised per-op cost — tight loop of 200,000 operations of one type, total time divided by count. Reliable below the clock floor because the loop spans millions of ticks. These are the numbers worth quoting.
| op | cost |
|---|---|
| add | 30.6 ns |
| cancel | 12.0 ns |
| cross (one resting order consumed) | 18.9 ns |
Mixed replay — 2,000,000 synthetic events, 44% cancel / 8% amend / 12% IOC / 36% limit, mid price random-walking across the ladder.
throughput 8.62 M events/s
fills 78,417
cancels 698,427
rejects 0
Per-event tail from the same replay. Each timing includes one clock read;
<41 means the measurement sat at or under the clock floor.
| op | n | p50 | p99 | p99.9 |
|---|---|---|---|---|
| add | 719,137 | 83 ns | 209 ns | 709 ns |
| cancel | 850,052 | <41 ns | 542 ns | 1000 ns |
| cross | 430,811 | <41 ns | 458 ns | 625 ns |
Observed maxima are in the low milliseconds and reflect scheduler preemption, not book work — the process is neither pinned to a core nor run at real-time priority. Reporting them as book latency would be dishonest.
include/mbook/order_book.hpp the book
include/mbook/feed.hpp wire format, replay, fill digest
tools/gen_feed.cpp seeded synthetic feed generator
tests/test_lob.cpp 9 correctness checks + determinism
bench/bench_lob.cpp the harness above
Price-time priority within a level, price priority across levels, limits that must not cross beyond their price, best-bid recomputation after the touch is cancelled, IOC leaving no residual, amend-down keeping priority, amend-up losing it, level quantity tracking through partial fills, and replay determinism over the generated feed.
MIT.