Cache-Friendly Order Book II

Walk through what the week 6 book does when an order arrives at a price that already has resting orders:

1. Look up the level in a BTreeMap: a few node hops, each a dependent load (you cannot fetch node 2 until node 1 tells you where it is). With a large book, upper nodes may be cached but lower ones often are not. (In the repo, week 26 already replaced the tree with a sorted Vec of prices per side. That's one dense array and no allocation, but a level away from the touch is still a binary search: log₂ L dependent probes.)
2. Append to the level's FIFO: touch the level and its tail order.
3. Insert into the order-id map: hash, probe, write — another cache line or two.

Every one of those is fine in a microbenchmark that keeps the whole book in L1. Under realistic flow — thousands of levels, hundreds of thousands of orders, a market-data burst evicting everything — they are the profile you saw in week 26: low IPC, high LLC MPKI. The fix is to make the common operations touch fewer, more predictable lines.

A ladder side is an array of len levels covering prices base, base + tick, …, base + (len − 1) · tick. The index of a price is (px − base) / tick. Everything that can go wrong with that one line will, eventually, in production:

• Prices off the tick grid must be rejected before they get here (week 8), but the ladder should still classify them rather than silently rounding.
• Negative prices exist. Calendar spreads, some energy futures (WTI front-month settled at about −$37 in April 2020) and many synthetic instruments trade below zero. Rust's / truncates toward zero and % keeps the dividend's sign, so naive code mis-indexes negative offsets — and (negative_i64) as usize is a gigantic positive index. Use div_euclid / rem_euclid, and check the sign before casting.
• Hostile input. The price comes from a client message. px − base can overflow i64 for extreme values — a panic in debug builds, silent wrap-around in release. Do the subtraction in i128 (or with checked_sub) and classify.
• The market moves. When the touch drifts toward the edge of the window, re-centre: compute a new base that keeps the same tick grid and puts the current mid near the middle. Moving levels is the cold path; how often it happens depends on window size and volatility.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Slot {
    In(usize),
    Below,
    Above,
    OffTick,
}

/// A dense window of `len` price levels: base, base + tick, ...,
/// base + (len - 1) * tick. Prices are integers and may be negative.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Ladder {
    pub base: i64,
    pub tick: i64,
    pub len: usize,
}

impl Ladder {
    pub fn new(base: i64, tick: i64, len: usize) -> Self {
        assert!(tick > 0 && len > 0);
        Ladder { base, tick, len }
    }

    /// Map a price straight off the wire (ANY i64) to a slot:
    /// OffTick if (px - base) is not a multiple of tick; otherwise Below /
    /// Above if outside the window; otherwise In(index).
    /// Must not overflow or panic for any input.
    pub fn index(&self, px: i64) -> Slot {
        todo!()
    }

    /// Price of level `idx` (idx < len).
    pub fn price(&self, idx: usize) -> i64 {
        todo!()
    }

    /// Same tick and len, re-centred so that `mid` — rounded DOWN onto this
    /// ladder's tick grid — lands at index len / 2. Keep the grid: the new
    /// base must differ from the old one by a multiple of tick.
    pub fn recenter(&self, mid: i64) -> Ladder {
        todo!()
    }
}

List the questions the book answers, by frequency: is this level non-empty (every best-price search), how much is resting at this level (market data, depth, FOK checks), which order is at the head of this level (matching), what are this order's client id and timestamps (only when reporting). Then lay memory out so the frequent questions read dense memory and the rare ones pay for the indirection.

// Array-of-structs: one level = 24 bytes (20 of data, padded to align 8).
// A 64-byte line holds 2.67 levels; a depth scan drags head/tail along.
#[repr(C)]
struct Level { qty: u64, head: u32, tail: u32, count: u32 }

// Struct-of-arrays: each question reads only its own array.
struct LadderSide {
    occupied: Vec<u64>, // 1 bit per level: 512 levels per cache line
    qty: Vec<u64>,      // 8 levels per line — what depth and aggregation read
    head: Vec<u32>,     // 16 per line — what matching reads
    tail: Vec<u32>,     // what adds read
    base: i64,
}

The occupancy bitmap is the trick that makes best-price maintenance cheap. When the best ask level empties, the next best is the lowest set bit at or above the old index: one trailing_zeros (a single tzcnt instruction on x86) per 64 levels. When a new bid improves the best, it is a comparison. No tree, no scan of empty levels.

Orders get the same treatment. The slab from week 27 can hold two arrays: a hot part touched on every match and cancel — remaining quantity, prev/next slab indices, level index, side — and a cold part touched only for reporting — client order id, account, entry timestamp, original quantity. Keeping the hot part to 16–24 bytes means two or three orders per cache line as you walk a level's FIFO.

