Spartan: A Deterministic C++20 Limit Order Book

Low-Latency Order Book implementation using Structure-of-Arrays (SoA) data layout, cache-line alignment, and lock-free design patterns for market data processing in high-frequency trading (HFT) environments.

Abstract: The Performance Challenge

This project implements a high-performance Price-Time Priority Limit Order Book (LOB), treating the system as a scientific investigation into low-latency architecture for electronic trading systems.

The initial architecture (using sequential vector insertion) yielded a crippling 1,780 ns per order. The primary engineering goal was to break the fundamental O(N) complexity bottleneck in insertion.

By refactoring to a Two-Level Index (a map of deques referencing contiguous Structure-of-Arrays (SoA) data), we isolated the high-latency operations and achieved sub-microsecond median latency with deterministic tail behavior.

---

Performance Results

Benchmark Environment

Parameter	Value
CPU	Apple M-series (12 cores @ 2.6 GHz)
L1 Cache	32 KiB (Data)
L2 Cache	256 KiB
L3 Cache	9 MB
Compiler	Apple Clang 17.0.0
Build	Release (-O3)

Throughput Benchmarks (Google Benchmark)

Scenario	Throughput	Latency (Aggregate)	Notes
Single Price Level	86.5M ops/sec	~11.6 ns/op	Best case - O(1) deque insertion
50 Price Levels	25.6M ops/sec	~39 ns/op	Typical trading spread
10 Price Levels	312K ops/sec	~3.2 μs/op	With per-op latency logging
Wide Range (10K levels)	594K ops/sec	~1.7 μs/op	Worst case - many price levels

Latency Distribution (1M Operations, 10 Price Levels)

The histogram below shows the latency distribution for 1 million order insertions with per-operation timing:

Metric	Value	Description
Sample Count	1,000,000	Total operations measured
Minimum	2,748 ns	Best-case latency
Maximum	4,394,932 ns	Worst-case (includes outliers)
Mean	3,451 ns	Average latency
Std Dev	7,055 ns	Standard deviation
Median (P50)	3,383 ns	50th percentile
P90	3,782 ns	90th percentile
P95	3,917 ns	95th percentile
P99	5,809 ns	99th percentile
P99.9	30,303 ns	99.9th percentile

Note: Per-operation latency measurements include std::chrono::high_resolution_clock overhead (~50-100ns). The aggregate throughput benchmarks (86M+ ops/sec for single level) more accurately reflect the true algorithmic performance.

Coordinated Omission Awareness: Latency measurements use continuous timestamping without back-off, ensuring tail latencies (P99, P99.9) accurately reflect worst-case behavior under sustained load. This methodology avoids the common benchmarking pitfall where slow operations cause measurement gaps that hide true latency spikes.

---

I. Architectural Design Decisions

1. Structure-of-Arrays (SoA) for Cache Locality

Instead of an Array of Structures (AoS) which scatters attributes in memory, the core order data (IDs, Prices, Quantities, Timestamps) are stored in separate, contiguous std::vectors.

// SoA Layout - Cache-friendly
struct OrderBook {
    std::vector<OrderId>   ids;        // Contiguous IDs
    std::vector<Price>     prices;     // Contiguous prices
    std::vector<Quantity>  quantities; // Contiguous quantities
    std::vector<Timestamp> timestamps; // Contiguous timestamps
};

Rationale: This layout guarantees sequential data access (e.g., iterating all prices during a sweep) hits the CPU's L1/L2 cache successfully, enabling SIMD instruction pipelining and maximizing CPU utilization.

Implementation: All core structs are marked with alignas(64) to ensure cache-line alignment and prevent false sharing between threads.

2. The Two-Level Price-Time Index

To eliminate the latency spike from arbitrary insertion into a sorted std::vector (which costs O(N)), we introduced a two-level indexing system:

Level	Data Structure	Purpose	Complexity
Level 1 (Price)	std::map<Price, OrderLevel>	O(log P) lookup/insertion of price levels. Best Bid/Ask always at map.begin().	O(log P)
Level 2 (Time)	std::deque<std::size_t>	Stores indices at each price. O(1) FIFO operations for time priority.	O(1)

This hybrid structure ensures insertion time is limited by price levels (P), not total orders (N).

---

II. Key Optimizations

