matchbox

A single-instrument limit-order-book matching engine in modern C++20 — the core data-structure-and-invariants problem at the heart of every exchange. Header-only, zero dependencies, property-tested, and benchmarked at ~8.6M orders/second single-threaded.

N 1 S LIMIT 100 10      ->  ACCEPT  #1 SELL rest 10 @ 100
N 2 B LIMIT 101 4       ->  TRADE   #2 x #1  4 @ 100   (price-time priority)

What it does

• Price-time priority. Incoming orders match resting orders best-price-first, then FIFO within a price level. Executions print at the resting (passive) order's price, so the aggressor gets price improvement.
• Order types: LIMIT (rest the remainder), MARKET (cross at any price, drop the remainder), IOC (immediate-or-cancel), FOK (fill-or-kill: all at once or reject — pre-checked against available depth).
• Cancel in O(1) via an id → location index.
• The book is never left crossed, quantity is conserved, and replay is deterministic — all enforced by tests (below).
• L2 depth snapshots and best-bid/ask queries.
• Events (accept / trade / cancel / unfilled / reject) are delivered through an EventSink, so callers can record, stream, or ignore them at zero cost.

Design

Each side is a std::map keyed by price (bids descending, asks ascending), so the best level is always begin(). Within a level, resting orders live in a std::list (stable FIFO, O(1) erase from the middle). An OrderId → {side, price, list-iterator} hash index makes cancels O(1). Each level caches its aggregate quantity for O(1) depth and fill-or-kill checks.

submit / cancel are O(log L + f) where L = distinct price levels and f = resting orders consumed by the fill. Prices are integer ticks (int64) — no floating-point money.

include/matchbox/
  types.hpp        Order/Side/Trade value types
  order_book.hpp   the engine (header-only)
app/matchbox_cli.cpp   stdin-driven replay/demo driver
tests/                 zero-dep test harness + suite
bench/bench.cpp        throughput + latency benchmark

Build & test

Standard CMake; needs only a C++20 compiler. No third-party packages.

cmake -G Ninja -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build
ctest --test-dir build --output-on-failure
./build/mb_bench 2000000          # run the benchmark

CI builds with gcc and clang, treats warnings as errors (-Wall -Wextra -Wpedantic -Wshadow -Wconversion), and re-runs the whole suite under AddressSanitizer + UndefinedBehaviorSanitizer.

Tests

The suite (tests/test_order_book.cpp) covers each order type and the priority rules, plus two properties that catch the subtle bugs:

• Fuzz / invariants — 40k randomized submits & cancels; after every operation it asserts the book is not crossed, level totals and the id-index are consistent, and that quantity is conserved (resting == accepted − traded − cancelled).
• Deterministic replay — the same input stream always produces an identical execution stream.

Benchmark

Mixed workload (80% passive limits around a random-walking mid, 20% aggressive IOC), single thread:

metric	value
throughput	8.6M orders/s
latency p50	~100 ns
latency p99	~300 ns
latency p99.9	~700 ns

(MSVC 19.44, Release, one core; timer granularity ~100 ns. Numbers vary by machine — run mb_bench to reproduce.)

CLI

N <id> <B|S> <LIMIT|MARKET|IOC|FOK> <price> <qty>   submit
C <id>                                              cancel
B                                                   best bid / ask
D <n>                                               n depth levels per side

./build/matchbox_cli < scenario.txt

Roadmap

• Array/tick-indexed book for O(1) best-price access at the extreme end.
• Self-trade prevention and order amend (in-place quantity reduce keeps priority).
• A binary wire protocol + TCP gateway, and an L2 market-data feed.

License

MIT