Why rsx-book is built this way

An order book is the live list of every resting buy and sell order for one market; matching pairs an incoming order against the best ones already sitting there. A busy market can hold millions of resting orders at once, so the match has to stay fast no matter how full the book gets — that is the whole job of this crate.

One goal: matching an order costs the same whether the book holds a hundred orders or ten million. A textbook book slows as it fills; this one stays flat. Here is the shape that buys that.

In one breath (if you already know orderbooks)

Not a BTreeMap. A flat, pre-quantised price grid — ~120 000 tick slots — so every hot operation is array arithmetic, not a tree walk:

• price → level: a sawtooth fold of the raw range onto the grid — O(1), no search, no pointers to chase.
• next-best level: a 3-tier occupancy bitmap + count-trailing-zeros — O(1), not O(price-range); a match that clears a level stays ~145 ns, flat (the isolated next-best find is ~25 ns).
• orders: a slab arena — ~1–5 ns alloc/free, zero heap on the hot path.
• layout: #[repr(C, align(64))] with a hot/cold field split — a resting-order match touches one cache line.

Net: every operation is O(1) and cache-resident, so match latency is flat from 100 to 10 M resting orders (measured below). i64 fixed-point throughout — no floats, exact prices.

The sections below are the why behind each choice — the cost each one removes that a naive orderbook pays on every order.

The price map — arithmetic instead of a search

Problem. An order arrives at some price. Where does it go? The obvious answer is a tree keyed by price (BTreeMap<price, level>), but a tree walk is O(log n): the more prices are live, the more hops to find the right one, on the hottest path in the system.

Fix. Prices don't need a tree — they live on a fixed grid (the tick size). So we pre-quantise the whole tradeable range into a fixed array of ~120 000 slots and fold the huge raw price range into it with plain arithmetic (a "sawtooth" of ± bands around the mid price, dense where it matters). Price → slot is now a couple of subtractions and a compare — O(1), no search, no pointers to chase.

Cost it removes. Every insert, cancel, and match starts by locating a price. Making that arithmetic instead of a tree walk takes the depth term out of the most frequent operation there is.

The occupancy bitmap — finding the next level without looking

Problem. After a trade clears the best price level, matching needs the next resting level. With slots in a flat array, the naive way is to scan forward until you hit a non-empty one. When the nearby book is thin, that scan walks thousands of empty slots — O(price-range) — and it lands right on the level-clearing hot path, where the cost is most visible.

Fix. Keep one bit per slot: 1 = something resting here, 0 = empty. Pack them 64 to a word, then put a second layer of bits summarising which words are non-zero, and a third summarising the second. To find the next filled level you read a word, and the CPU's count-trailing-zeros instruction hands you the answer in one step; if the word is empty you climb one level and repeat. Three levels cover all 120 000 slots, so next-best-level is ~3 word reads regardless of how far the next order sits — O(depth=3), not O(price-range).

Why not a tree here either? A BTreeMap would also answer "next key," but it re-earns the search every time and scatters nodes across the heap. The domain is already a dense pre-quantised grid — the slot index is the key — so a bitmap over that grid is both smaller and faster than a tree laid on top of it. (A single "pointer to the next filled slot" can't help: inserts arrive in any order and matching seeks in both directions, so you'd still need the search the bitmap gives you for free.) The find itself is ~25 ns; a full match that has to clear the touch level and find the next stays ~145 ns, flat — no matter how far the next order sits.

The slab — allocation that isn't allocation

Problem. Orders and levels are created and destroyed constantly. Calling malloc/free for each one costs 20–80 ns and can grab a global lock under load — unacceptable when the whole match budget is a few hundred nanoseconds, and a hard "no" for the zero-heap-on-hot-path rule.

Fix. Grab one big block at startup and hand out fixed-size slots from it. Allocating is bumping a counter or popping a free-list head (~1–5 ns); freeing is pushing it back (O(1)). Slots get reused, so there's no fragmentation and no trip to the system allocator ever happens mid-trade. As a bonus the slots sit contiguously, so the CPU's prefetcher works with us instead of chasing scattered heap pointers.

Cache layout — not straddling the line

Problem. x86 memory moves in 64-byte cache lines. A struct that isn't line-aligned can sit across two lines, so reading one field drags in two lines — half the effective L1 bandwidth — and neighbouring order slots can share a line and fight over it (false sharing).

