Hey everyone,
A while back I shared my C++ Order Matching Engine here and got some "honest" feedback about my use of
std::list and global mutexes.I took that feedback to heart and spent the last week refactoring the core. Here are the results and the specific optimizations that worked:
The Results:
Baseline: \~129,000 orders/sec (MacBook Air)
Optimized: \~733,000 orders/sec
Speedup: 5.6x
The Optimizations:
1. Data Structure: `std::list` -> `std::deque` + Tombstones
Problem: My original implementation used
std::list to strictly preserve iterator validity. This killed cache locality.Fix: Switched to `std::deque`. It offers decent cache locality (chunked allocations) and pointer stability.
Trick: Instead of
erase() (which is O(N) for vector/deque), I implemented "Tombstone" deletion. Orders are marked active = false. The matching engine lazily cleans up dead orders from the front using pop_front() (O(1)).2. Concurrency: Global Mutex -> Sharding
Problem: A single `std::mutex` protected the entire Exchange.
Fix: Implemented fine-grained locking. The Exchange now only holds a Shared (Read) lock to find the correct OrderBook. The OrderBook itself has a unique mutex. This allows massively parallel trading across different symbols.
3. The Hidden Bottleneck (Global Index)
I realized my cancelOrder(id) API required a global lookup map (`OrderId` \-> `Symbol`) to find which book an order belonged to. This map required a global lock, re-serializing my fancy sharded engine.
Fix: Changed API to cancelOrder(symbol, id). Removing that global index unlocked the final 40% performance boost.
The code is much cleaner now
I'd love to hear what you think of the new architecture. What would you optimize next? Custom Allocators? Lock-free ring buffers?
PS - I tried posting in the showcase section, but I got error "unable to create document" (maybe because I posted once recently, sorry a little new to reddit also)
Github Link - https://github.com/PIYUSH-KUMAR1809/order-matching-engine
https://redd.it/1pk5iv3
@r_cpp