Optimization	Implementation	Why It Matters
SoA over AoS	Separate contiguous vectors for each field	Maximizes cache hits when scanning single attributes (e.g., all prices). AoS interleaves unneeded fields, wasting cache lines.
Cache-Line Alignment	alignas(64) on all hot data structures	Prevents false sharing in multi-threaded scenarios; ensures CPU prefetcher loads complete cache lines.
Two-Level Index	std::map<Price, std::deque<size_t>>	Decouples price discovery O(log P) from time-priority queue O(1). Avoids O(N) vector shifting.
Pre-allocation	reserve(1'000'000) on all vectors	Eliminates heap allocations from hot path; zero malloc() calls during order insertion.
Index-Based References	Store size_t indices, not pointers	Indices remain valid through vector reallocation; enables memory-mapped persistence.
Stable Deque	std::deque for time-priority queues	O(1) push_back/pop_front without iterator invalidation; maintains FIFO order.

Why SoA Beats AoS for Order Books

AoS (Array of Structures) - Cache Unfriendly:
┌─────┬───────┬─────┬───────┬─────┬───────┬─────┬───────┐
│ ID₁ │Price₁ │Qty₁ │ Time₁ │ ID₂ │Price₂ │Qty₂ │ Time₂ │ ...
└─────┴───────┴─────┴───────┴─────┴───────┴─────┴───────┘
↑ Loading prices loads unwanted IDs, quantities, timestamps

SoA (Structure of Arrays) - Cache Optimal:
IDs:    │ ID₁ │ ID₂ │ ID₃ │ ID₄ │ ...           ← One cache line
Prices: │ P₁  │ P₂  │ P₃  │ P₄  │ ...           ← Sequential access
Qtys:   │ Q₁  │ Q₂  │ Q₃  │ Q₄  │ ...           ← SIMD-friendly
Times:  │ T₁  │ T₂  │ T₃  │ T₄  │ ...

When executing a price sweep (matching against best bid/ask), only the price and quantity vectors are accessed—the SoA layout ensures these fit in cache without polluting it with unneeded timestamp data.

---

III. Build and Run

Prerequisites

• C++20 compliant compiler (GCC 10+, Clang 12+, MSVC 2019+)
• CMake 3.16+
• Python 3.8+ with matplotlib, numpy (for plotting)

Build Instructions

# Clone and build
git clone https://github.com/mickelsamuel/cpp20-soa-orderbook.git
cd cpp20-soa-orderbook
mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j$(nproc)

# Run tests
./unit_tests

# Run benchmarks
./run_benchmarks

Generate Latency Histogram

# From project root (after running benchmarks)
python3 plot_latency.py

---

IV. Implementation Details

C++20 Features Used

Feature	Usage
[[nodiscard]]	Enforce return value handling
alignas(64)	Cache-line alignment
std::optional	Safe order lookups
Designated initializers	Clean order construction
Concepts (future)	Type constraints

Zero-Allocation Hot Path

The BuySideOrderBook uses reserve() to pre-allocate memory, avoiding all new or malloc calls in the hot insertion path:

book.reserve(1'000'000);  // Pre-allocate for 1M orders
// All subsequent insertions are O(1) amortized

Trade Execution

Implemented O(1) Execute() logic for partial and full fills:

auto result = book.Execute(price, quantity);
// Returns: matched quantity, remaining quantity, trade details

---

V. Test Results

Running OrderBook unit tests...

test_buy_side_price_priority: PASSED
test_buy_side_time_priority: PASSED
test_buy_side_price_time_priority: PASSED
test_sell_side_price_priority: PASSED
test_sell_side_time_priority: PASSED
test_reserve_and_capacity: PASSED
test_clear: PASSED
test_num_price_levels: PASSED
test_soa_contiguity: PASSED

All tests PASSED!

---

VI. Files

File	Description
include/spartan/OrderBook.hpp	Main order book implementation
src/OrderBook.cpp	Implementation details
tests/test_main.cpp	Unit tests
benchmarks/benchmark_main.cpp	Performance benchmarks
latency_log.txt	Raw latency data (1M samples)
docs/latency_histogram.png	Latency distribution visualization
docs/architecture_diagram.png	Two-level index architecture
docs/benchmark_comparison.png	Performance comparison chart

---

VII. References

• LMAX Disruptor - Lock-free ring buffer architecture
• CppCon: Trading at Light Speed - HFT optimization techniques
• Structure of Arrays - Data layout optimization

---

Technical Skills Demonstrated

Category	Skills
Languages	C++20, Modern C++ (move semantics, RAII, templates)
Low-Latency Techniques	Cache-line alignment (alignas(64)), SoA data layout, zero-allocation hot paths, branch prediction optimization
Data Structures	Price-time priority queues, two-level indexing, lock-free patterns
Performance Engineering	Google Benchmark integration, P50/P99/P99.9 tail latency analysis, Coordinated Omission awareness
Trading Domain	Order book mechanics, price-time priority matching, limit order lifecycle
Build Systems	CMake, cross-platform compilation (GCC, Clang, MSVC)
Testing	Unit testing, property-based validation, memory contiguity verification

---

License

MIT License - See LICENSE for details.