Ultra-Low Latency Limit Order Book (LOB) Matching Engine

A high-performance Limit Order Book (LOB) matching engine built from scratch in C++17. The architecture strictly enforces Zero Runtime Memory Allocation to eliminate OS allocator overhead and memory fragmentation, achieving highly deterministic ultra-low latency and a throughput exceeding 30 million transactions per second (TPS).

---

Hardware & Environment Specifications

Benchmarking was executed on the following environment:

• OS: Windows 11 (64-bit)
• CPU: 12th Gen Intel Core i7-12700H (14 Cores / 20 Threads)
• RAM: 16.0 GB
• Compiler: GCC (MinGW-w64)
• Build Flags: -O3 -march=native -std=c++17

---

Key Architecture Features

• Zero Runtime Heap Allocation: The engine executes 0 new or delete calls during the matching process. This completely eliminates OS-level context switching, Stop-The-World pauses, and heap fragmentation.
• Custom Memory Pool (Free List): A highly optimized, pre-allocated memory arena manages order nodes. Memory is claimed and returned in strict O(1) time by manipulating pointers, maximizing CPU cache locality.
• Intrusive Doubly Linked List: Order structures embed their own prev and next pointers. This allows nodes to exist within the memory pool and the price-level queues simultaneously without requiring wrapper nodes, drastically reducing structural overhead.
• Direct-Mapped Flat Arrays: Standard tree maps and hash tables are entirely replaced with contiguous flat arrays for price levels and order lookups. This reduces Time Complexity to hardware-level O(1) by directly computing memory offsets.

---

Systems Design Evolution

The project evolved through three architectural phases to measure the performance impact of memory management:

Phase 1: The STL Baseline

• Architecture: Utilized std::map (Red-Black Tree) for price levels and std::list (Doubly Linked List) for FIFO order queues.
• Bottleneck: High latency variance and limited throughput due to massive dynamic memory allocation overhead (over 1.4 million allocations for 1 million orders).

Phase 2: Custom Memory Pool & Intrusive Queue

• Architecture: Replaced std::list with a custom Free List allocator and intrusive nodes.
• Result: Eliminated allocation overhead on the queueing side, pushing throughput to ~3.98M TPS. However, residual allocations remained due to the std::unordered_map used for order tracking.

Phase 3: Total Zero-Allocation Engine (Current)

• Architecture: Stripped all STL containers. Replaced order_lookup with a Direct-Mapped Array and utilized pointer tracking for best_bid and best_ask to avoid loop scanning.
• Result: Achieved 0 Runtime Heap Allocations, deterministic memory footprint, and a throughput of 30.3M TPS.

---

Performance Benchmarks (1 Million Random Orders)

Architecture	Throughput (Orders/sec)	Heap Allocations (Runtime)	Memory Footprint	Latency Profile
Phase 1: STL Baseline	~2.8M TPS	~1,498,495 times	~79 MB	High Variance
Phase 2: Memory Pool	~3.98M TPS	~877,920 times	~107 MB	Moderate
Phase 3: Flat Array	~30M TPS	5 times	~94 MB	Highly Deterministic

(Note: The 5 allocations recorded in Phase 3 are strictly from pre-allocating std::vector capacities during initialization. Runtime allocations during the benchmarking loop are exactly 0.)

---

Advanced Benchmarking Methodology & Testcase Generation

To ensure the 30.3M TPS metric reflects worst-case and highly contested market conditions rather than optimal edge cases, the test data is generated using an aggressive profiling methodology:

1. Benchmarking Isolation: All 1,000,000 dummy orders are pre-generated and stored in a pre-allocated std::vector prior to starting the high-resolution timer. This strictly isolates the Matching Engine's pure execution time from the overhead of RNG and memory paging.
2. Aggressive Price Clustering: Prices are tightly constrained using std::uniform_int_distribution (Range: 90 to 110). This intentionally creates massive order book density and forces continuous spread crossing. It stresses the engine's core matching logic rather than merely testing best-case O(1) insertions in empty price levels.
3. Partial Fill Sweeping (Stress Test): Order quantities are heavily randomized (Range: 10 to 100). When a large 100-qty order sweeps a price level filled with small 10-qty resting orders, the engine is forced to execute rapid, consecutive node deletions and pointer reassignments. This heavily benchmarks the robustness of the Intrusive Linked List and the Free List's deallocation efficiency.
4. Liquidity Balancing: A strict 50/50 Buy/Sell ratio maintains deep liquidity on both sides of the LOB. This prevents degenerate book states (e.g., an infinitely growing bid side with zero asks) which would artificially inflate TPS by bypassing the matching loop entirely.
5. Deterministic RNG (std::mt19937): Using the Mersenne Twister engine with a fixed seed guarantees 100% reproducible test vectors. This is critical for profiling zero-allocation states, ensuring that memory stability and matching paths are deterministic and not the byproduct of a lucky random sequence.

---

Build & Run

To replicate the exact benchmark environment and maintain strict control variables across all phases, the project is compiled with strict warnings and debug symbols, without compiler-assisted optimizations (-O3). This demonstrates the raw algorithmic efficiency of the architecture.

Direct Compilation (GCC/MinGW-w64):

g++ -Wall -Wextra -g3 -std=c++17 main.cpp OrderBook.cpp -o lob_engine
./lob_engine