Three update outcomes and their measurement

Worked example: one update, three outcomes

At 06:40:00.123456789 UTC on Thursday 15 October 2026 by the venue’s clock, the feed handler for BTC-USDT-PERP, pinned to core 3, receives the 48-byte update: seq 1,873,465,902, side bid, price 6,812,345 ticks ($68,123.45), quantity 512 lots (0.512 BTC). The last update applied was 1,873,465,901, so the check says next and apply runs. The array’s window has base 6,779,577, chosen at startup so that this price sat in the middle of its 65,536 slots, and the update’s slot is 6,812,345 − 6,779,577 = 32,768. What happens next depends only on where the best bid is.

In the first outcome the best bid is 6,812,360, $68,123.60, fifteen ticks higher, so this is a deep level. Slot 32,768 held 300 lots and now holds 512; its bit stays set; the price is below the cursor, which does not move; the best bid is unchanged in price and quantity. apply returns false and nothing is published. On the array: check, index, load and store, and compare, with nothing for the cursor, 5–9 ns, under 1% of a budget. On the tree: 100–300 ns to update the existing level and two walks of 30–100 ns to find the best before and after for the compare, 160–500 ns, up to half a budget to learn that nothing happened.

In the second outcome the best bid is exactly 6,812,345, with 800 lots, and the best ask is one tick above at 6,812,346. The cursor points at slot 32,768. The store replaces 800 with 512; the level is still occupied, so the cursor stays, the third case, but the compare sees the top bid go from (6,812,345, 800) to (6,812,345, 512). The top changed, in quantity only; apply returns true, and at the end of the batch the handler writes one Top: bid 6,812,345 for 512 lots, ask unchanged. The array spent the same 5–9 ns plus the publish; the tree the same 160–500 ns.

Now let the same batch carry one more update, seq 1,873,465,903: bid, 6,812,345, quantity 0. The buyers at $68,123.45 have gone, cancelled or filled. The store writes 0 into slot 32,768 and clears its bit, and the cursor, which pointed there, walks inward. Slots 32,767 and 32,766 are empty too; slot 32,765, at 6,812,342, holds 1,450 lots. The walk passes three empty levels, the one just cleared and the two below it, and stops at 6,812,342. The best bid is now $68,123.42, the spread has widened from one tick to four, and apply returns true. With the bitmap the walk reads two words, because slot 32,768 is the lowest bit of its 64-bit word: the mask leaves that word empty, and one leading_zeros on the word below finds 32,765. The update costs 10–30 ns, under 3% of a budget; without the bitmap, three slot reads in L1 take about 3 ns, cheaper here, since the bitmap is for long walks. The tree spends 150–500 ns removing the level, which can merge a node and free it, and 30–100 ns on each of its two walks to the last leaf, before and after: 210–700 ns, the one case here past half a budget.

Because the second and third updates arrived in one recv, the strategy never hears about 512 lots at $68,123.45: the handler published once, and its Top says the best bid is 6,812,342 for 1,450 lots. Publishing per update would have announced a level already gone. Across the three outcomes the array spent 5–30 ns on each, about a hundredth of a budget, and the tree 160–700 ns, from a sixth of a budget to most of one.

Seeing it

Measure apply in a replay harness, the program that feeds recorded updates through the same Book with no network. Around each call read the time-stamp counter with rdtsc, an lfence before each read so the core cannot start it early, and record the difference into a histogram from the hdrhistogram crate, a Rust library that keeps every value to three significant digits in fixed memory, so the p99 and max can be trusted. Count the top-changed flags too:

use core::arch::x86_64::{_mm_lfence, _rdtsc};
use hdrhistogram::Histogram;

let mut hist = Histogram::<u64>::new_with_bounds(1, 1_000_000, 3).unwrap();
let mut top_changes: u64 = 0;
for u in &updates {
    let t0 = unsafe { _mm_lfence(); _rdtsc() };
    let changed = book.apply(u);
    let t1 = unsafe { _mm_lfence(); _rdtsc() };
    hist.saturating_record(t1 - t0);
    top_changes += changed as u64;
}
println!("p50 {} p99 {} max {} cycles; top changed {} per 1,000",
         hist.value_at_quantile(0.50), hist.value_at_quantile(0.99), hist.max(),
         top_changes * 1_000 / updates.len() as u64);

The two reads cost about as much as the array’s whole apply, so time an empty loop too and subtract its p50. On the array expect a p50 at the first rung, 8–20 cycles, and a p99 among the cursor moves, 20–80; on the tree, its two walks included, a p50 of 640–2,000 and a p99 among new and emptied levels, up to 2,800. The max is whatever else the machine did then, an interrupt or the first touch of a fresh page; a separate histogram per outcome keeps the rare walks from hiding in the common case’s p99. For cache and branches, run the replay under perf stat and divide by the number of updates:

perf stat -e cache-misses,branch-misses -- taskset -c 3 ./replay array updates-10m.bin

On the array both counts per update should be close to zero; on the tree both are higher, and the gap widens whenever something else shares the cache. The last number the harness prints matters most: top changes per thousand updates is the fraction of the feed the strategy ever hears about, typically a few per cent. Well over nine updates in ten end at the compare, which is why the cheap path through apply sets the p50 and why publishing once, after the batch, is enough.