A price-time-priority limit order book and matching engine in C++23, built for sub-microsecond tail latency and honest measurement.
Status: implemented and benchmarked. FastBook, the production engine, is complete (bitmap ladder, intrusive pool, dense-id cancel, IOC/FOK/PostOnly/STP, incremental L2, seqlock BBO), differential-verified against two reference books (11 M+ checks, ASan+UBSan clean), replay-validated against a real NASDAQ ITCH 5.0 day (engine-vs-feed: 0 violations on AAPL + MSFT full days), wrapped in an OUCH 4.2 order-entry gateway (scripted inbound messages -> FastBook -> report stream, differential vs MapBook, hash pinned), and measured at ~16.6-18.5 ns/op mixed against four vendored alternatives. Numbers are machine-specific (WSL2/i5-1335U) and only interleaved runs are comparable — see How it compares.
| Document | What it is |
|---|---|
| PLAN.md | The full plan: reference-repo verdicts, architecture, exact memory layouts, 10 phases, optimization catalog, benchmark protocol, acceptance gates |
| PLAN.md §1.1 | The interesting part. Four planning assumptions tested against real hardware, and what broke |
| DECISIONS.md | The pre-build choices and their resolutions (defaults accepted, all landed) |
| docs/PROBES.md | How to rebuild and rerun every measurement below |
| To_Research.md | Study guide + decision log for the OUCH order-entry gateway (done) and command journaling (next) |
| replay/README.md | ITCH replay + OUCH gateway: fixtures, gates, current results |
Flat tick-indexed price ladder (no tree, no pointer chasing) with a three-tier occupancy
bitmap, so best-price recovery is three bit-scans and is independent of book sparsity.
Orders are 32-byte intrusive nodes linked by 32-bit indices in a preallocated pool, two per
cache line, giving O(1) cancel with no allocation on the hot path. Bids are mirror-indexed so
both sides compile to the same tzcnt. One thread owns one book and takes zero locks;
concurrency lives only at the edges (SPSC ring in, seqlock out) and scale-out is by sharding
symbols, never by parallelizing one book.
flowchart LR
subgraph feed["Market data (real)"]
ITCH["NASDAQ ITCH 5.0 daily file<br/>(4.4 GB, 368M records)"]
EX["itch_extract - filter one symbol"]
FX["committed fixture<br/>(replay/data/)"]
end
subgraph engine["FastBook - one thread, zero locks"]
LAD["flat tick ladder<br/>2 x 65,536 levels"]
BM["3-tier occupancy bitmap<br/>best = 3 bit-scans"]
POOL["intrusive order pool<br/>16 B hot node + cold sidecar<br/>zero alloc on hot path"]
DIRTY["incremental L2 change-set"]
SEQ["seqlock BBO"]
end
subgraph out["Outputs"]
DELTAS["take_deltas() - L2 updates"]
BBO["read_bbo() - wait-free top of book"]
VAL["engine-vs-feed validator<br/>0 violations on full trading day"]
BENCH["benchmarks: 16-18 ns/op mixed<br/>p99.9 140-464 ns"]
end
subgraph ouch["OUCH 4.2 order entry (done)"]
OWIRE["scripted inbound stream<br/>(replay/data/ouch_demo.bin)"]
GW["OuchGateway<FastBook><br/>token -> engine id, chain accounting<br/>report stream (A/U/C/E/J/S)"]
OREP["differential vs MapBook<br/>byte-identical reports, hash pinned"]
end
ITCH --> EX --> FX --> REPLAY["replay/ (0 rejects)"] --> LAD
FX --> VAL
ORDERS["orders (limit/market/IOC/FOK/PostOnly)"] --> LAD
LAD --> POOL --> DIRTY --> DELTAS
LAD --> SEQ --> BBO
LAD --> BENCH
VAL --> LAD
OWIRE --> GW --> LAD
GW --> OREP
Everything is measured, nothing is assumed: 23 probes settle every design choice against this machine, the differential suite runs 11 M checks per build, the engine-vs-feed validator replays the engine against the exchange's own executions for a full trading day, and the OUCH gateway drives FastBook from scripted wire messages with a byte-identical FastBook-vs-MapBook report differential (3,885 checks, hash pinned).
Same 300k-op stream (60% add / 30% cancel / 10% market), same harness (min-of-25, batched, engine-direct — id translation off the timed path), same machine, books interleaved in the same minutes. That is the only comparison this repo trusts; day-over-day numbers drift ~±1 ns/op on the WSL2 VM. Fresh run at the current commit (2026-08-06, 5 interleaved rounds, min-of-5; full methodology in docs/COMPARISON.md):
| book | mixed ns/op (min-of-5) | vs FastBook |
|---|---|---|
| karanshah/lob (closest rival) | 15.70 | ~14% faster |
| FastBook (this repo) | 18.32 | — |
| TheYellowDuck | 23.69 | ~29% slower |
| go_orderbook (Go, wall-clock incl. GC) | ~720 | ~39x slower |
All four engines produce the identical execution stream — 192,865 fills per 300k ops and the same final book — so the comparison is over the same work, not different workloads. (hsdxpro ~19 ns/op mixed and HFT-Orderbook primitives are compared on their own benchmarks; methodology-incomparable, documented in COMPARISON.md. exchange-core is a different tier: a full exchange core doing ~100x more work per op, compared as a documented table.)
Worse — mixed-flow throughput, ~9-14%. The gap is the price of features karanshah does not have; the causes are measured, not guessed (BASELINES.md "Tier 1 speedups" + "Round 2"):
- Incremental-L2 bookkeeping on the hot path: dirty-set + order-count
tracking cost ~0.45-0.98 ns/op of mixed. karanshah has no market-data out.
It is a real feature, not dead weight:
TrackMd=falserecovers most of it. - Best-price maintenance: karanshah caches bid/ask scalars; FastBook walks the occupancy bitmap after each match/cancel. Flat in book depth, but not free.
- No reduce(): karanshah lacks it, so the Tier A stream is reduce-free to keep the comparison fair. FastBook's reduce is exercised everywhere else (differential tests, real-data replay, the OUCH gateway).
Better — features and validation the latency table does not show:
- reduce(), IOC/FOK/PostOnly, all 4 STP modes, and priority-preserving replace (venue U semantics). karanshah supports only plain limit adds and cancels.
- Incremental L2 change-set + wait-free seqlock BBO — a market-data feed out of the box. karanshah is book-only.
- Engine-vs-feed validation: FastBook's real matching replayed against a full NASDAQ trading day (AAPL + MSFT), 0 violations. karanshah has no replay or validation story.
- OUCH 4.2 order-entry gateway: parse scripted order-entry messages, drive FastBook, emit the report stream, differential vs MapBook.
- Config levers that turn latency into a deployment choice: cancel at
70k live orders is 40.5-43.4 ns on the default config and 22.9-24.4 ns
with
TrustedIds+TrackMd=false+TC=16384— pure template configuration, no code change. - Zero-allocation hot path, dense-id O(1) cancel flat from 70k to 1M orders, and 11M+ differential checks against two independent reference books every build.
The honest summary: karanshah is ~10% faster on mixed flow and this repo is ~10x more complete — reduce, order types, market-data out, real-data validation, an order-entry gateway, and deployment levers. Feature breadth is not latency, and the latency is the price of the features.
Everything below was measured on the target machine before any engine code was written. Four assumptions were wrong, and two would have produced plausible-looking false benchmarks.
| Assumption | Reality |
|---|---|
| "Pin to a P-core, mandatory" | Impossible. WSL2 reports a fake topology; all 12 vCPUs measure identically. Now disclosed, not claimed. |
Fenced rdtscp per operation |
17.7 ns overhead vs a 20 ns target, and its lfence kills the ILP the engine exploits. Replaced by a two-tier harness (batched → 0.93 ns/op). |
MAP_HUGETLB just works |
Fails by default. Now a 3-way fallback, reporting the tier obtained. |
| Gates hold at any book size | False. Random cancel degrades 16x from 10 k to 2 M orders. Gates scoped by book size, always published. |
| Bitmap wins because it traverses fast | Backwards. It loses read-only scans by ~13x to a sorted vector. It wins on level mutation, which is what a book actually does. |
| 16 B hot/cold node split would help (predicted) | Confirmed, ~1.7x at 1 M orders. Took three attempts to measure honestly: 1.83x (single run) → 1.2-1.44x (median) → 1.29-2.02x (min-of-25). |
| Huge pages are a Tier-2 win | No, 1.00-1.05x. A single run said 2.14x; the median said 1.1x; min-of-25 says essentially nothing. |
| Median is a fine estimator for A/B benchmarks | No. Noise is additive and positive, so min-of-N is ~3.7x more reproducible (3.6% vs 13.5% spread). Using the median produced both a false positive and a false negative. |
Open addressing is ~2x faster than unordered_map (borrowed) |
False here, 0.96-1.43x. The real win is dense direct indexing: 2.8-16.2x faster and flat at ~2.2 ns from 70 k to 1 M orders. |
| Level prefetch is a "real advantage over trees" | Small and conditional. ~3-5% on sparse books only; hurts tight books. Demoted to Tier 3; distance-gated variant proposed. |
| Batched bitmap clears help | Only on sparse books (2.2-2.7x). Lose 6x on tight books. Immediate stays default; threshold-gated variant proposed. |
| Codegen tuning helps (O3/PGO/branch hints) | Within noise here (0.94-1.03x). Settled on -O2 -march=native; re-measure only with engine evidence. |
| A 64-bit divide on every add must be worth removing | No, it is free. Deleting it entirely changed nothing (5.98-6.17 vs 5.97-6.27 ns); replacing it with a tick_size==1 branch cost +2.4 ns/op, 9/9 runs. The out-of-order window already hid the divide behind the dependent loads; the branch did not fit. |
| Prefetching the next maker helps matching (the faster rival does it) | Regressed 6/6 runs (~0.3-0.4 ns). This book's levels are shallow, so the prefetched node is usually never touched. |
The codegen row is the most consequential. The memory-access floor, with no matching logic at all:
| orders | pool | cancel floor | 20 ns gate |
|---|---|---|---|
| 70,000 | 2.14 MiB | 4.60 ns | ✅ |
| 500,000 | 15.26 MiB | 13.15 ns | ✅ |
| 1,000,000 | 30.52 MiB | 24.38 ns | ❌ |
| 2,000,000 | 61.04 MiB | 33.96 ns | ❌ |
Cancel is a dependent load chain (id→node→prev→next→level). Once the pool outgrows L2 then L3, that is DRAM latency, and no engine optimization removes it. A latency number published without its book size is not a claim.
This finding then paid off, after three attempts at measuring it honestly. It predicted that halving the order node would extend the cache-resident range. Measuring that prediction turned out to be harder than making it:
| attempt | estimator | hot/cold gain | huge pages |
|---|---|---|---|
| 1 | single run | 1.83x | 2.14x |
| 2 | median of 15 | 1.2-1.44x | ~1.1x |
| 3 | min of 25 | 1.29-2.02x | 1.00-1.05x |
Attempt 1 was noise: re-running the same binary gave 0.73x to 2.52x. Attempt 2 fixed that but introduced a subtler error, and I wrongly concluded the machine had a ~1.4x "noise floor" and retracted a real win. Attempt 3 identified the actual problem: benchmark noise is additive and positive, so the minimum of N trials estimates true cost, while the median carries half the noise. Measured directly, min is ~3.7x more reproducible than median (3.6% vs 13.5% spread across independent repetitions).
The settled result, reproduced across 4 repetitions: the 16 B split is worth 1.65x at 1 M orders (1.29-2.02x across the range), and decisively, at 1 M the 32 B node fails the 20 ns cancel gate (21.60 ns) while the 16 B node passes (13.10 ns) every time. That extends the viable book from ~700 k to ~1.5 M resting orders. Huge pages, meanwhile, are worth essentially nothing here.
The architecture rests on "bitmap ladder beats a tree". That came from the literature, so it
was measured here on the workload a live book actually runs: levels created and destroyed at
a moving touch, with best-price queried after every change. All three structures replay an
identical op stream, and the bitmap is differentially verified against std::set first
(800 k checks, 0 errors, ASan+UBSan clean).
| book levels | bitmap | std::map |
sorted vector |
|---|---|---|---|
| 20 | 6.73 ns | 36.81 ns (5.5x) | 16.16 ns (2.4x) |
| 500 | 5.38 ns | 39.85 ns (7.4x) | 24.41 ns (4.5x) |
| 2000 | 5.83 ns | 38.69 ns (6.6x) | 27.65 ns (4.7x) |
The bitmap is also flat in book size while both competitors degrade. But on read-only traversal it loses to a sorted vector by ~13x, so the usual explanation ("it's fast to walk") is wrong. The win is level insert/delete plus best-price recovery. Testing only the traversal case would have wrongly condemned the design.
Also established: the environment's noise floor is p99.9 = 26.1 ns, so a sub-microsecond p99.9 headline is genuinely measurable here, while max = 298 µs from hypervisor preemption means p99.99 and max will be published but never claimed.
bash docs/verify_probes.sh # rebuilds all 5 probes -Wall -Wextra clean, reruns them
bash docs/scaling_sweep.sh # the cache-cliff table above
bash docs/check_docs.sh # asserts these docs agree with each otherRequires WSL2 or Linux with g++-14. See docs/PROBES.md.
MIT