Irene Liu (irenel), Lillian Yu (lyu2)
15-418 – Spring 2026
orders_ map)Deadline: April 28
Status: In progress
Test Configuration:
perf stat -e cycles,instructions,cache-misses,L1-dcache-load-misses \
./build/sim --engine {fine|coarse} --num-orders 1000000 --num-tickers 8 \
--parallel --threads 8 --workload crossing
Processed in 60650 us (~16,493,322 msgs/sec)
Trades produced: 549,535
Performance counter stats:
1,495,248,677 cycles
2,592,902,524 instructions # 1.73 insn per cycle
12,962,693 cache-misses
14,919,583 L1-dcache-load-misses
0.201856 seconds time elapsed (wall time)
0.336337 seconds user time
0.048615 seconds sys time
Processed in 58677 us (~17,047,906 msgs/sec)
Trades produced: 549,535
Performance counter stats:
1,403,503,792 cycles
2,433,121,866 instructions # 1.73 insn per cycle
13,057,629 cache-misses
14,895,499 L1-dcache-load-misses
0.157232 seconds time elapsed (wall time)
0.266671 seconds user time
0.054727 seconds sys time
| Metric | Fine | Coarse | Difference |
|---|---|---|---|
| Wall Time (us) | 60,650 | 58,677 | +3.4% slower |
| Cycles | 1,495M | 1,403M | +6.6% more cycles |
| Instructions | 2,592M | 2,433M | +6.5% more instructions |
| IPC (Insn/Cycle) | 1.73 | 1.73 | Same |
| L1 dcache misses | 14.9M | 14.9M | Identical |
| Cache miss rate | ~0.87% | ~0.87% | Identical |
Key Finding: L1 cache behavior is identical between fine and coarse, suggesting the 3.4% slowdown is not from cache misses but from lock overhead itself (hand-over-hand re-acquisitions).
Run profiling ./scripts/profile_engines_comprehensive.sh –quick
Analyze results ./scripts/analyze_profile.sh results/profile_comprehensive.csv
View formatted report cat results/profile_comprehensive_report.txt
Ran full profiling sweep across all workloads (balanced/crossing/resting) and order counts (100k/500k/5M) at 8 tickers × 1/2/4/8 threads using profile_engines_comprehensive.sh.
Balanced Workload (60% limit, 20% market, 20% cancel):
Config (orders/tickers) | 1-thread | 2-thread | 4-thread | 8-thread
------------------------+----------+----------+----------+----------
100k/8 | 0.92 | 0.90 | 0.91 | 0.94
500k/8 | 0.94 | 0.92 | 0.94 | 0.94
5M/8 | 0.97 | 0.95 | 0.97 | 0.98
Pattern: Consistent 2-8% slowdown across all thread counts. Fine-grained overhead dominates.
Crossing Workload (30% limit, 60% market, 10% cancel):
Config (orders/tickers) | 1-thread | 2-thread | 4-thread | 8-thread
------------------------+----------+----------+----------+----------
100k/8 | 0.96 | 0.67 | 1.11 | 0.86
500k/8 | 0.90 | 0.92 | 0.91 | 0.94
5M/8 | 0.90 | 0.91 | 0.93 | 0.95
Pattern: More variance at small order counts (100k is noisier). Avg 5-10% slowdown. One case (4-thread/100k) shows 1.11x, but within measurement noise.
Resting Workload (70% limit, 10% market, 20% cancel):
Config (orders/tickers) | 1-thread | 2-thread | 4-thread | 8-thread
------------------------+----------+----------+----------+----------
100k/8 | 0.96 | 0.84 | 0.94 | 0.97
500k/8 | 0.96 | 0.95 | 0.95 | 0.94
5M/8 | 0.98 | 0.94 | 0.96 | 0.95
Pattern: Consistent 3-6% slowdown. Even with minimal market orders (10%), fine-grained overhead dominates.
Cache miss rates are nearly identical between fine and coarse across all workloads:
Balanced:
Crossing:
Resting:
Conclusion: <1% difference in cache miss rates. This definitively proves the slowdown is not from cache behavior but from lock overhead.
1) The global orders_ map is accessed without ordersMutex_ protection while another thread may call hasOrder() or modifyOrder(), causing undefined behavior. Thus, we fix by acquire ordersMutex_ before erase.
2) [TODO] modifyOrder Not Fully Fine-Grained: currently entire cancel-then-add sequence holds a single lock. We could try to split into phases: first, cancel under side + level lock (if crossing-free), then, add under separate locks
#1: False-Sharing Padding (PriceLevel). The hypothesis is that multiple PriceLevel objects on the same cache line (64 bytes) cause false sharing when threads access different levels. The goal is to reduce cache-line conflicts between level locks.
Implementation:
struct alignas(64) PriceLevel {
static constexpr std::size_t kCacheLineBytes = 64;
Price price;
std::list<OrderPointer> orders;
std::unordered_map<Id, std::list<OrderPointer>::iterator> orderIters;
alignas(64) mutable std::mutex levelMutex;
std::array<std::byte, kCacheLineBytes> padding{};
};
Processed in 62129 us (~16,100,693 msgs/sec)
Trades produced: 549,535
Performance counter stats:
1,529,924,590 cycles
2,635,684,262 instructions # 1.73 insn per cycle
12,907,056 cache-misses
15,386,382 L1-dcache-load-misses
0.159977 seconds time elapsed (wall time)
0.293796 seconds user time
0.054406 seconds sys time
| Metric | Original Fine | Padded Fine | Effect |
|---|---|---|---|
| Wall Time (us) | 60,650 | 62,129 | +2.4% slower |
| Cycles | 1,495M | 1,529M | +2.3% |
| Instructions | 2,592M | 2,635M | +1.7% |
| IPC | 1.73 | 1.73 | no change |
| Cache misses | 12.96M | 12.91M | -0.4% (slight improvement) |
| L1 dcache load misses | 14.92M | 15.39M | +3.1% |
Interpretation: Padding PriceLevel did not improve end-to-end throughput on this workload; it regressed wall time by ~2.4%. The tiny reduction in aggregate cache misses was not enough to offset extra memory footprint / locality costs from larger aligned-and-padded level objects. On our current workload, lock protocol overhead and crossing-path serialization still dominate more than false-sharing effects. As a result, we did not end up including this optimization in our final code.
#2: [TODO] Lock-Free Best-Price Pointer: acquiring side lock just to find best level is wasteful on hot path. We will want to use atomic compare-and-swap (CAS) on best-price pointer to aim to remove side lock from level discovery, reduce acquisitions from 3N to N.
std::atomic<Price> bestAskPrice_{std::numeric_limits<Price>::max()};
Requires C++20 however we coded our whole thing in C++17, so did not end up pursuing this route. —
ordersMutex_ in matching paths before orders_.erase()make verify to confirm correctnessperf stat across all workloads (crossing/balanced/resting)strace -e futexPriceLevel