Fix. Every hot struct is #[repr(C, align(64))]: fixed C field order (so we can count bytes and it survives compiler upgrades) and a guaranteed 64-byte start. In a slab of 128-byte slots each order is exactly two lines, perfectly aligned, never straddling, never sharing a line with its neighbour.

Hot/cold split. Within a slot, the fields touched on every match — price, quantity, side, the linked-list pointers — go in the first cache line. The fields only touched on insert or cancel — order id, user id, original quantity, timestamps — go in the second. Matching a resting order then pulls exactly one line, not two, and never pays to load audit data it won't read.

The through-line

Every choice above replaces a variable cost with a fixed one: a tree walk becomes arithmetic, a linear scan becomes three word reads, a malloc becomes a pointer bump, a two-line read becomes one. That's the whole reason the numbers stay flat as the book grows — and the benchmark (reports/ + the live demo) is just that, measured. Everything is i64 fixed-point throughout: no floats, no rounding, exact prices.

rsx-book Architecture

The data structures behind a depth-invariant matching book, and how they compose. This is "how it is"; the "why" lives in notes/ and the formal spec specs/2/21-orderbook.md.

Module layout (rsx-book/src/)

File	Purpose
book.rs	Orderbook struct; insert_resting, unlink_order, cancel_order, modify_*, best-bid/ask scan, occupancy maintenance, price_asc build.
matching.rs	process_new_order, match_at_level, can_fill_fully — GTC / IOC / FOK / post-only / reduce-only, event emission.
slab.rs	Generic Slab<T> arena: bump + free-list, O(1) alloc/free.
compression.rs	CompressionMap — 5-zone sawtooth price→index bisection.
occupancy.rs	Occupancy — hierarchical set-bit bitmap; set/clear/find_next/find_prev in O(depth).
level.rs	PriceLevel — 24-byte level head (head/tail slab handle, total_qty, order_count).
order.rs	OrderSlot — 128-byte #[repr(C, align(64))] order, hot fields in cache line 0.
event.rs	Event enum + reason constants; MAX_EVENTS = 65_536.
user.rs	UserState — per-user net position + active order count, tracked inside the book.
migration.rs	Lazy incremental recentering when mid drifts.
snapshot.rs	Binary save/load (magic RXSN + version).

How the pieces compose

                        Orderbook
   ┌──────────────┬──────────────┬───────────────────────────┐
   │ active_levels│  orders       │  bid_occ / ask_occ         │
   │ Vec<PriceLevel> Slab<OrderSlot>  Occupancy (per side)     │
   │  (dense,     │  (arena,      │  (bitmap over the same     │
   │  compressed) │  128B slots)  │   compression slots)       │
   └──────┬───────┴──────┬────────┴────────────┬──────────────┘
          │ index by     │ head/tail handle    │ bit set =
          │ compression  │ into slab; orders    │ level non-empty
          │ price→slot   │ doubly-linked (FIFO) │ (next-best find)
          ▼              ▼                      ▼
   CompressionMap    OrderSlot chain        find_next / find_prev
   (price → u32)     head → … → tail        (O(depth) skip-empty)

• A price maps to a slot index via CompressionMap::price_to_index (bisection, ~2 ns).
• active_levels[slot] is a PriceLevel: head/tail handles into the slab, plus total_qty and order_count.
• Orders at a level are a doubly-linked list threaded through the slab (next/prev are slab handles), head→tail = time priority.
• bid_occ / ask_occ mark which slots are non-empty, so next-best-level is a bitmap find, never a scan.

Slab arena (slab.rs)

Slab<OrderSlot> is a preallocated Vec<OrderSlot> with a free-list head and a bump cursor.

• alloc: pop free_head (reuse) or bump bump_next (fresh). O(1). Asserts on exhaustion.
• free: push the slot onto free_head. O(1). The free-list chains through each slot's next field.
• no-leak invariant: live = bump_next − |freelist|. Every alloc pairs with at most one free. free_count() walks the list for test/introspection cross-checks (not the hot path).

OrderSlot is 128 bytes, #[repr(C, align(64))] (compile-time asserted): cache line 0 is hot (price, remaining_qty, side, flags, tif, next/prev/tick_index), cache line 1 is cold (user_id, sequence, original_qty, timestamp_ns, order ids). Cancel and match touch only line 0.

