Measuring updates and defining the book interface

Seeing it

Your machine’s numbers come from a replay: record a stream of real updates once, and have a small program feed them from the file to the same apply with no network, so whatever is measured is the book. To time each call, read the time-stamp counter before and after it with rdtsc, the instruction that reads a counter ticking at a fixed rate near the nominal clock, and report p50, p99 and max, never the mean. To see where the time goes, replay 10 million updates under perf stat, which counts hardware events over a run, with taskset pinning it to core 3, and divide each count by 10,000,000:

perf stat -e cycles,instructions,cache-misses,branch-misses \
    -- taskset -c 3 ./replay tree updates-10m.bin
perf record -g -- taskset -c 3 ./replay tree updates-10m.bin
perf report

cycles per update is the number to set against the ladder. instructions over cycles is instructions per cycle, near the core’s best on the array and well below it on the tree, where the core waits on each node’s load. cache-misses counts, on most parts, last-level misses, the ones that go to DRAM; branch-misses counts mispredictions at 15–20 cycles each, mostly from the searches. Replay once with a book that does nothing and subtract, since the replay’s own loop is in every count. perf record -g then samples where the cycles land, and perf report names the functions: for the tree, the search in alloc::collections::btree, then malloc and free; for the Vec, memmove; for the array, apply and little else.

6.4 Anatomy of an update: from bytes to a changed book

A depth update arrives as the 48 bytes the networking chapter decoded: length, kind and instrument, the venue’s sequence number, a price in ticks, a quantity in lots, the venue’s timestamp and a side. This section starts with those fields already integers in a struct and follows them to a changed book: check that this is the next update, find the level it names, write the quantity, keep the best price correct, decide whether anything the strategy acts on has changed, and tell it, once. None of it is particular to trading: a database replica applying its primary’s change log checks the log position, finds the row, writes the new value and decides whom to tell, in the same order.

The representations sit behind one Rust trait, Rust’s name for an interface, a set of functions a type promises to provide, so the feed handler is written once. This is the Book trait:

pub type Ticks = i64;   // price as a count of ticks
pub type Lots  = i64;   // quantity as a count of lots

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum Side { Bid, Ask }

#[derive(Clone, Copy)]
pub struct Update {
    pub seq: u64,     // the venue's update number
    pub side: Side,
    pub price: Ticks,
    pub qty: Lots,    // 0 means the level is removed
}

#[derive(Clone, Copy, PartialEq, Eq, Default, Debug)]
pub struct Top {
    pub bid: Option<(Ticks, Lots)>,
    pub ask: Option<(Ticks, Lots)>,
}

pub trait Book {
    /// Apply one level update. Returns true when the top of book changed.
    fn apply(&mut self, u: &Update) -> bool;
    fn best_bid(&self) -> Option<(Ticks, Lots)>;
    fn best_ask(&self) -> Option<(Ticks, Lots)>;
    fn top(&self) -> Top { Top { bid: self.best_bid(), ask: self.best_ask() } }
}

apply is the one function that changes the copy: it writes one decoded update into the structure and returns true when the top of the book, the best bid and best ask with their quantities, differs afterwards. best_bid and best_ask return a side’s best price and quantity, or None for an empty side, and top packs both into a Top, all the strategy is ever given. The implementations are ArrayBook (the dense array), VecBook (the sorted Vec) and TreeBook (a BTreeMap per side). The sequence check is deliberately outside apply: the structures only store levels, and one check in the feed handler guards all three.