While learning about limit order books, I kept coming across two ideas. The first was the textbook answer: a flat array indexed by price is the optimal solution for a dense book because updates are O(1). The second came from low-latency systems and HFT discussions, where people repeatedly stress that contiguous memory and cache locality often matter more than algorithmic complexity.
That got me wondering how these ideas compare in practice, so I implemented four different order book data structures and benchmarked each implementation using both synthetic workloads and a real BTCUSDT replay.
The setup
A limit order book is the core data structure of an exchange: for one symbol, it tracks resting buy and sell orders at each price level, and the hot operation is applying a stream of updates (add, cancel, modify) as fast as possible.
In Rust, this is implemented using a common OrderBook trait. I also wrote a differential test harness that replays the same event stream through every implementation and verifies that they all produce identical results before benchmarking them.
I chose four implementations that represent the trade-offs you'll commonly see discussed in systems programming: pointer-based trees, contiguous vectors, linear scans that exploit locality, and direct indexing with arrays.
- BTreeMap the straightforward implementation. Memory usage grows only with occupied price levels, but updates involve tree traversal and pointer chasing.
-
Sorted Vec of
(price, level). stores price levels in contiguous memory and locates them with binary search. Better cache locality than a tree, but insertions require shifting elements. - Reverse-sorted Vec with a linear scan. keeps the best prices at the front and relies on a simple linear scan. This sounds inefficient, but if most updates happen near the inside market, it can outperform binary search.
- FlatBook (flat array indexed by price tick) indexes directly by price tick, giving constant-time access without searching.
Going into the project, I expected the flat array to come out ahead. It has constant-time lookups, avoids tree traversal entirely, and is the implementation that's usually recommended for dense order books. The benchmarks were mainly meant to measure how much faster it was than the alternatives.
The order book isn't the whole system, though. In a market data engine, updates also need to be distributed to multiple consumers, so each implementation plugs into the same lock-free pipeline shown below.
One pinned producer, two lock-free primitives, K independent consumers. The book is the hot path; the seqlock and ring are how its output fans out.
On synthetic data, the textbook answer wins. On real data, it comes in last by 288x
To avoid drawing conclusions from a single workload, I benchmarked each implementation under two very different conditions. The first was a synthetic workload with a relatively narrow, uniformly distributed price range. The second replayed a real BTCUSDT market session, where updates arrive with the same characteristics as they did on the exchange.
The synthetic benchmark matches the textbook expectation. The real market replay tells a completely different story. Every bar is re-derived from throughput.csv.
The surprising part isn't that FlatBook slows down—it's that the entire ranking reverses once the workload becomes realistic.
The result wasn't just that the ranking changed—it completely flipped. The FlatBook implementation, which was consistently the fastest on the synthetic benchmark, became the slowest on the real replay, while the BTreeMap implementation ended up on top by a wide margin.
If I had only benchmarked the synthetic workload, I would've concluded that the flat array was the obvious choice. Replaying real market data completely changed that conclusion.
At this point, the obvious question was why. The algorithms hadn't changed, only the workload had. The answer turned out to have very little to do with Big-O complexity and everything to do with how much memory the data structure actually touches.
Why the FlatBook slowed down
The biggest difference between the synthetic benchmark and the real replay wasn't the number of updates—it was the range of prices those updates covered.
A FlatBook allocates memory for every possible price tick in that range, whether there's an order there or not. That means its memory footprint grows with the price span, not with the number of price levels that actually contain orders.
The flat array's span on the real book is ~88 MiB, about 2.74x the 32 MiB L3. Every "O(1)" index is now a main-memory round trip.
This was the point where it became clear that memory footprint mattered more than lookup complexity.
Once the array grows beyond what the processor can comfortably keep in cache, the cost of an "O(1)" lookup changes dramatically. The indexing itself is still constant time, but the data you're indexing often has to be fetched from lower levels of the memory hierarchy.
The BTreeMap has the opposite trade-off. Tree traversal involves pointer chasing, but memory usage stays proportional to the number of occupied price levels instead of the total price span. On the real replay, that smaller working set outweighed the extra traversal cost.
In this workload, the deciding factor wasn't algorithmic complexity—it was the working set size. Once the FlatBook grew to roughly 88 MiB, cache locality became the dominant cost.
The same idea explains another result from the benchmarks. I originally expected the binary-search implementation to consistently outperform the linear scan, but that wasn't always true either.
If most updates happen near the best bid and ask, a short linear scan often finishes before a binary search has a chance to pay off. If updates are spread uniformly across the book, the scan eventually becomes too expensive and binary search wins instead.
Under uniform touches the linear scan degrades ~18x by depth 2048; under concentrated touches it never loses. Source: service_sweep.csv.
The choice between linear scan and binary search depends more on access patterns than on theoretical complexity.
At this point the benchmark results made sense, but I still wanted evidence that the processor was actually spending time where I thought it was. That's where the hardware performance counters came in.
One of the reasons low-latency systems often favor contiguous data structures is cache locality—but this benchmark also shows the other half of that advice. Contiguous memory only helps when the working set still fits in cache. Once it doesn't, the advantage can disappear surprisingly quickly.
What the hardware counters showed
The benchmarks told me which implementation was faster, but they couldn't explain why. For that, I needed hardware performance counters (PMUs), which expose where the processor is actually spending its time.
Before I had access to server hardware, I tried to explain each benchmark result just from its behavior. Looking at how throughput changed under different workloads, I formed a hypothesis about what each implementation was bottlenecked on.
Later, I reran the benchmarks on a rented AMD EPYC system and collected the native Zen 4 PMU counters. They matched those hypotheses surprisingly well. Here's a summary of what the counters showed.
The table below isn't meant to compare performance again—it summarizes where each implementation spends its time.
| impl | IPC | bad-spec | backend-mem | verdict |
|---|---|---|---|---|
SortedVec |
2.50 | 0.1% | 50.5% | memory-bound (branchless locate) |
BTreeBook |
1.33 | 28.3% | 9.1% | pointer chase (frontend + memory) |
RevVec |
6.10 | 1.3% | 2.3% | core-bound (scan length) |
FlatBook |
2.43 | 25.5% | 13.4% | mispredict-bound at wide depth |
The interesting part isn't which implementation is "best." It's that each one spends its time differently, even though they're solving exactly the same problem.
-
SortedVecspends most of its time waiting on memory. Its binary search usespartition_point, which is already branchless, so branch prediction barely shows up. -
BTreeBookpays the expected cost of pointer chasing through the tree. -
RevVecis mostly limited by the work done in the scan itself. -
FlatBook, surprisingly, spends much more time recovering from branch mispredictions than waiting on memory. This isn't something I'd be comfortable concluding from the benchmark alone. The PMU data is what made the explanation convincing.
A quick note: these measurements come from AMD Zen 4's native pipeline-utilization counters. They're conceptually similar to Intel's Top-Down methodology, but they're not the same thing, so I've intentionally kept the terminology specific to AMD.
Earlier I mentioned that low-latency engineers often emphasize cache locality and real measurements over theoretical complexity. This is exactly why. The benchmark tells you what happened. The PMU counters are what let you build a credible explanation for why it happened.
The two primitives, and the seqlock that never blocks its writer
The order book wasn't the only component I built. Rather than benchmark the order book in isolation, I embedded it in a small market-data pipeline. That's where the other two components in the architecture diagram come in: a seqlock for publishing the latest top-of-book snapshot and an SPMC ring buffer for broadcasting every update. Both implementations are entirely safe Rust (#![forbid(unsafe_code)]) and were verified with Loom before benchmarking.
A seqlock uses a simple version counter. Even values mean the data is stable, while odd values indicate that a write is in progress. Readers optimistically copy the snapshot and then check whether the version changed while they were reading. If it did, they simply retry. Because readers never acquire a lock, the writer is never blocked.
pub fn load_counted(&self) -> (TopOfBook, u32) {
loop {
let s1 = self.seq.load(Acquire); // (R1) pairs with the writer's Release
if s1 & 1 == 0 { // even => no write in progress; snapshot it
let t = TopOfBook { /* payload: Relaxed loads */ };
fence(Acquire); // (R2) order payload reads before the re-check
let s2 = self.seq.load(Relaxed);
if s1 == s2 { return (t, retries); } // unchanged => no write straddled the read
}
// else: odd, or straddled => discard and retry
}
}
In practice, a load() stays around 10 ns (p50) and remains essentially flat even as the number of readers increases. Across six million timed reads, no torn snapshots were observed.
The ring buffer did expose one limitation. As more consumers are added, producer throughput drops from 12.17 to 8.46 Mev/s. My first suspicion was false sharing, but perf c2c showed something different. The payload slots remain isolated on separate cache lines; the contention comes from the write cursor itself, which every consumer must observe. In other words, this is true sharing, not false sharing. It's an inherent cost of broadcasting to multiple readers rather than a bug in the implementation.
I left that behavior as-is because eliminating it would require changing the design rather than fixing an implementation issue. The producer remains wait-free; only the throughput changes.
These primitives weren't the focus of the benchmark, but they complete the data path and are reusable outside the order book itself.
What I learned
I started this project wanting to compare different order book implementations. What I ended up with was a much better appreciation for how easily synthetic benchmarks can hide real bottlenecks.
The FlatBook wasn't "wrong"—it was simply optimized for a workload that didn't resemble the one I eventually tested. Once the working set grew beyond cache, a data structure with theoretically better complexity became the slowest implementation in the benchmark.
This project is also serving as a stepping stone toward a larger goal: building low-latency infrastructure for microVM-based systems. The same approach—benchmark on realistic workloads, measure with hardware counters, and avoid relying on intuition alone—is the one I'll carry into that work.
The repository contains all benchmark inputs, raw CSVs, plotting scripts, and source code, so every figure in this article can be reproduced.
Repository: https://github.com/umangPokhriyall/low-latency-lob
Top comments (0)