This document outlines three different order book implementations and provides an analysis of their performance based on key operations: Adding, Modifying, and Deleting orders. The performance results are derived from benchmarking tests and are summarized in comparison charts (GPT assisted in the making of this readme - and for V3 implementation)
Hardware all tests were conducted on:
- Processor: 11th Gen Intel(R) Core(TM) i5-11400H @ 2.70GHz 2.69 GHz
- RAM: 32 GB
- Environment: WSL2
- Uses two TreeMaps (bids and asks) to group orders by price.
- Each price level contains a LinkedList of orders.
- Orders are grouped by price, making it easier to access orders at a specific price level.
- Deleting or modifying an order requires iterating through the LinkedList at the relevant price level.
- Orders at the same price level are executed in FIFO order.
- Modifying an order causes it to lose priority and be re-added to the end of the LinkedList.
- Adding Orders:
O(log n)(inserting into the TreeMap). - Deleting/Modifying Orders:
O(n)(iterating through the LinkedList). - Finding Orders by Price:
O(log n)(accessing the TreeMap).
- Efficient for accessing orders at a specific price level.
- Maintains FIFO order within each price level.
- Deleting or modifying orders requires iterating through the LinkedList.
- Poor performance at scale, as seen in benchmark results.
- Uses two ArrayLists (bids and asks) to store orders.
- Orders are stored in a flat list, with no grouping by price.
- Orders are added to the end of the list.
- Deleting or modifying an order requires iterating through the list to find it by ID.
- Orders at the same price level are executed in FIFO order.
- Modifying an order causes it to lose priority and be re-added to the end of the list.
- Adding Orders:
O(1)(appending to the list). - Deleting/Modifying Orders:
O(n)(iterating through the list). - Finding Orders by Price:
O(n)(iterating through the list).
- Simple and easy to implement.
- Works well for small order books.
- Inefficient for large order books.
- No grouping by price, making price-level access slow.
- Uses a HashMap (
orderMap) for quick lookup of orders by ID. - Uses two TreeMaps (bids and asks) to group orders by price.
- Each price level contains a List of orders.
- Orders are grouped by price, making it easier to access orders at a specific price level.
- Deleting or modifying an order is optimized using the orderMap for quick lookup.
- Orders at the same price level are executed in FIFO order.
- Modifying an order causes it to lose priority and be re-added to the end of the list.
- Adding Orders:
O(log n)(inserting into the TreeMap). - Deleting/Modifying Orders:
O(1)(using the orderMap). - Finding Orders by Price:
O(log n)(accessing the TreeMap).
- Fast lookup, deletion, and modification using
orderMap. - Efficient grouping of orders by price.
- More complex due to multiple data structures.
- Requires additional memory for
orderMap.
Benchmarking tests were conducted to compare the three implementations for the operations: Add, Modify, and Delete. The results are summarized below:
- V1 (Grouped by Price - TreeMap + LinkedList): Performs the worst, scaling poorly as the number of orders increases.
- V2 (Flat List): Performs the best (
O(1)) since adding to an ArrayList is efficient. - V3 (Optimized Lookup): Slightly worse than V2 but better than V1.
✅ Best for Adding Orders: V2 (Flat List) ❌ Worst for Adding Orders: V1 (Grouped by Price)
- V1 (Grouped by Price): Degrades significantly as orders increase (
O(n)). - V2 (Flat List): Performs better than V1 but still requires
O(n)lookup. - V3 (Optimized Lookup): Performs the best (
O(1)) using a HashMap for lookups.
✅ Best for Modifying Orders: V3 (Optimized Lookup) ❌ Worst for Modifying Orders: V1 (Grouped by Price)
- V1 (Grouped by Price): Performs the worst due to LinkedList iteration.
- V2 (Flat List): Similar to Modify, deletion requires scanning the list (
O(n)). - V3 (Optimized Lookup): Stays almost constant (
O(1)).
✅ Best for Deleting Orders: V3 (Optimized Lookup) ❌ Worst for Deleting Orders: V1 (Grouped by Price)
| Feature | Version 1 (Flat List) | Version 2 (Grouped by Price) | Version 3 (Optimized Lookup) |
|---|---|---|---|
| Data Structure | ArrayList |
TreeMap + LinkedList |
HashMap + TreeMap + List |
| Order Lookup by ID | O(n) |
O(n) |
O(1) |
| Order Lookup by Price | O(n) |
O(log n) |
O(log n) |
| Add Order | O(1) |
O(log n) |
O(log n) |
| Delete Order | O(n) |
O(n) |
O(1) |
| Modify Order | O(n) |
O(n) |
O(1) |
| FIFO Behavior | ✅ | ✅ | ✅ |
| Complexity | Simple | Moderate | More Complex |
✅ Best for: Small order books where performance is not critical. ✅ Why? Simple and easy to implement.
✅ Best for: Medium-sized order books needing efficient access to orders by price. ✅ Why? Maintains FIFO order within each price level.
✅ Best for: Large order books where fast lookup, deletion, and modification of orders are critical. ✅ Why? Best for high-performance trading systems.