nanobook — a C++20 HFT order book & matching engine

A C++20 NASDAQ TotalView-ITCH 5.0 limit order book and price-time matching engine, engineered and measured like production HFT infrastructure: a zero-allocation hot path clocked in nanoseconds, proven correct against a std::map oracle over millions of messages.

nanobook reconstructs a live limit order book from a real NASDAQ ITCH 5.0 feed and matches against it with price-time priority, on a hot path with zero heap allocation, zero exceptions, and zero virtual dispatch. It ships with a verification stack — differential testing against a std::map oracle, fuzzing, sanitizers, determinism replays, and a coverage check — strong enough to trust the performance numbers.

Numbers

Measured on Apple M4 (macOS 26.5, 16 GiB), Apple clang 21, release build (-O3 + LTO + -mcpu=native), on a busy corporate laptop (load1 ≈ 4) as the stable low end across repeated runs (±20%). Full methodology and per-number commands: docs/PERF.md; machine disclosure: docs/ENV.md.

Metric	Value
ITCH parser, parse-only throughput	~600 M msgs/s
Book add latency (p50)	31 ns → 13 ns → 17 ns (v1 → v2 → v3)¹
Book add latency (p99, v3)	~23 ns
Book cancel latency (p50)	25 ns → 14 ns → ~35 ns (v1 → v2 → v3)¹
Top-of-book best_bid/best_ask	O(1), p50 < 1 ns (all variants)
Replay throughput	2.4 M/s → 53 M/s → 35 M/s (v1 → v2 → v3)¹
Real-day replay (268.7M-msg NASDAQ session)	~0.8 M/s cold / ~13 M/s warm²
Hot-path heap allocations (shipping v3)	0 (proven over 200k ops)
Line coverage (src/book + src/engine)	98.9% (≥ 90% required)

¹ v2 (std::unordered_map id index) beats v3 (custom open-addressing) on the median — add 13 vs 17 ns, cancel 14 vs ~35 ns, replay 53 vs 35 M/s. We ship v3 anyway, on purpose: v2 allocates a heap node on every id insert on the hot path (caught red-handed by the ZeroAlloc.HotPathDoesNotAllocate test), and a per-op malloc is exactly the unpredictable p99.9 tail / non-determinism an HFT book must avoid. The objective is a bounded, allocation-free hot path (0 allocs over 200k ops), not median throughput — v3 delivers zero-alloc, v2 does not. The documented next optimization is a tombstone / periodic-rehash (or Robin-Hood) delete to also win the median without giving up zero-alloc. See docs/PERF.md and docs/DESIGN_NOTES.md.

² Real-day replay is indicative, not a headline benchmark: the full-day figure was measured on the busy laptop and dominated by 7.7 GiB of cold page-fault / mmap I/O (a warm re-run reached ~13 M/s). It confirms the book correctly and memory-boundedly processes a real 268.7M-message day; the microbenchmarks above are the CPU-cost numbers.

Real trading day

The shipping v3 book was run end-to-end over a full real NASDAQ TotalView-ITCH 5.0 session — 12302019 (Dec 30, 2019), the smallest complete day on the NASDAQ EMI index (7.7 GiB decompressed):

framed messages	268,744,780 (264.5 M in-scope)
distinct symbols	8,906
per-type mix	117.1 M add · 114.4 M delete · 21.6 M replace · 5.7 M execute · 2.8 M cancel
peak book depth (max over symbols)	5,608 levels
session	start('O') → end('C')
peak RSS	~2.7 GB (memory-bounded across 8,906 per-symbol books)
mid-session prices (2 GB prefix)	AAPL 285.88 / 285.91 · SPY 320.75 / 320.76 — in that day's public range
end-of-day book_hash	0 (see note)

Why the end-of-day book_hash is 0 — this is correct, not a bug. A full-session feed ends after the closing cross, by which point essentially every resting order has been withdrawn (deletes ≈ adds). Every symbol's EOD book is therefore empty, and the XOR of empty per-symbol hashes is 0. Reconstructed prices are instead validated on a mid-session prefix, where AAPL and SPY land in that day's published range with realistic (ETF-tight) spreads — independent confirmation the book reconstructs a real market, not just a self-consistent hash.

Processing this day is what forced the hybrid ladder + spillover design and the grow-small-per-symbol memory bounding (see Architecture and docs/DESIGN_NOTES.md): a pure dense ladder OOMed at 74 GB because one symbol's price span was ~2 billion ticks.

Verification

Correctness is a first-class deliverable, not an afterthought — the whole point is that the performance numbers are trustworthy.

• Differential lockstep — the fast OrderBook is driven in lockstep with a deliberately-simple std::map reference book over 1M ops × 20 seeds, comparing best_bid/best_ask/level_qty after every mutation and the full book_hash at the end.
• Property invariants — 1M synthetic messages × 50 seeds asserting never-crossed book, quantity conservation (no shares created or lost), and hash-determinism.
• 4-way golden agreement — an independent Python generator, the C++ parser, the reference book, and the replay tool all converge on the same order-independent book_hash = 2085432840951497505.
• Fuzzing — the ITCH parser survives 67.7M libFuzzer executions, 0 crashes under ASan + UBSan: the wire-decode-never-overreads safety property.
• Sanitizers — ASan / UBSan / TSan clean. TSan covers the optional threaded replay pipeline (parser and book on separate threads, handed off over a lock-free SPSC ring), which is asserted to reach a book state identical to the single-threaded path.
• Determinism — replaying the same stream always yields the same final book hash.
• Coverage — 98.9% line coverage on src/book + src/engine (llvm-cov), against a ≥ 90% requirement.
• CI — GitHub Actions on every push: gcc-13 + clang × release + asan (live status in the badge above).