Compression map (compression.rs)

A price→slot quantization centered on mid_price, so the whole tradeable range fits a bounded, dense level array instead of one slot per tick. Five zones by absolute distance from mid:

zone	distance from mid	ticks per slot
0	0–5%	1 (1:1 near mid)
1	5–15%	10
2	15–30%	100
3	30–50%	1000
4	50%+	catch-all, 1 slot per side

price_to_index is a 2–3 comparison bisection over the four raw-price thresholds, then an in-zone offset. Each zone is a symmetric ± band around mid laid out at ascending index, so the index is a sawtooth: it is not globally price-monotonic across zone boundaries. Two consequences enforced everywhere:

• BBA is tracked by raw price, never by index. best_bid_px / best_ask_px are compared as prices; the tick index is only a slot address.
• Next-best walks price_asc, not the raw bitmap. build_price_asc precomputes the ≤10 zone-half index sub-ranges ordered by price band (within each, ascending index == ascending price). Recomputed only on construction / recenter.

Orders sharing a slot (zones 1–4) store their exact price; the matcher checks the real price per order.

Occupancy bitmap (occupancy.rs)

Per-side hierarchical set-bit index over the compression slots: bit set = "this level holds ≥1 resting order of that side". levels[0] is one bit per slot; each higher level is one bit per word of the level below. ~120k slots ⇒ 3 levels (1929 + 31 + 1 words), ~15 KB.

• set / clear — O(depth); climb up only while a word flips empty↔non-empty, so a deep cancel is a couple of word writes.
• find_next / find_prev — O(depth); climb summary words to find a candidate, then descend via trailing_zeros / leading_zeros.
• find_first_in / find_last_in — bounded to a price_asc sub-range.

Maintained in lockstep with PriceLevel::order_count at every site that crosses the 0 boundary: insert_resting (0→1 sets), unlink_order (→0 clears — covers cancel and maker-fill), migrate_single_level, trigger_recenter (reset), and snapshot load (rebuild_occupancy). A stale bit would be a phantom or skipped level, i.e. a matching bug; scan_reference_test.rs cross-checks the bitmap path against a brute-force scan. Deep why: notes/occupancy.md.

Best-bid / best-ask

Cached as (best_bid_tick, best_bid_px) / (best_ask_tick, best_ask_px). Updated on the fly during insert (compare raw price) and match. When a level empties, scan_next_bid / scan_next_ask walk price_asc in price order and take the extreme set bit per sub-range — the common near-BBO case returns after touching a few zone-0 summary words.

Matching algorithm (matching.rs)

process_new_order(book, order) — one aggressor in, events out. Event buffer is reset at entry, so book.events() afterward is exactly this order's events.

process_new_order(book, order):
    event_buf.reset()
    validate tick/lot           -> OrderFailed(VALIDATION) on fail
    reduce-only:                 clamp qty to net position,
                                 or OrderFailed(REDUCE_ONLY)
    post-only:                   OrderCancelled(POST_ONLY) if would cross
    FOK:                         can_fill_fully()? else OrderFailed(FOK)
                                 (pre-check — no partial, no rollback)

    cross loop (Buy vs asks / Sell vs bids):
        while remaining > 0 and touch level exists:
            match_at_level(book, touch, order)
            if touch emptied: best = scan_next_*()
            if no progress or book side empty: break

    residual:
        remaining > 0 and IOC   -> OrderDone(CANCELLED, filled/remaining)
        remaining > 0 otherwise -> insert_resting + OrderInserted
        remaining == 0          -> OrderDone(FILLED)

    if best bid/ask tick changed: emit BBO

match_at_level(book, tick, aggressor) walks the level from head (FIFO), and per maker:

    skip if maker price doesn't cross aggressor limit
    fill_qty = min(aggressor.remaining, maker.remaining)
    decrement both; decrement level.total_qty
    emit Fill                       <-- fill precedes any OrderDone
    update_positions_on_fill(taker, maker)
    if maker fully filled:
        unlink_order (clears occupancy if level empties)
        emit OrderDone(FILLED) for the maker
        slab.free(maker)

