Work / 1.2 Multitype Order Book in C++
Case study 1.2 · Quant · Systems
Multitype Order Book in C++
Several order types matched in one C++ book, with tests that pin price ordering and a measured latency benchmark.
- Date
- Mar 2024
- Role
- Author
- Stack
- C++, GoogleTest
Status: published. Certainty: The numbers are measured on OrderbookSim, the later repository with the corrected ordering, on one shared Apple M1 Pro; they include OrderbookSim’s history and neural-network bookkeeping, so they are not those of a bare matching engine. The tests, fixes and benchmark are in OrderbookSim pull request #8. The original repository had the bid and ask ordering reversed; its pull request #1 ports the fix.
Summary
This case study covers a C++ limit order book supporting Good-Till-Cancel, Fill-and-Kill, Fill-or-Kill, Good-For-Day and Market orders on a std::map baseline. The first version, in the original repository (March 2024), had its bid and ask ordering reversed, and its seven GoogleTest cases could not detect that. The later OrderbookSim repository corrected the ordering in January 2026. Its pull request #8 makes it build again, adds 30 tests that pin the matching contract, fixes four defects those tests found, and adds a seeded benchmark.
On one shared Apple M1 Pro, the median call takes 208 ns for an add, 125 ns for a cancel and 1,667–1,708 ns for a match that trades about three times; p99 is 625, 333 and 4,062–4,125 ns. These numbers are for OrderbookSim’s book as it stands, which also records order history and runs one neural-network training step per trade. std::map is 1.2% of that time, so the container is not what limits it.
Context and constraints
A limit order book brings together resting buy and sell orders and incoming instructions. Supporting several order types makes the contract more demanding than simply finding a compatible price: whether an order may rest, partially fill or expire is part of its behaviour.
The project states no latency, workload or memory budget, so the limits below record the measured workload and environment rather than targets.
| Limit | Value |
|---|---|
| Latency budget | None stated by the project, so there is nothing to compare against |
| Message mix and book depth | 54.9% add, 35.1% cancel and 10.0% aggressive, split about evenly across Good-Till-Cancel, Fill-and-Kill, Fill-or-Kill and Market; no modifies; mean 640 resting orders and about 38 price levels per side |
| Memory and allocation | No budget stated. Per call: 5.49 allocations and 20,867 bytes requested for an add, about 20.8 allocations for a match, none for a cancel. Peak resident memory 170 MiB, including about 64 MB of benchmark buffers; memory per resting order not measured |
| Event volume and run duration | 1,000 prefill orders, 100,000 untimed warm-up calls and 1,000,000 timed calls per repetition; 10 repetitions in 11 seconds |
| Execution environment | Apple M1 Pro, 16 GiB, macOS 27.0.1; Apple clang 21.0.0 with libc++, -O3 -DNDEBUG -std=gnu++20; shared, not isolated |
Correctness and speed are separate questions. The behaviours the tests pin are the starting point for accepting a change; a faster run cannot compensate for a different matching outcome. Equally, a passing behavioural suite does not establish a runtime bound or demonstrate suitability for a production venue.
My role
My role is author of the order-book project. The tests, fixes and benchmark described on this page are in OrderbookSim pull request #8, and the ordering fix for the original repository is in its pull request #1.
The idea came from a recommended practice project, a basic order book with a single order type; this version goes further, with multiple order types. I am not claiming an independently designed exchange architecture, a deployed trading system or an operating history beyond the evidence described here.
Architecture
Each side of the book is a std::map from price to a list of orders, with bids ordered by std::greater and asks by std::less after the correction. An unordered_map finds an order by id, and another holds per-price level data. In OrderbookSim, every addOrder also writes buy, sell and purchase history and a live-order map, and runs one neural-network training step per trade. The original repository has none of that bookkeeping.
The ladder below is a conceptual view of the matching boundary: an incoming market buy consumes available asks. In the repository’s own test data, a market order larger than the opposite side becomes a limit order at the worst opposite price, and its remainder rests there. That is this repository’s contract, not the usual exchange convention.
The original suite is one parameterised test over seven data files. They assert only order and level counts, have no Good-For-Day case, and their Fill-and-Kill case never reaches the path that cancels a remainder. The 30 tests added in pull request #8 cover price priority on both sides, first-in-first-out within a level, crossing, each order type, cancel, modify, a 20,000-call seeded random flow checked after every call, and book destruction. All 37 pass, 20 times each, and again under the address and undefined-behaviour sanitisers.
Key decisions
Container baseline. The choice in the current book is std::map, kept as the evaluation baseline. Profiling shows red-black-tree work is 1.2% of book time. Of the 45.5% spent in matching, 32.8 points are history and neural-network bookkeeping; hash-map work is 30.2% and operator new 16.1%. A different price-level container would barely move these numbers until those costs are dealt with.
Behaviour before optimisation. Tests that pin the contract come before any timing, so that a faster run can be checked for the same matching outcome. Each replayed benchmark call is also checked to produce the same number of trades as the first pass.
Separate results from presentation. The depth ladder stays schematic. The histogram’s shape below is illustrative; the measured counts are in the repository, and the measured percentiles are in the method box. No improvement is inferred from either chart.
Evaluation and results
The results are in RESULTS.md, with the raw output of the main run in results/main.
Method what is measured, and how
- Question
- What does supporting several order types cost on the matching path of the std::map baseline?
- Workload
- A flow from std::mt19937_64, seed 42: 1,000 prefill orders, 100,000 untimed warm-up calls, then 1,000,000 timed calls; passive orders within 50 ticks of the mid; mix and depth as in the limits above
- Hardware
- Apple M1 Pro, 10 logical CPUs, 16 GiB, on mains power; shared with other work, 1-minute load average 21–24 during the run
- Software
- macOS 27.0.1; Apple clang 21.0.0 with libc++; -O3 -DNDEBUG -std=gnu++20 (CMake Release); OrderbookSim revision 432ef48
- Controls
- No pinning, which macOS lacks; user-interactive priority instead. Prefill and warm-up replayed untimed before each timed pass; 10 repetitions on a fresh book with the same flow; steady_clock, 41.67 ns resolution, not overhead-corrected
- Reported
- Per call, median of 10 repetitions [IQR across repetitions], p50 / p99: add 208 [208–208] / 625 [594–625] ns; cancel 125 [125–125] / 333 [292–333] ns; Good-Till-Cancel match 1,667 [1,667–1,667] / 4,062 [4,042–4,125] ns, the other types within one timer tick at p50. Throughput 2,597,382 calls/s [2,547,452–2,627,365]
- Limiter
- History and neural-network bookkeeping, hash maps and allocation, not std::map (1.2% of book time; macOS sample, 8 s at 1 ms). The slowest add, 13.8 ms (median over repetitions), requests about 3.3 MB, mostly a rehash of a live-order map that never drops cancelled orders
- Reproduce
- OrderbookSim/bench/run.sh --reps 10 --seed 42; tests: cmake -S OrderbookSim -B build, cmake --build build, ctest --test-dir build
- Not claimed
- The speed of a bare matching engine, results on other hardware or compilers, modify latency, concurrent use, a speed-up over another implementation, production readiness or exchange equivalence.
OrderbookSim/bench/results/main/latency_histogram.csv. Illustrative dataOrder types cost little on the matching path. The four aggressive types match at the same p50 to within one timer tick. The Fill-or-Kill pre-check adds 41–63 ns at p99 with about 38 levels per side, and 104–188 ns with about 340.
Depth matters more. From about 9 to 38 to 340 levels per side, add p50 goes from 167 to 208 to 375 ns, cancel from 83 to 125 to 292 ns and match from 1.54 to 1.67 to 1.96 µs, and throughput falls from 3.09 to 2.60 to 1.79 million calls per second. These runs do not separate the map’s depth from the per-call allocation, which grows with the number of resting orders. A second seed changed throughput by about 5% and the p50s by at most one tick.
Allocation follows the bookkeeping. A match makes about 7 allocations per trade. About 20.9 KB is requested on every add and match because matching reserves room for a trade per resting order on every call, whether or not it trades.
What went wrong and limits
The original repository’s bid and ask comparators were reversed from convention: asks were ordered with std::greater and bids with std::less, and begin() was treated as the best level on both sides. The best bid was therefore the lowest and the best ask the highest, and the crossing check in the match loop was inverted too, as its own comment notes. This defect, recorded in the repository, was pending a fix until 7 January 2026, when OrderbookSim swapped the two orderings and corrected the crossing check (pull request #6). The consequences are now shown by tests: with that change reverted, a bid at 99 trades against an ask at 101, an aggressive sell hits the lowest bid, and 16 of 37 tests fail, while all seven original cases still pass (log).
That fix was merged into a tree that could not be built. A commit on 4 November 2024 removed method bodies that were still called, and the test file still included a header that had been renamed, so OrderbookSim’s main did not compile from then; pull request #8 restores the missing definitions. Once it built, the new tests exposed four more defects, each now fixed with a test that failed before: a self-deadlock when a Fill-and-Kill order partly fills, a destructor that could hang on a lost wake-up, an end-of-day routine that removed every order except the Good-For-Day ones, and a use-after-free in matching that the address sanitiser reported. The deadlock and the use-after-free also exist in the original repository; their fixes are not ported there.
Some defects are reported but not fixed in pull request #8. The live-order map never drops cancelled orders, so it grows without bound and causes the slowest adds. The neural network’s time-of-day input is always 0, yet localtime_r, which computes it, accounts for 9.3% of book time across all its callers; pull request #9 (open) fixes the input and builds the WebAssembly module behind the browser demo. The addOrder overload without an id derives one from the book’s size, so a new order can reuse a live id and be dropped silently.
The limits are evidential. The numbers come from one shared laptop with no pinning and a 1-minute load average above 20, which mostly affects the tails and the maximum. There is no Linux, GCC or x86 run, no hardware counters, no modify latency, no concurrent callers and no figure for memory per resting order. The Good-For-Day pruning thread, which acts at 16:00, never ran during the benchmark.
Next
Separate the history and neural-network bookkeeping from matching, so that the book itself can be timed; only then is a container change worth comparing against this std::map baseline. Repeat the benchmark on a quiet Linux machine with GCC and pinned threads, add modify latency and memory per resting order, and draw Fig. 1 from the measured counts.