Limit Order Book - Performance Optimized

This is a redevelopment and performance optimization of the Limit Order Book project by Benjamin Rienecker. This fork achieves ~3 million TPS (transactions per second), a 2.1× improvement over the original implementation (~1.4M TPS).

The project implements a high-performance matching engine in C++ that supports Market, Limit, Stop, and Stop Limit orders. All functionality is tested through unit tests and integration tests using GoogleTest.

Performance Improvements

This redevelopment includes significant performance optimizations over the original implementation. The following improvements were applied:

Optimization	Description	Impact
AVL height maintenance	Replaced recursive O(N) height calculation with O(1) stored height field, updated during insert/delete/rotate	Major
Duplicate map lookups	Replaced find() + at() pattern with iterator-based access in limitBuyMap, limitSellMap, stopMap	Moderate
Object pooling	Introduced ObjectPool<Order> and ObjectPool<Limit> to eliminate new/delete overhead and improve cache locality	Major
Limit destructor simplification	Moved tree reconnection logic from Limit::~Limit() into deleteLimit/deleteStopLevel, avoiding redundant work	Moderate
limitOrderAsMarketOrder inlining	Inlined marketOrderHelper logic to process multiple price levels without repeated function calls	Moderate
stopOrderAsMarketOrder de-recursion	Directly call marketOrderHelper + executeStopOrders instead of going through marketOrder wrapper	Minor
Branch prediction hints	Added [[likely]]/[[unlikely]] on critical buyOrSell branches	Minor
Hot path I/O removal	Removed std::cout from searchOrderMap, searchLimitMaps, searchStopMap (Cancel/Modify failure paths)	Moderate

Performance Results

Metric	Original	Optimized	Improvement
Latency per order	~713 ns	~333 ns	2.1× faster
Throughput	~1.4M TPS	~3M TPS	2.1× higher

Benchmarks were run with 5 million in-memory orders (no file I/O during measurement) on an 8-core Apple M1 Pro chip.

Build & Run

./build.sh build   # Compile the project
./build.sh run     # Run the executable

Architecture

The order book uses AVL trees of Limit objects (sorted by price), each containing a doubly linked list of Order objects. Key optimizations include:

• O(1) AVL height: Stored height field instead of recursive calculation
• Object pooling: ObjectPool<Order> and ObjectPool<Limit> for memory efficiency
• Separate trees: Buy and sell limits in separate AVL trees
• O(1) operations: Add/Cancel/Modify orders, GetBestBid/Offer

For detailed design and architecture information, see the original repository.

References

• Original Limit Order Book - Benjamin Rienecker
• How to Build a Fast Limit Order Book - wkselph
• Millions of Orders per Second Matching Engine Testing - Alex Zus