Event ordering upholds invariant #1 (fills precede ORDER_DONE): the maker's Fill is emitted before its OrderDone, and both before the taker's terminal event at the end of process_new_order. Invariant #2 (exactly-one completion): every return path emits exactly one terminal event for the aggressor.

can_fill_fully (FOK) walks only the crossing levels in price order via price_asc + occupancy, summing each level's maintained total_qty and early-exiting the instant the running total reaches the order size — O(levels crossed), never a per-order or full-slot scan. A whole level shares one price, so total_qty counts it exactly.

Incremental recentering (migration.rs)

When mid drifts past 50% of zone-0 half-width, the book rebuilds its compression map without a stop-the-world pause:

• trigger_recenter(new_mid) — swap in a fresh empty active array and new CompressionMap; keep the old array as old_levels; reset occupancy + price_asc; enter Migrating.
• resolve_level(price) — lazy: migrate the old level covering price on first access past the frontier.
• migrate_batch(n) — proactive: migrate n levels per idle call, advancing bid/ask frontiers until both cover the old range, then complete_migration back to Normal.

During migration two arrays are live; migrate_single_level re-links each order into the new array and re-sets occupancy / BBA.

Event buffer

Fixed Box<[Event; 65_536]> on the Orderbook, reset per process_new_order. emit asserts on overflow (invariant: ME never drops events). Worst case is a market order sweeping every resting order at ~3 events per fill (Fill + maker OrderDone + final BBO), so 65,536 slots covers ~21k fills in one cascade. The caller drains book.events() after each order and fans out to two transports (fills/BBO/done → risk; inserts/cancels/fills → marketdata); that fan-out lives in the ME process, not in this crate.

How it plugs into the ME tile

rsx-book is a library of pure data structures — no runtime, no threads, no I/O. The matching-engine process (rsx-matching) owns one Orderbook per symbol and drives it from a pinned tile loop: decode an incoming order off the transport, call process_new_order, drain book.events(), and publish. Because each book is single-owner state on one thread, it needs no locking; scale-out is one book (one core) per symbol. rsx-marketdata runs the same book as a shadow (fed inserts/cancels/fills) to serve L2 / BBO. The book makes no thread-safety claims because no caller shares it across threads.

Trust boundary. The book is internal, single-owner, and never touches the network. Authentication, margin, and risk limits are enforced upstream (gateway JWT, risk tile) before an order reaches it — the book trusts that boundary and does not re-check caller identity or solvency on the hot path. It validates only structural well-formedness (tick / lot multiples, reduce-only / post-only semantics), the checks it needs to keep its own state consistent.

Memory layout (config-driven)

Component	Sizing	Memory
Order slab	capacity × 128 B (constructor arg)	e.g. 78M slots ≈ 10 GB virtual; pages fault in on use
Price levels (×2: active + staging)	~120k slots × 24 B × 2	~6 MB (grows with range/tick)
Occupancy (×2 sides)	~15 KB each	negligible
Event buffer	[Event; 65_536] heap-boxed	~8 MB

Slab capacity is a caller choice; level-array and occupancy sizes follow from mid/tick via the compression map.

Operation complexity

operation	cost
Insert (rest)	O(1) — bisect + slab alloc + tail link + bit set
Cancel by handle	O(1) — slab unlink + bit clear (+ O(depth) next-best only if the touch emptied)
Match, touch survives	O(fills) — depth-invariant (~60–65 ns)
Match, touch clears	O(fills) + O(depth) next-best find (~145 ns)
Deep sweep of K levels	O(K · depth) — linear in levels swept, not in slots
Best bid/ask read	O(1) — cached
Recenter	amortized via lazy + batched migration; no global pause

Architectural decisions

Runtime: none — pure data structures. rsx-book is a library, not a process: no async runtime, no threading primitives, no I/O. The caller owns the loop and the threading model. Consumers today are rsx-matching (the ME tile) and rsx-marketdata (shadow book), both single-owner on whatever thread drives them.

rsx-book benchmark — 2026-07-04 (clean quiet-box run)

What: the full rsx-book Criterion suite (book_bench + deep_book_bench), the matching/orderbook library in isolation. Box: AMD Ryzen 9 5950X (4-vCPU slice), single core, 1 thread/core. Method: the RSX cluster was STOPPED first (its ME+Risk busy-spin at ~90% CPU otherwise poisons the numbers — a contaminated earlier run showed +757% noise). Criterion, closed-loop, n=50-100 per case. Commit f45e0a0. Source: cargo bench -p rsx-book.

