lob-engine

A single-threaded limit order book in modern C++20. Implements the core matching engine used by every electronic exchange: price-time priority, self-matching limits, market orders that walk levels, and O(1) cancel via intrusive iterators.

Includes an apples-to-apples Python reference (using sortedcontainers) so the cost of writing this in Python is visible — about 11× slower on the same i9-13900K.

Build & run

# Build everything (demo + tests + benchmark) with -O3 -march=native
make            # or: mingw32-make on MSYS2

make test       # run the 11 invariant tests
make bench      # run the C++ throughput benchmark
make bench-py   # run the Python reference (needs `pip install sortedcontainers`)

Single-file compile if you don't want to use make:

g++ -std=c++20 -O3 -march=native src/lob.cpp src/demo.cpp -o demo

Demo output

[3] Limit buy 30 @ 101 (marketable, fills against ask side)
  [limit 100] 1 fill(s):
      30 @ 101  (taker=100  vs maker=5)

[4] Limit buy 40 @ 103 (walks 101, 102, then partially 103)
  [limit 101] 3 fill(s):
      10 @ 101  (taker=101  vs maker=5)
      25 @ 102  (taker=101  vs maker=6)
       5 @ 103  (taker=101  vs maker=7)

Architecture

Containers

Side	Container	Best at
Bids	std::map<Price, Level, std::greater<Price>>	begin()
Asks	std::map<Price, Level>	begin()

Each Level holds the running total_qty plus a std::list<Order> (FIFO time priority — front = oldest = highest priority). std::list was picked over std::deque because list iterators are stable across other list modifications, which lets us store iterators in the cancel index.

O(1) cancel

std::unordered_map<OrderId, OrderLoc> id_to_loc_;

struct OrderLoc { Side side; Price price; std::list<Order>::iterator it; };

When a cancel request arrives:

1. O(1) hash lookup → (side, price, iterator)
2. O(1) decrement of level total_qty
3. O(1) std::list::erase(it) (only possible because list iterators are stable)
4. O(log k) map erase only if the level became empty

In practice cancel is amortized O(1).

Why integer ticks

Real exchanges quote in integer ticks (e.g. cents, fractional pennies). Using int64_t for prices removes any floating-point rounding pathology in matching — two orders at "the same price" really are equal under ==. Mid / spread are returned in double only at the query interface.

Complexity summary

Operation	Worst case	Comment
add_limit (non-crossing)	O(log k)	map lookup/insert; k = price levels
add_limit (crossing m levels)	O(log k + m)	walks and erases
cancel	O(1) amortized	+ O(log k) if level empties
market_order (m levels)	O(m)
best_bid / best_ask	O(1)	map::begin() is constant time

Tests

11 invariant tests, all assert-based, run by make test:

• empty book has no BBO
• single resting limit sets BBO
• two levels each side: spread + mid correct
• cancel removes order and updates BBO
• FIFO time priority within a level (resting orders fill in order of arrival)
• market order walks multiple levels
• crossing limit auto-matches against opposite side
• crossing limit leaves residue on the book
• non-marketable limit just rests
• insufficient liquidity → partial fill, no resting on aggressor side
• volume invariant holds across 1000 ops with mixed adds + cancels

Benchmark

Workload: 1,000,000 events, deterministic seed, mix of 75% limit-adds and 25% cancels. Prices uniformly in [9000, 11000] (2k ticks), quantities in [1, 100], both sides random.

Results (Intel i9-13900K, single thread, Windows 11)

Implementation	Time	Throughput	Avg latency
C++ (-O3 -march=native -std=c++20)	0.16 s	6.34M ops/s	158 ns/op
Python (sortedcontainers.SortedDict)	1.80 s	0.56M ops/s	1795 ns/op

C++ is ~11× faster running an identical workload. Notes:

• The Python version is not a strawman — sortedcontainers is a well-tuned C-backed structure. This is roughly what you'd get if you wrote a carefully-engineered Python LOB.
• C++ wins because every hot operation (map lookup, list insert/erase, unordered_map probe) compiles to a few pointer dereferences and branches. Python pays interpreter overhead per attribute lookup, per integer compare, per dict probe.
• Real production LOBs (Jane Street, HRT, Citadel) routinely hit tens of millions of ops/s by adding: SoA layouts, custom allocators, ID-recycling pools, and lock-free queues for the network thread. This repo is the honest single-threaded baseline.

Reproduce

make bench
make bench-py

Layout

lob-engine/
├── src/
│   ├── lob.hpp          # public interface (Book, Order, Side, Fill)
│   ├── lob.cpp          # matching engine + book management
│   └── demo.cpp         # CLI demo
├── tests/
│   └── test_lob.cpp     # 11 invariant tests
├── bench/
│   ├── bench.cpp        # C++ throughput benchmark
│   └── bench.py         # Python sortedcontainers reference
├── Makefile
├── LICENSE              # MIT
└── README.md

What's intentionally not here (yet)

This is a clean baseline. Real production extensions you'd layer on top:

• Iceberg / hidden orders
• Self-trade prevention (STP) modes
• Pegged orders, stop orders, IOC / FOK time-in-force
• Multi-symbol routing
• Fix gateway / market data fanout
• SoA + custom pool allocator for the order objects (reduces cache miss rate)
• Lock-free SPSC queue for cross-thread submission
• Replay / journaling for crash recovery
• Trade through protection (Reg NMS in US equities)

Roadmap entries past v0.1.0 will pick a couple of these.