Overview
A matching engine is easy to write and hard to trust. Being fast only counts if the book is still right after 263 million messages.
Toy order books are usually tested against a handful of hand-written orders. Real books are deep and messy: AAPL reaches 4,212 bid levels, and a third of all level changes happen 256 to 1,023 levels away from the best price. So this engine is driven by a real NASDAQ trading day, and every claim about speed or correctness is measured.
Results
| p50 | p99 | p99.9 | throughput | allocations |
|---|---|---|---|---|
| 51 ns | 223 ns | 609 ns | 36M msgs/sec | 0 per message |
AAPL, 2019-12-30, 1.51M book messages. Across every NASDAQ symbol for the full day (263M messages, 8,892 symbols) it sustains 6.1M messages a second on one core. Timed per message with rdtsc (including ~20 ns of timer overhead), median of 5 pinned, warmed-up runs on a Ryzen 5 5600H, g++ 13.3, -O3 -march=native.
How it's fast
Nothing is allocated on the hot path
Orders and price levels live in index-addressed pools with free lists, so freed slots are reused while still warm in cache. The replay tool swaps in a counting
operator new, so "zero allocations" is a measurement.32-byte orders, two to a cache line
Each price level's queue is an intrusive doubly-linked list threaded through the pool with 32-bit indices. Every order knows its level, so a cancel is one hash lookup and an unlink.
The best price in two instructions
Levels within ±2,048 ticks sit in an array indexed by tick, with a two-level occupancy bitmap. The next best price is a
countl_zeroand acountr_zero, however sparse the book.An id map that stays in cache
Open addressing with linear probing and backward-shift deletion, so no tombstones build up over a day. Sized for peak live orders, not the day's total.
No locks between threads
One thread owns the book. A feed thread hands it work through a lock-free SPSC ring: 1.7× the throughput of a mutex-guarded deque and about half the handoff latency (225 ns vs 435 ns p50).
Profiled, not guessed
perfon the AAPL replay: 123 cycles and 262 instructions per message (IPC 2.1), 0.83 cache misses and 1.4 branch misses.
How I know it's right
| Check (full 2019-12-30 file) | Result |
|---|---|
| Every NASDAQ execution hit our best bid or ask | 60,543 / 60,543 ✓ |
| Hidden-order prints fell inside our spread | 7,178 / 7,178 ✓ |
| An independent, deliberately simple rebuild agrees at top of book after every message | 1.5M / 1.5M ✓ |
| Every crossed book explained by a halt, pause or reopening cross | 8,649 / 8,649 ✓ |
| Deliberately injected bugs caught by the test suite | 14 / 14 ✓ |
Plus differential fuzzing against a naive reference book (trades, depth and quantity conservation checked after every operation), and CI running ASan, UBSan, ThreadSanitizer, libFuzzer, g++, clang and a Windows build.
Architecture
What I'd do next
The price-ladder band is centred on a book's first order and never moves, so a stock that trades far from its open falls back to a slower sorted-vector path (still correct). Across all symbols the replay is memory-bound, since consecutive messages usually touch different books, so software prefetching of the next message's book is the obvious next step.