One caution: cache lines are 64 bytes on current x86 and most Arm server cores, but 128 bytes on Apple's M-series cores. Reason about lines, but measure on the machine you deploy to.

A branch the predictor gets right is almost free. A branch it gets wrong flushes the speculative work behind it — roughly 15–20 cycles on recent x86 cores, more than an L2 hit. Matching engines are full of data-dependent branches: which side is this order, does it cross, is this level now empty, is this price better than the best. On a mixed stream some of those are close to coin flips.

The branchless alternative computes both outcomes and selects with a mask, which compilers turn into a conditional move (cmov on x86, csel on Arm):

fn select(cond: bool, a: i64, b: i64) -> i64 {
    let mask = -(cond as i64);  // all ones or all zeros
    b ^ ((a ^ b) & mask)
}

Branchless is not automatically faster:

• If the branch is predictable — most adds do not improve the best price — the branch costs almost nothing and a cmov adds a data dependency on both inputs to the critical path.
• The compiler may turn your branchless source back into a branch, or your branchy source into a cmov. Recent Rust has std::hint::select_unpredictable to state the intent; either way, read the assembly (week 37 goes deeper) and measure with perf stat -e branch-misses.
• Beware the classic arithmetic tricks. min = b + ((a - b) & ((a - b) >> 63)) overflows when a − b does — exactly for the i64::MIN/i64::MAX sentinels an empty book side uses. Masks built from comparisons do not overflow.

/// Branch-free select: `a` if cond else `b`. No if/match/&&/|| — build a
/// mask from `cond as i64` and combine with bitwise operations.
pub fn select(cond: bool, a: i64, b: i64) -> i64 {
    todo!()
}

/// Correct for ALL i64 inputs, including i64::MIN and i64::MAX.
pub fn min_branchless(a: i64, b: i64) -> i64 {
    todo!()
}

pub fn max_branchless(a: i64, b: i64) -> i64 {
    todo!()
}

/// Sentinels for an empty side: no bid is below i64::MIN, no ask above i64::MAX.
pub const EMPTY_BID: i64 = i64::MIN;
pub const EMPTY_ASK: i64 = i64::MAX;

/// New best price after a resting order is added at `px`:
/// bids keep the highest price, asks the lowest. Branch-free.
pub fn best_after_add(best: i64, px: i64, is_bid: bool) -> i64 {
    todo!()
}

/// Occupancy bitmap: bit (i % 64) of word (i / 64) is set when level i has
/// resting quantity. Lowest non-empty level (best ask on an ascending
/// ladder). Hint: u64::trailing_zeros.
pub fn lowest_set(bits: &[u64]) -> Option<usize> {
    todo!()
}

/// Highest non-empty level (best bid). Hint: u64::leading_zeros.
pub fn highest_set(bits: &[u64]) -> Option<usize> {
    todo!()
}

Hardware prefetchers watch your access stream and fetch ahead when they detect a pattern — sequential lines, constant strides, and on Intel the adjacent line of a 128-byte pair. Dense arrays benefit automatically: a depth scan over the qty array is prefetched for free. Pointer chasing is invisible to them: the next address is not known until the current load completes.

Software prefetch fills that gap when you know an address early. The best example in an exchange: a cancel or modify message carries the order id. As soon as you have decoded the id, prefetch the order's slab slot and its level; then do the remaining decoding, session checks and risk checks; by the time you touch the order, the line is (hopefully) in L1.

#[cfg(target_arch = "x86_64")]
#[inline(always)]
fn prefetch_read<T>(p: *const T) {
    use std::arch::x86_64::{_mm_prefetch, _MM_HINT_T0};
    // A prefetch is a hint: it never faults, even on a bad address.
    unsafe { _mm_prefetch::<_MM_HINT_T0>(p as *const i8) }
}

Prefetch only helps if it is issued early enough — a DRAM miss takes hundreds of cycles, so a prefetch issued twenty instructions before the load hides almost nothing — and not so early that the line is evicted again. It costs a load slot and cache capacity when it is wrong. Treat every prefetch as an experiment: keep it only if the open-loop p99 or the LLC-miss count on that path improves.

A book benchmark is only as good as its price distribution. Benchmark every order at one price and both books live in L1 — the comparison measures nothing. Draw prices uniformly over thousands of ticks and the ladder spends its time in the sparse fallback — an equally fictional market. Use the shape from Day 2: most orders within a few ticks of a slowly moving mid, a fat tail of far orders, cancels biased toward recent orders, occasional aggressive orders that sweep a few levels, and a book large enough (tens to hundreds of thousands of resting orders) that it does not fit in L1/L2.

Run both books under the same generator, seed and machine, and compare open-loop latency (week 25) as well as throughput. Use the differential test from week 12 to prove they produce identical events.