Architecture

   NASDAQ ITCH 5.0 feed  (mmap'd, big-endian, 2-byte length-framed)
                          │  zero-copy, in-place iteration
                          ▼
   ┌───────────────────────────────────────────────┐
   │  parser  (src/itch)                             │  noexcept, alloc-free
   │  wire bytes ─▶ decoded event structs            │  byte-wise BE decode
   │  (itch_events.h) ─▶ handler.on_event(ev)        │  templated handler,
   └───────────────────────────────────────────────┘  no virtual dispatch
                          │  Book concept (book_api.h) — compile-time, no vtable
            ┌─────────────┴───────────────┐
            ▼                             ▼
   ┌────────────────┐          ┌──────────────────────────────────────┐
   │ RefBook        │          │ OrderBook (fast, v3, SHIPPING)        │
   │ std::map +     │          │ HYBRID book:                          │
   │ std::deque     │          │   dense ladder  near-touch (O(1) ToB) │
   │ (oracle)       │          │ + std::map spill  far-from-touch (~4%)│
   │                │          │ intrusive FIFO/level (O(1) cancel)    │
   │                │          │ object pool       (0 heap, zero-alloc)│
   │                │          │ open-addressing id→node hash          │
   └───────┬────────┘          └───────────────┬──────────────────────┘
           │      book_hash() order-independent │
           └────────────► differential ◄────────┘
                          lockstep (≥1M ops)
                                  │
                                  ▼
                 matching engine (src/engine) ─▶ Trade reports
                 price-time priority, partial fills

Quickstart

# Release build + tests
cmake --preset release
cmake --build --preset release
ctest --preset release

# Sanitizers (ASan + UBSan)
cmake --preset asan && cmake --build --preset asan && ctest --preset asan

Other presets: fuzz (libFuzzer parser harness, Homebrew LLVM clang — cmake --preset fuzz && cmake --build --preset fuzz --target fuzz_parser) and coverage (llvm-cov — bash scripts/coverage.sh prints the measured src/book+src/engine line-coverage number).

Replay a real (or synthetic) ITCH feed:

scripts/get_real_data.sh                       # fetch one full NASDAQ day into data/
./build/release/nanobook-replay data/12302019.NASDAQ_ITCH50 --stats --analytics
./build/release/nanobook-replay data/12302019.NASDAQ_ITCH50 --stats --threaded  # 2-thread pipeline
./build/release/nanobook-replay data/12302019.NASDAQ_ITCH50 --shards 8          # symbol-sharded

# Drive synthetic order flow through the price-time matching engine (seeded):
./build/release/nanobook-match --orders 100000 --seed 1

# Hardware-counter view of the hot loop (cache-miss rate + IPC on Linux):
./build/release/nanobook-perf --ops 5000000

Design highlights

• Zero heap allocation on the hot path — and proven, not asserted. A counting global operator new override verifies 0 allocations across 200k add/cancel/execute/replace ops (tests/test_zero_alloc.cpp). This test is why the shipping book uses the custom open-addressing index (v3) and not std::unordered_map (v2): v2 is faster at the median but allocates per id insert on the hot path, and the test fails the moment the production book aliases it.
• Hybrid dense-ladder + sparse-spillover book — like real matching engines. The liquid near-touch levels (~96% of adds) live in a bounded O(1) dense price ladder, with top-of-book served by a two-level occupancy bitmap (highest/lowest-set-bit, a few clz/ctz ops — genuinely O(1), not amortized-with-a-cliff); the rare far-from-touch levels spill into a per-side std::map. A pure dense ladder can't span a real equity price range (one symbol's span was ~2 billion ticks) — the hybrid keeps the common case cache-resident and the long tail correct.
• Two books, one shared contract. A std::map oracle and the fast hybrid book both satisfy a compile-time Book concept, so they run in lockstep with no shared memory layout — the fast book can't be "accidentally right".
• Lock-free concurrency, correct by construction. --threaded runs the parser and the book on separate threads over a wait-free single-producer/ single-consumer ring (src/common/spsc_ring.h, cache-line-isolated head/tail, acquire/release ordering); --shards N partitions symbols across N worker threads by stock_locate, each owning a disjoint set of books over its own ring, so workers never share book state — the lock-free architecture a real feed handler uses. Both are asserted to reach a book state identical to the serial path and are exercised under ThreadSanitizer (tests/test_pipeline.cpp). Honest caveat: on file replay the single-threaded parser is the bottleneck, so these do not beat serial wall-time here — the value shown is the correct, race-free hand-off mechanism, not a throughput win on this input. (A live multicast front end, where receive is the bottleneck, is where sharding pays — see docs/PRODUCTION_NOTES.md.)
• Honest performance engineering. Every number is measured on a disclosed (busy, ±20%) machine and reproducible by one documented command; latency is reported with tails (p99.9), and the deliberate v2-median-vs-v3-zero-alloc trade is explained rather than hidden.

Documentation

• docs/DESIGN.md — the "why": scope, type vocabulary, parser and book design, differential-testing philosophy, hot-path discipline.
• docs/PERF.md — measurement methodology + results tables.
• docs/ENV.md — machine + toolchain disclosure.
• docs/DESIGN_NOTES.md — engineering decisions & rationale.
• docs/PRODUCTION_NOTES.md — what a production feed handler adds (kernel bypass, NUMA, hardware timestamps, sharding) and the roadmap.

License

MIT — see LICENSE.