C++17 · Header-only core · Zero heap allocations in the matching hot path (verified in CI) · P99 ~400-500 ns Runs on macOS Apple Silicon (M1/M2/M3), macOS Intel, and Linux
A limit order book with a matching engine, built to demonstrate — and correctness-check — the core techniques used in HFT and low-latency execution systems: a free-list memory pool, a lock-free SPSC ring buffer, and an open-addressing hash map, all with zero heap allocations on the hot path.
There's a WASM visualiser in docs/ (order book, trade tape, latency histogram, mid-price chart). It isn't currently built or deployed — see wasm/build.sh to build it locally with Emscripten; docs/index.html will tell you it's missing orderbook.wasm if you open it without building first.
-O3 -march=native · 5,000,000 messages · seed 42 · real producer/consumer threads (see Architecture)
Measured on a shared cloud CI runner — numbers on dedicated hardware (bare-metal Xeon/Apple Silicon) will be tighter and less noisy. Run make run on your own machine for numbers that mean something for your hardware.
| Metric | Pool book (this repo) | std::map baseline |
Improvement |
|---|---|---|---|
| Throughput | 4.83 M msg/s | 2.09 M msg/s | 2.3× |
| P50 latency | 85 ns | 210 ns | 2.5× |
| P90 latency | 184 ns | 472 ns | 2.6× |
| P99 latency | 424 ns | 1 007 ns | 2.4× |
| P99.9 latency | 649 ns | 36 032 ns | 55× |
| Max latency | 7.2 ms | 129.6 ms | 18× |
The P99.9 gap is still the real story — std::map has unpredictable spikes from heap-allocator contention and tree rebalancing that the pool book (verifiably, see Zero heap allocations, verified below) doesn't have.
Max latency for both books is now milliseconds, not the sub-2µs numbers an earlier version of this README showed — that's not a regression, it's honesty: this benchmark now runs the feed generator and the matching engine on two real, separately-scheduled threads (previously it didn't — see Architecture), so occasional OS scheduling jitter on a shared runner shows up in the tail exactly like it would in a real deployment. P50/P90/P99 — the numbers that matter for steady-state throughput — are barely affected.
- Quick start (macOS M1)
- Architecture
- Zero heap allocations, verified
- Component deep-dive
- Project structure
- Build & run
- Git workflow
- Interview talking points
- Resume snippet
This is a real thread split, not just a conceptual diagram — src/main.cpp's run_threaded_benchmark() spawns an actual std::thread running FeedSimulator::generate() as the producer, while the calling thread pops and matches as the consumer. Per-message latency is timed on the consumer side only, around the add_limit_order / add_market_order / cancel_order call itself.
┌─────────────────────────────────────────────────────────────────────┐
│ FEED LAYER │
│ │
│ FeedSimulator │
│ ┌────────────────────────────────┐ │
│ │ 70% Limit 20% Cancel │ │
│ │ 10% Market │ push(OrderMessage) │
│ │ │──────────────────────► │
│ │ Mid price random-walks │ │
│ │ Price ± 10 ticks of mid │ │
│ └────────────────────────────────┘ │
└──────────────────────────────────┬──────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────────┐
│ TRANSPORT LAYER │
│ │
│ SPSCRingBuffer<OrderMessage, 1M> │
│ │
│ Producer (feed thread) Consumer (engine thread) │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ head_ │ ◄──cache line──►│ tail_ │ │
│ │ (atomic) │ (separate!) │ (atomic) │ │
│ └─────────────┘ └─────────────┘ │
│ │
│ [ msg ][ msg ][ msg ][ msg ][ msg ][ msg ][ msg ][ msg ]... │
│ ↑ tail head ↑ │
│ (consumer reads) (producer writes) │
└──────────────────────────────────┬──────────────────────────────────┘
│ pop() → OrderMessage
▼
┌─────────────────────────────────────────────────────────────────────┐
│ MATCHING ENGINE │
│ │
│ switch(msg.type) │
│ ├── Limit → add_limit_order() │
│ ├── Market → add_market_order() │
│ └── Cancel → cancel_order() │
│ │
│ Each call time-stamped → LatencyStats.record(Δt) │
└──────────────────────────────────┬──────────────────────────────────┘
│
▼
┌─────────────────────────────────────────────────────────────────────────┐
│ ORDER BOOK │
│ │
│ BID SIDE ASK SIDE │
│ │
│ best_bid_ ──►[102]──►[101]──►[100] [100]◄──[101]◄──[102]◄──best_ask_ │
│ │ │ │ │ │ │ │
│ [ord] [ord] [ord] [ord] [ord] [ord] │
│ │ │ │ │
│ [ord] [ord] [ord] │
│ │
│ Each price level: FIFO doubly-linked list of Order* │
│ Price level list: intrusive sorted doubly-linked list │
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ order_map_ OrderId → Order* (O(1) cancel lookup) │ │
│ │ bid_levels_ Price → Level* (O(1) level lookup) │ │
│ │ ask_levels_ Price → Level* (O(1) level lookup) │ │
│ └─────────────────────────────────────────────────────────┘ │
└──────────────────────────────────┬──────────────────────────────────────┘
│ on_trade(Trade&)
▼
[ Trade Callback ]
trade_count++, logging, P&L, etc.
┌──────────────────────────────────────────────────────────────────┐
│ STATIC MEMORY (no heap) │
│ │
│ MemoryPool<Order, 1 048 576> 67.1 MB │
│ ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐ │
│ │ slot │ slot │ slot │ slot │ slot │ · │ · │ · │ │
│ │ 0 │ 1 │ 2 │ 3 │ 4 │ │ │ │ │
│ └──────┴──┬───┴──────┴──────┴──────┴──────┴──────┴──────┘ │
│ │ free list ptr │
│ ▼ │
│ free_head_ → [slot N] → [slot N-1] → [slot N-2] → nullptr │
│ │
│ MemoryPool<PriceLevel, 65 536> 3.1 MB │
│ ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐ │
│ │ lvl │ lvl │ lvl │ lvl │ lvl │ · │ · │ · │ │
│ └──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘ │
│ │
│ OrderBookTables (3× FlatMap, open-addressing) 40.1 MB │
│ ┌────────────────────────────────────────────────────────┐ │
│ │ order_map_ FlatMap<OrderId,Order*, 2 097 152> │ │
│ │ bid_levels_ FlatMap<Price, Level*, 131 072> │ │
│ │ ask_levels_ FlatMap<Price, Level*, 131 072> │ │
│ │ each: inline keys[]/values[]/state[] arrays, │ │
│ │ linear probing + tombstones, no heap traffic │ │
│ └────────────────────────────────────────────────────────┘ │
│ │
│ SPSCRingBuffer<OrderMessage, 1 048 576> 67.1 MB │
│ ┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐ │
│ │ msg │ msg │ msg │ msg │ msg │ · │ · │ · │ │
│ └──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘ │
│ │◄─64 byte─►│ (each OrderMessage = 1 cache line) │
│ │
│ Total: ~177 MB static — see 'make check-zero-alloc' below │
└──────────────────────────────────────────────────────────────────┘
OrderMessage arrives
│
▼
┌─────────────┐ ┌─────────────────────────────────────────┐
│ pool.alloc()│ │ MemoryPool — O(1) free-list pop │
│ ~2 ns │ │ No malloc, no lock, no system call │
└──────┬──────┘ └─────────────────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────────────────┐
│ MATCH LOOP │
│ │
│ while qty_remaining > 0 AND opposite best exists: │
│ if price does NOT cross → break │
│ fill = min(aggressor.qty, passive.qty) │
│ emit Trade callback │
│ passive.qty -= fill │
│ if passive.qty == 0 → dequeue + pool.deallocate() │
│ if level.count == 0 → remove level + pool.deallocate() │
└──────┬───────────────────────────────────────────────────────┘
│
▼
qty_remaining > 0?
├── YES → insert_into_book()
│ hash lookup (bid/ask_levels_) → O(1)
│ level exists?
│ ├── YES → append to FIFO tail
│ └── NO → pool.alloc() new PriceLevel
│ insert_level_sorted() into intrusive list
└── NO → pool.deallocate(order)
(fully filled — nothing rests)
Without padding (WRONG):
┌───────────────────────────────────────────────────────┐
│ cache line 0 │
│ [head_:8][tail_:8][... buffer ...] │
│ ↑ producer writes ↑ consumer writes │
│ CACHE PING-PONG — ~100 ns penalty per operation │
└───────────────────────────────────────────────────────┘
With padding (THIS REPO):
┌───────────────────────────────────────────────────────┐
│ cache line 0 (producer owns) │
│ [head_:8][padding:56] │
└───────────────────────────────────────────────────────┘
┌───────────────────────────────────────────────────────┐
│ cache line 1 (consumer owns) │
│ [tail_:8][padding:56] │
└───────────────────────────────────────────────────────┘
No sharing → no coherency traffic → producer and consumer
run at full speed on separate cores
Order and PriceLevel objects have always come from MemoryPool. But
order_map_, bid_levels_, and ask_levels_ used to be std::unordered_map
— a node-based container that heap-allocates on every insert and frees on
every erase, regardless of whether the values it stores are pooled. That
meant the "zero heap allocations" claim was true for order/level objects but
false for the map bookkeeping around them: measured with an allocation
counter, the matching loop alone made 164,710 malloc() calls while
processing 200,000 messages — not zero.
All three maps are now FlatMap (include/flat_hash_map.hpp): a
fixed-capacity, open-addressing hash map with keys/values/slot-state stored
in plain inline std::arrays, sized generously (2× the pooled-object
capacity) to keep the load factor low. No pointers, no nodes, no heap.
This is checked automatically, not just asserted in prose:
make check-zero-alloctests/check_zero_alloc.cpp overrides the global operator new/delete
(portable across Linux and macOS, unlike an LD_PRELOAD malloc shim),
generates a batch of messages up front, resets the counter, then runs
that batch through add_limit_order / add_market_order / cancel_order.
It fails the build if that count is nonzero. It's part of scripts/check_regression.sh
and runs in CI on every push, so a future change that reintroduces heap
traffic on the hot path breaks the build instead of quietly rotting a claim
in this README.
The tradeoff: FlatMap's inline storage means a fully-sized instance is
large (sizeof(OrderBookTables) == 40.1 MB, see Memory layout below).
There's no rehashing or growth — capacities are fixed at compile time based
on MAX_ORDERS / MAX_LEVELS, which is the right tradeoff for a matching
engine where the maximum number of live orders/price levels is a known
bound, but it does mean OrderBookTables needs static/namespace-scope
storage duration, not stack storage — see the comment on OrderBookTables
in order_book.hpp for why (a stack-local OrderBook that owned these by
value blew the default thread stack).
Fixed-size free-list object pool. All storage is a std::array<Slot, N> allocated inline — the pool object itself is placed in BSS (static storage) so there is no heap call even for the pool itself.
allocate() → free_head = free_head->next (~2 ns)
deallocate() → node->next = free_head; free_head = node (~2 ns)
The FreeNode pointer is stored inside the free slot — the slot is large enough to hold it (enforced by static_assert). No extra metadata array needed.
Single-Producer Single-Consumer lock-free queue.
pushloadstailwithacquire, storesheadwithreleasepoploadsheadwithacquire, storestailwithrelease- Power-of-two capacity →
index & MASKreplaces modulo alignas(64)on head, tail, and buffer — each on its own cache line
The hot path is a single pointer-chasing loop through pre-allocated nodes, plus FlatMap lookups for order-id → order and price → level. No heap calls anywhere in this file — see Zero heap allocations, verified.
| Operation | Complexity | Hot path allocations |
|---|---|---|
add_limit_order |
O(fills) | 1 Order, 0–1 PriceLevel (both pooled) |
add_market_order |
O(fills) | 1 Order (immediately freed, pooled) |
cancel_order |
O(1) | 0 |
| Level insert | O(levels) | 0–1 PriceLevel (pooled) |
| Level remove | O(1) | 0 |
"Allocations" here means pool slot acquisitions, not malloc() — with FlatMap in place of std::unordered_map, malloc() is called exactly 0 times across all of these, which make check-zero-alloc checks on every CI run.
HDR-lite histogram — no sorting, no dynamic allocation.
Bucket mapping:
idx 0 – 1023 → 1 ns resolution (0 – 1 023 ns)
idx 1024 – 4095 → log-compressed (1 µs – ~seconds)
record() → O(1) bucket index calculation + increment
percentile() → O(4096) linear scan (fits entirely in L1 cache)
Deterministic synthetic feed. Same seed → identical message sequence → reproducible benchmarks.
| Type | Mix | Detail |
|---|---|---|
| Limit | 70% | Price = mid ± rand(0,10) ticks; qty = rand(1,500) |
| Cancel | 20% | Picks a random live order; swap-and-pop removal |
| Market | 10% | qty = rand(1,100); sweeps best price levels |
Mid-price random-walks ±1 tick with ~1.2% probability per message, creating realistic spread dynamics.
Fixed-capacity, open-addressing hash map — replaces std::unordered_map for order_map_, bid_levels_, ask_levels_.
insert/find/erase → linear probe from Hash(key) & MASK, tombstone
deletion, until match / empty slot / full scan
- Keys, values, and per-slot state live in three inline
std::arrays — no nodes, no heap. - Capacity must be a power of two; sized to 2× the caller's pooled-object capacity to keep load factor ≤50%.
- Default hash is a 64-bit bit-mixer (splitmix64 finalizer), not identity —
std::hash<uint64_t>in libstdc++ is the identity function, which is fine for small sequential key ranges but clusters badly under adversarial or wide-stride keys. - No rehashing, no growth. That's a deliberate tradeoff, not an oversight — the matching engine already has a compile-time bound on live orders/levels via
MemoryPool, so a fixed-capacity table is the right fit.
orderbook/
├── .github/
│ ├── workflows/
│ └── ci.yml GitHub Actions: build, test, sanitize, zero-alloc + P99 check (Linux + macOS)
├── include/ Header-only core (all hot-path code)
│ ├── types.hpp OrderMessage, Order, Trade, PriceLevel
│ ├── memory_pool.hpp Fixed free-list allocator
│ ├── flat_hash_map.hpp Fixed-capacity open-addressing hash map (no heap)
│ ├── ring_buffer.hpp SPSC lock-free ring buffer
│ ├── order_book.hpp Matching engine + price-level management
│ ├── latency_stats.hpp HDR-lite histogram + now_ns()
│ └── feed_simulator.hpp Synthetic ITCH-style feed generator
│
├── src/
│ └── main.cpp Benchmarks: optimised vs std::map baseline, real producer/consumer threads
│
├── tests/
│ ├── test_main.cpp 17 test cases / 68 assertions (no external framework)
│ └── check_zero_alloc.cpp Regression check: 0 malloc() calls in the matching loop
│
├── scripts/
│ └── check_regression.sh CI gate: zero-alloc check + fail if P99 exceeds threshold
│
├── Makefile all, run, bench, test, sanitize, check-zero-alloc, clean
├── .gitignore
└── README.md
Requirements: macOS (Apple Silicon or Intel) or Linux. No dependencies beyond the system compiler.
macOS M1/M2/M3:
xcode-select --installis all you need — see INSTALL.md for a step-by-step guide.
# Clone
git clone https://github.com/joshuabvarghese/Orderbook-Simulator.git
cd Orderbook-Simulator
# Build (release, zero warnings)
make
# Benchmark — 5 million messages
make run
# Quick benchmark — 1 million messages
make bench
# Custom message count
./orderbook 10000000
# Run unit tests
make test
# Unit tests + AddressSanitizer + UndefinedBehaviorSanitizer
make sanitize
# Verify zero heap allocations in the matching hot path
make check-zero-alloc
# Clean build artifacts
make cleanThis project follows a GitHub Flow branching strategy.
main ──●──────────────────────────────●──────────────────► (always deployable)
\ /
●── feature/spsc-ring ─────● PR → review → merge
\ /
●── fix/pool-drain ────● PR → review → merge
\ /
●── perf/level-prefetch ──●
| Branch pattern | Purpose |
|---|---|
main |
Always builds, all tests pass, tagged releases |
feature/<name> |
New components or capabilities |
fix/<name> |
Bug fixes |
perf/<name> |
Performance improvements |
docs/<name> |
Documentation only |
Follow Conventional Commits:
<type>(<scope>): <short description>
[optional body]
[optional footer]
| Type | When to use |
|---|---|
feat |
New component or capability |
fix |
Bug fix |
perf |
Performance improvement (include before/after) |
refactor |
Code restructure, no behaviour change |
test |
Add or fix tests |
docs |
README, comments, diagrams |
ci |
CI/CD changes |
chore |
Tooling, deps, build system |
Examples:
git commit -m "feat(ring_buffer): add batch push() for multi-message bursts"
git commit -m "perf(order_book): prefetch next price level in match loop
P99 improved from 500ns to 380ns on Xeon E5-2690.
Measured with 5M messages, seed=42."
git commit -m "fix(memory_pool): handle zero-capacity edge case in ctor"
git commit -m "test(order_book): add price-time priority coverage"# 1. Start from an up-to-date main
git checkout main
git pull origin main
# 2. Create a feature branch
git checkout -b perf/prefetch-price-levels
# 3. Make changes, build, test
make sanitize # AddressSanitizer + UBSan
make run # verify benchmark
# 4. Commit in logical chunks
git add include/order_book.hpp
git commit -m "perf(order_book): prefetch next level in match loop"
# 5. Push and open a PR
git push origin perf/prefetch-price-levels
# → open PR on GitHub, fill in the template
# 6. After review and CI passes → squash-merge to maingit checkout main
git tag -a v1.0.0 -m "v1.0.0 — initial public release
- Lock-free SPSC ring buffer
- Free-list memory pool + open-addressing FlatMap (zero heap allocations, CI-verified)
- Intrusive order book with price-time priority
- P99 ~400 ns on shared CI hardware — see README benchmark table for current numbers"
git push origin v1.0.0