A low-latency, price-time-priority matching engine in C++20. It uses a direct-indexed price ladder, bitmap best-price tracking, intrusive FIFO queues, a flat open-addressed order-id map, and a huge-page arena allocator. It is validated against an independent reference engine over tens of millions of messages, and measured with a methodology that keeps throughput and latency as separate, correctly-labeled statistics.
Measured on an Apple M2 Max (arm64), -O3 -march=native. Reproduce with
./build/lob_bench, which prints these numbers for your own machine plus a full
reproducibility report.
Throughput (saturated loop, ns/op = elapsed / count):
| Operation | This engine | std::map baseline |
Speedup |
|---|---|---|---|
| cancel | 57 ns (18 M/s) | 350 ns (2.9 M/s) | 6.1x |
| add (resting) | 48 ns (21 M/s) | 67 ns (15 M/s) | 1.4x |
| realistic mix (93% cancels/replaces, touch-concentrated, bursty) | 43 ns/msg (23 M msg/s) | 59 ns/msg (17 M msg/s) | 1.4x |
Depth scaling (amortized ns/op as the live book grows). The ladder stays flat; the tree degrades. The gap is widest for cancel, the dominant real-world operation:
| Book depth | ladder cancel | std::map cancel |
|---|---|---|
| 1,000 | 20 ns | 69 ns |
| 100,000 | 30 ns | 141 ns |
| 1,000,000 | 53 ns | 329 ns |
Latency is measured under coordinated-omission-free replay at true trace
arrival rates, per operation type, into an HdrHistogram (p50 through p99.99). On
this Apple Silicon host the 24 MHz timer resolves the microsecond-scale tail but
not the sub-40 ns median (throughput above is the true service time); the harness
auto-selects the sub-nanosecond rdtscp timer on x86 Linux for a full latency
histogram.
Absolute nanosecond figures are from a quiet machine and drift with desktop load
on an un-isolated laptop; the speedup ratios are load-independent and stable. Run
./build/lob_bench for your own numbers, or an isolated core
for production-grade figures.
Verified three ways, all runnable via ctest:
- Differential fuzzing: 30 million messages across 120 flow regimes, spanning
IOC, FOK, post-only, iceberg, and self-trade-prevention order types, with
bit-for-bit trade-stream and full-L2-depth agreement against an independent
std::mapengine. Zero divergences. - Raw Nasdaq ITCH 5.0: a hand-written parser reconstructs the book and checks full-depth agreement against the reference at every checkpoint.
- Determinism and crash-recovery-by-replay: identical state hashes across runs, and replaying the input log reproduces exact state.
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build --output-on-failureC++20 and CMake 3.16+, no third-party dependencies.
./build/lob_bench # benchmark + reproducibility report
./build/lob_difftest --seconds 60 # differential fuzzing campaign
./build/lob_itch_replay # ITCH 5.0 parser, full-depth validated
./build/lob_determinism # determinism + replay recovery
./build/lob_spsc # lock-free parser-to-matcher handoff
./build/lob_cli # interactive order entry (HELP for commands)| Concern | Approach |
|---|---|
| Price to level | direct-indexed array ladder[tick - base], one load |
| Price drift | sliding window with rebasing |
| Best price | two-level occupancy bitmap + hardware bit-scan |
| Level queue | intrusive doubly-linked FIFO, O(1) cancel |
| Order storage | slab arena, huge/superpages, no malloc on hot path |
| Id lookup | flat open-addressed map, single combined array, one probe per cancel |
| Parser/matcher | wait-free SPSC ring, acquire/release, no false sharing |
Order types: limit, IOC, FOK, post-only, iceberg, and self-trade prevention.
Order is packed to exactly 32 bytes (two per cache line) with 32-bit intrusive
links. The engine is header-only in include/lob/.
include/lob/ engine headers (ladder, arena, bitmap, id map, ITCH, SPSC, clock, histogram)
apps/ bench, difftest, itch_replay, determinism, spsc_demo, cli
tests/ smoke (includes rebasing stress vs reference)
scripts/ get_itch.sh, setup_isolated_core.sh
docs/ PERF.md (hardware-counter analysis)
MIT.