Window edges and representation trade-offs

The window, and what happens at its edge

An array over every price would be 6.8 million ticks × 8 bytes, 54 MB a side, nearly all zeros, so it covers a window that starts at the base and is centred on the mid. At 65,536 levels the window is $655.36 wide, ±$327.68 or about ±0.48%, which a volatile hour can leave; at 4,096 levels, ±$20.48 and 32 KB a side, a quiet minute can.

ArrayBook ignores updates outside the window. For a deep level, a bid at $67,500 far below any price the strategy would trade at, that is fine, if everyone remembers the copy is now of the window only. The best price leaving the window is a real event: the cursor walks off the edge, and a book reading “no bids” is wrong in a way the strategy acts on. So the feed handler checks each price against the window first and moves the window when the best nears its edge.

Moving the window is a re-base, a new base centred on the mid. Copying every level along is a 1 MB memmove for both sides, 50–150 µs (200,000–600,000 cycles, 50–150 budgets) with no update applied. A ring avoids the copy: a price’s slot is the price mod 65,536, its low 16 bits, so when the window moves d ticks the d prices entering reuse the slots of the d that left. A re-base is then a new base and the clearing of those slots and bits, nearly free, for an extra AND per update and a bitmap search that wraps from slot 0 to 65,535. Either way the entering levels were outside, their updates ignored, so they read zero, and a level whose quantity never changes is never resent: the hole stays unless out-of-window levels were kept elsewhere, say in a small ordered map that only those rare updates touch.

A rebuild instead discards the copy, fetches a snapshot (the venue’s full list of levels with an update id), centres a new base on its mid and replays the deltas buffered meanwhile: 70–200 ms with the venue 35 ms away, 70,000–200,000 budgets with the book untrusted, but no holes. The width is chosen per instrument from how many ticks its price travels between re-bases: for BTC 1% is 68,123 ticks, so a 3% day crosses 204,370, about three 65,536-level windows, while a coin at $2.0000 with a $0.0001 tick moves 200 ticks per 1%, so 4,096 levels span ±10%.

Comparing the three

The array wins every column the hot path pays on each update and loses the two paid rarely: memory, 520 KB a side (512 KB of levels, 8 KB of bitmap) against 16 KB however shallow the book, and the window’s edge, which the tree does not have. That is why it comes last: fastest only with the bitmap and the window in place, and correct only if the edge code is.

What it costs

ArrayBook::apply costs 2–5 ns (8–20 cycles, 0.2–0.5% of a budget) when the cursor stays and 5–20 ns (up to 2%) when the bitmap moves it; reading the best costs 1 ns. VecBook costs 20–60 ns (80–240 cycles, 2–6%) to find a level, and 120–360 ns, up to a third of a budget, to add or remove one. TreeBook as written, two 30–100 ns walks included, costs 160–500 ns (640–2,000 cycles, a sixth to a half of a budget) on an existing level and 210–700 ns on a new or emptied one. The tail comes from queueing behind a burst, and from the window: a copying re-base costs 50–150 µs, a ring re-base almost nothing, a rebuild 70–200 ms. Indirectly, the tree’s 20–50 KB of scattered nodes per side, and the allocator’s free lists behind them, compete for an L1 of 32–48 KB with everything else on the core. The array’s hot working set is the line at each cursor plus the bitmap word beside it: about five lines, 320 bytes. The rest of its megabyte waits in L2 and L3 for deep updates, its tail: a deep level whose line has dropped to L3 costs 10–40 ns, not 2–5.

Worked example: a thousand updates in a second of the open

Take BTC-USDT-PERP from 09:30:00.000 to 09:30:01.000 New York time, the US stock market’s open, when even a market that never closes gets busy, with the feed handler on core 3. A thousand updates arrive past decode and the sequence check: 950 deep (say 750 changing an existing level and 200 creating or emptying one), 40 changing the best’s quantity, and 10 emptying the best, with the next level on average 3 empty levels further in. Summing the costs above:

The median is one of the 790 overwrites of an existing level: 0.2–0.5% of a budget on the array, 2–6% on the Vec (12–36% at worst), and 16–50% on the tree (21–70% at worst). A plain walk over three empty levels would add only about 3 ns, so the bitmap buys nothing here; it pays on the day a walk is three thousand. Over the whole second, even the tree spends at most 0.54 ms, 0.05% of the core, so the total is not the problem. The strategy acts on the 50 updates that changed the top, and on the tree each reaches it 160–700 ns after decode, a sixth to most of a budget gone.

Seeing it

Predict the ranking first, then count it over the companion repository’s replay of 10 M updates, one structure at a time on core 3:

perf stat -e cycles,instructions,branch-misses,cache-misses,L1-dcache-load-misses \
    -- taskset -c 3 ./replay array updates-10m.bin

Divide each count by 10 M; cycles over 4 is nanoseconds at 4 GHz. Expect tens of instructions per update for the array and hundreds for the tree, and branch-misses near zero for the array, about five for the Vec and a few for the tree, one per node whose scan stops at an unpredictable key. cache-misses, the loads that reached DRAM, stays near zero for all three while a thousand-level tree fits in L2. The difference shows in L1-dcache-load-misses: well under one per update for the array, and 2–5 for the tree, about one per node. Warm up before counting, because the first write to each 4 KB page of a fresh array takes a page fault, Chapter 2’s.

cargo install cargo-show-asm provides cargo asm; cargo asm --lib lists the library’s functions, and this prints apply:

RUSTFLAGS="-C target-cpu=native" cargo asm --lib "<ch06_book::ArrayBook as ch06_book::Book>::apply"

A deep update runs about sixty instructions from entry to ret, the only calls going to core::panicking::panic_bounds_check on index checks that never fail, and the walk uses tzcnt and lzcnt (bsf and bsr without target-cpu=native). TreeBook’s apply runs to hundreds of instructions, calling memmove for shifts within a node and __rust_alloc and __rust_dealloc for splits and merges. To count allocations, a test installs Chapter 2’s counting global allocator, applies a replay and asserts the counter has not moved: true for ArrayBook and a preallocated VecBook, never for TreeBook.

Read more: WK Selph, “How to Build a Fast Limit Order Book” (2011), first posted on howtohft.wordpress.com and now read through the Internet Archive: a tree of price levels, each a linked list of orders, with a hash map from price to level, the per-order (L3) relative of these structures. David Gross, “When Nanoseconds Matter: Ultrafast Trading Systems in C++” (CppCon 2024 keynote), takes an order book from std::map to a sorted vector, measuring each step: keeping the best at the vector’s end shortened the moves near the top, and a linear scan beat binary search on his data. The Rust standard library’s BTreeMap documentation explains its B-tree and node search; B = 6, 11 keys a node, is in library/alloc/src/collections/btree/node.rs.