Headline — matching is O(1) in book depth

Matching a marketable order stays ~65 ns whether the book holds 100 thousand or 10 MILLION resting orders. Best case 28 ns at depth 1. Depth-invariant because the compression map + slab arena make level lookup and order pop constant-time, not a tree walk.

resting orders in book	match latency (median)
1	28.1 ns
100	60.0 ns
1,000	61.0 ns
10,000	60.2 ns
100,000	64.5 ns
1,000,000	66.3 ns
10,000,000	65.5 ns

(match_depth/* + deep_flat_match/* — the same op across depths.)

Primitives (per-op, single core)

op	median
slab alloc (bump)	556 ps
slab alloc (freelist)	1.44 ns
slab free	8.30 ns
compression price→index (near)	1.91 ns
compression price→index (far)	2.18 ns
price→index bisection	1.99 ns
compression map build	12.7 ns
lazy recenter (per access)	1.95 ns
modify order qty-down	2.12 ns
post-only reject	5.96 ns
deep flat insert (100k–10M book)	238–260 ns

Bulk / amortized

op	median	note
insert+cancel, depth 1k–100k	160–350 ns	amortized per pair
cancel, depth 1k–100k	15–170 ns
recenter 10k orders	308 µs	bulk compression-map rebuild
best-bid scan after cancel	50 µs	the known O(n) scan (BUGS.md)

Caveats (honest)

• Lab microbenchmark, not system TPS. Single core, in-process, no I/O, no network — this is the algorithm, not the exchange round-trip (that's the transport-bound ~1.1 ms cross-process figure, a different story).
• Criterion closed-loop, quiet box, single run — re-run before quoting elsewhere.
• match_by_type/fok_full was a separate finding (bugs.md FOK-AVAILABLE-LIQUIDITY-ON-SCAN): FOK's old pre-check was its own O(N-resting) full-book scan, ~296 µs at depth 10k, not touched by the occupancy-bitmap fix. Also fixed 2026-07-04 — see the FOK section below; now ~118 ns.

Post-scan-fix — occupancy bitmap (2026-07-04, commit da9a2b4)

The MATCHING-BENCH-ORDERTYPE-FIXTURE finding above was WRONG about root cause. The 32-224 µs match_by_type/insert_cancel_depth numbers were NOT fixture alloc/drop bleed — post_only_reject ran on the exact same depth-10k fixture and measured 5.96 ns, which is only possible if the fixture itself was cheap. The real cause: scan_next_bid/scan_next_ask did an O(compression- slots) linear scan (~100k slots) whenever a price level actually emptied (match-that-clears-the-touch, or cancel-that-empties-a-level) — post_only_ reject never clears a level, so it never paid the scan; the match_depth/ deep_flat_match numbers above dodged it too, because their taker is always replenished onto the SAME touch level before it can go empty. Every op whose fixture design clears a level (match_by_type's taker_fill, cancel-driven depth sweeps) hit the scan and paid 30-1000x the true match cost.

Fixed by a hierarchical occupancy bitmap (rsx-book/src/occupancy.rs): 1 bit/compression-slot + a u64 summary tree, find_next/find_prev via trailing/leading-zeros, O(depth=3) instead of O(slots). Re-measured 2026-07-04 on the same quiet box, same commit family:

bench	before da9a2b4	after	speedup
match_ioc_vs_1k_asks (clears touch level)	4.37 µs	145 ns	30x
match_by_type/ioc_full	~80 µs	79.4 ns	~1000x
match_by_type/gtc_full_cross	~80 µs	79.7 ns	~1000x
match_by_type/sweep_10_levels	~1 ms	700 ns	~1400x
match_by_type/post_only_reject	5.96 ns (unaffected, never clears)	6.17 ns	—
match_by_type/fok_full	in the quarantined 99-224 µs / 1 ms range	296 µs → 118 ns	fixed separately (FOK section below)

Happy path is unaffected, confirming it was never the fixture: match_depth/1000 61.0 ns → 61.3 ns, match_depth/10000 60.2 ns → 63.5 ns — same ~60-65 ns band as the original headline table above, within run-to-run noise.

Budget claim, corrected: the exchange's <500 ns ME-match budget was previously met only on the path that never clears a resting level. Any real match that empties the touch (a common case — the whole point of matching is to consume liquidity) cost 32-224 µs, 200x over budget. It is now genuinely met on both paths: 60-65 ns when the touch survives, 145 ns when it clears.

rsx-book vs. the obvious baseline (BTreeMap<price, VecDeque<order>>)

Per the CEO-audit "so what, vs the obvious thing" ask (.ship/34-COMPARE- RESEARCH/PLAN.md): a textbook order book — BTreeMap<i64, VecDeque<Order>> per side, HashMap<order_id, (side, price)> to locate an order for cancel (linear scan within its level's VecDeque — no slab, no compression map, no occupancy bitmap). Same Criterion harness (rsx-book/benches/harness.rs), same box, same RNG seed per depth so both books hold statistically-identical content. Source: rsx-book/benches/compare_naive_bench.rs, cargo bench -p rsx-book --bench compare_naive_bench.

op	depth	rsx-book	naive BTreeMap	speedup
match, clears touch level	100	72.1 ns	106.5 ns	1.5x
match, clears touch level	1,000	71.7 ns	110.2 ns	1.5x
match, clears touch level	10,000	71.6 ns	117.8 ns	1.6x
insert + cancel (pair)	100	160.0 ns	241.7 ns	1.5x
insert + cancel (pair)	1,000	162.2 ns	286.8 ns	1.8x
insert + cancel (pair)	10,000	171.1 ns	349.1 ns	2.0x
cancel	100	18.4 ns	101.0 ns	5.5x
cancel	1,000	17.8 ns	146.4 ns	8.2x
cancel	10,000	17.9 ns	178.4 ns	10.0x

Honest reading: BTreeMap was never O(book-size) for this — tree removal and next-best lookup are both O(log n), so it never had rsx-book's pre-fix O(slots) bug; the gap here is constant-factor (slab handle vs. hash lookup + tree traversal + heap alloc/dealloc per level), not asymptotic. The gap is narrowest on match (1.5-1.6x, both O(1)-ish at these depths) and widest on cancel (5.5x→10x, growing with depth) — rsx-book's cancel is a pure slab unlink (O(1), no tree, no hash lookup), while the naive cancel pays a HashMap lookup plus a BTreeMap tree descent plus a VecDeque scan, and that tree descent cost grows with depth. insert+cancel sits between the two (1.5x→2.0x, growing) since it's dominated by the same insert-side BTreeMap entry-or-default cost at both ends.

FOK fill-or-kill — no map, just "try to match it" (2026-07-04)

FOK (fill-or-kill) must fill the whole order immediately or reject it. The old check (available_liquidity) answered "is there enough crossable liquidity?" with a SEPARATE O(N) pass: it iterated all ~100k active levels AND every resting order on each, summing crossable qty, before matching. At depth 10k that pre-check was the entire cost — fok_full sat at ~296 µs while every other order type was 60-145 ns.

The fix is not a new structure (no histogram, no per-side liquidity index). FOK is just "try to match it, take it or don't", so can_fill_fully walks only the crossing levels in price order — the same traversal a real match performs, via the book's existing best-level index (price_asc + occupancy) — and sums each level's already-maintained total_qty, stopping the instant the running total reaches the order size. A whole price level shares one price, so it either crosses or it doesn't; total_qty counts it exactly with no per-order walk. Complexity: O(levels crossed, early-exit) instead of O(slots + orders).

bench	before	after	speedup
match_by_type/fok_full (depth 10k)	296 µs	~118 ns	~2500x (−99.95%)

Correctness is pinned by rsx-book/tests/fok_liquidity_test.rs: 3000 FOK probes over multi-zone random flow, each compared to an independent brute-force sum over every resting order — the fast walk must fail (no fills) exactly when brute-force liquidity < order size, and fully fill otherwise. Caveat: the ~118 ns figure is from a lightly-contended box (a parallel bench was running); the −99.95% magnitude is unambiguous, but re-run on a fully quiet box before quoting the exact ns elsewhere.

Distribution robustness (2026-07-04, distribution_bench.rs)

Does the occupancy bitmap hold O(depth) regardless of how orders are laid out? Next-best / match-that-clears / cancel measured under dense (packed zone 0), sparse (gaps across zones), and concentrated (single wall) shapes, at depth 1k and 10k. Quiet box, single core, medians (ns):

op	dense 1k / 10k	sparse 1k / 10k	concentrated 1k / 10k
next_best (pure scan)	21.7 / 21.8	29.0 / 26.6	25.3 / 25.0
match_clears (clear touch + scan)	73.8 / 71.9	81.2 / 77.8	77.9 / 77.8
cancel_touch (cancel best → scan)	41.8 / 43.3	46.0 / 48.7	42.9 / 43.2
cancel_deep (far level, no scan)	26.6 / 26.8	26.3 / 25.8	26.2 / 25.9

Verdict: O(depth), not O(slots), in every shape. Every op is flat 1k→10k (10× the orders, ~same latency). Sparse adds only a small additive constant to the scan-bearing ops (+5-7 ns) from skipping empty summary words — additive, not proportional to the gap, the O(depth) signature. cancel_deep is a dead-flat ~26 ns baseline (pure slab unlink + O(1) bit clear), so the scan is the only distribution-sensitive part and it stays bounded. No shape degrades.

Tail latency (2026-07-04, tail_bench.rs)

Closes the last CEO-eval gap: every figure above is a Criterion median (p50). This section measures p50/p99/p99.9 on the hot ops, with special attention to match_clears — the level-clearing path the occupancy bitmap fixed (see the "Post-scan-fix" section above). Quiet box (RSX cluster stopped), single core (pinned, same harness::pin() as every other bench in this suite), dense-shape book (contiguous levels behind a 1-order touch), depths 1k and 10k. Source: rsx-book/benches/ tail_bench.rs. Run: cargo bench -p rsx-book --bench tail_bench.

Methodology — and why a naive per-op timer would lie here

These ops run in 25-100 ns. Instant::now() on this box (vDSO clock_gettime(CLOCK_MONOTONIC)) costs ~20-30 ns per call — a large fraction of the op — so timing every single op individually mostly measures the timer, not the op. Measured directly (back-to-back Instant::now() calls, nothing timed in between, n=100,000):

	mean	p50	p99	p99.9	max
timer floor	24.0 ns	20.0 ns	31.0 ns	31.0 ns	114,485 ns

The floor's own max (114 µs) is OS scheduling jitter on an otherwise idle box — a reminder that any single huge max reading below could be noise, not the algorithm, and is called out per-op rather than overclaimed.

Given that floor, this harness reports two numbers per op, both printed by the harness, only one of them quoted as authoritative:

1. Batch-amortized (the number in the table below). Batches of BATCH=64 consecutive ops are timed as one span and divided by 64, so timer overhead contributes <1 ns to the per-op figure. 2,000,000 ops per op/depth combo -> 31,250 batch samples, so p99.9 has ~31 points above it (a real quantile, not a handful of outliers).
2. Single-op raw timer (context only, NOT quoted as fact). Every op timed individually, n=100,000. Included in the raw harness output so the reader can see it sits close to the timer floor (p50 50-90 ns vs. the 20-31 ns floor) — i.e. its distribution is partially timer noise, and its p99/p99.9 should not be read as the op's true tail.

Both runs are preceded by 20,000 discarded warmup iterations (cache / branch-predictor warmup) and every op result is passed through std::hint::black_box so the compiler cannot elide it. Single run, quiet box, commit f45e0a0+tail_bench.rs — re-run before quoting elsewhere, per the standing caveat on every table in this report.

Results (batch-amortized, ns/op)

op	depth	mean	p50	p99	p99.9	max
match (partial fill, touch survives)	1,000	29.4	28.3	35.7	154.8	1,949.9
match (partial fill, touch survives)	10,000	29.0	28.2	41.3	118.5	266.9
match_clears (empties touch → occupancy scan)	1,000	71.1	70.5	76.5	175.2	1,289.4
match_clears (empties touch → occupancy scan)	10,000	70.2	68.2	109.4	216.5	542.3
cancel_touch (cancel best → scan)	1,000	46.4	43.2	90.0	175.6	1,406.1
cancel_touch (cancel best → scan)	10,000	40.8	39.6	74.4	173.3	583.1
cancel_deep (far level, no scan)	1,000	26.4	26.1	28.0	89.2	232.9
cancel_deep (far level, no scan)	10,000	28.0	26.8	40.5	97.8	303.2

Reading it

match_clears has a tight tail, not a fat one. p99/p50 is 1.08-1.60× (76.5/70.5 at depth 1k, 109.4/68.2 at depth 10k) — nowhere near the 30-1000× blowups the pre-fix O(slots) scan produced (see the "Post-scan-fix" section: 4.37 µs, ~80 µs, ~1 ms before). The occupancy-bitmap find (O(depth=3) trailing/leading-zeros) does not have a data-dependent slow path at these depths; the p99.9 bump (~175-217 ns, ~2.5-3× p50) is consistent with occasional branch mispredicts / cache misses on the summary-word walk, not an asymptotic blowup, and stays flat 1k→10k (matching the O(depth) verdict from the distribution-robustness section above).

match (happy path, touch survives) is the tightest of the four — p99/p50 ~1.1-1.5×, as expected: no scan, no bitmap walk, just slab pop + level update.

cancel_touch has the widest p99/p99.9 spread of the four (p99/p50 up to 2.1×, p99.9/p50 up to 4.4×) — it does two things per op (insert + cancel-that-empties-and-scans), so it accumulates two sources of jitter instead of one; cancel_deep's single-op, no-scan baseline is correspondingly the tightest apart from match.

Caveats. Single run, quiet box, dense shape only (the distribution-robustness section above already covers sparse/ concentrated — this section is about the tail, not the shape). The single-op numbers exist in the raw harness output for context but are NOT reported here as fact — they sit too close to the ~20-30 ns timer floor to trust their tail. max columns include rare multi-hundred-ns to ~2 µs batch averages, i.e. one op inside that batch of 64 likely stalled for tens of µs (OS scheduling, not algorithm) — consistent with the timer floor's own 114 µs max on an idle box. Re-run before quoting an exact ns elsewhere.

rsx-book vs. the obvious baseline (BTreeMap<price, VecDeque<order>>)

Per the CEO-audit "so what, vs the obvious thing" ask (.ship/34-COMPARE- RESEARCH/PLAN.md): a textbook order book — BTreeMap<i64, VecDeque<Order>> per side, HashMap<order_id, (side, price)> to locate an order for cancel (linear scan within its level's VecDeque — no slab, no compression map, no occupancy bitmap). Same Criterion harness (rsx-book/benches/harness.rs), same box, same RNG seed per depth so both books hold statistically-identical content. Source: rsx-book/benches/compare_naive_bench.rs, cargo bench -p rsx-book --bench compare_naive_bench.

op	depth	rsx-book	naive BTreeMap	speedup
match, clears touch level	100	72.1 ns	106.5 ns	1.5x
match, clears touch level	1,000	71.7 ns	110.2 ns	1.5x
match, clears touch level	10,000	71.6 ns	117.8 ns	1.6x
insert + cancel (pair)	100	160.0 ns	241.7 ns	1.5x
insert + cancel (pair)	1,000	162.2 ns	286.8 ns	1.8x
insert + cancel (pair)	10,000	171.1 ns	349.1 ns	2.0x
cancel	100	18.4 ns	101.0 ns	5.5x
cancel	1,000	17.8 ns	146.4 ns	8.2x
cancel	10,000	17.9 ns	178.4 ns	10.0x

Honest reading: BTreeMap was never O(book-size) for this — tree removal and next-best lookup are both O(log n), so it never had rsx-book's pre-fix O(slots) bug; the gap here is constant-factor (slab handle vs. hash lookup + tree traversal + heap alloc/dealloc per level), not asymptotic. The gap is narrowest on match (1.5-1.6x, both O(1)-ish at these depths) and widest on cancel (5.5x→10x, growing with depth) — rsx-book's cancel is a pure slab unlink (O(1), no tree, no hash lookup), while the naive cancel pays a HashMap lookup plus a BTreeMap tree descent plus a VecDeque scan, and that tree descent cost grows with depth. insert+cancel sits between the two (1.5x→2.0x, growing) since it's dominated by the same insert-side BTreeMap entry-or-default cost at both ends.