The book-update latency ladder

6.3 The ladder of an update

Every update the feed delivers, a delta giving one level its new quantity, ends in the same act: the program finds that level in its copy of the book, writes the new quantity, and works out whether the best bid or best ask has moved. The code calls it apply; the next section takes it apart, and this one prices it. The price depends first on the representation, the data structure the copy is kept in; the table compares four. A dense array has a slot for every price in a band, so a price’s slot is found by subtraction, not search. A sorted Vec, Rust’s growable array, holds only the occupied levels in price order and finds one by binary search, halving the range at each compare; an insert or delete in the middle shifts everything behind it with a memmove, a bulk copy. A BTreeMap, the ordered tree in Rust’s standard library, keeps about eleven prices per node with pointers to the nodes below, so a lookup is a pointer chase: each load’s address is known only when the previous load returns. A HashMap keyed by price finds any price by hashing it but keeps no order, so naming the best price means looking at every key.

A cursor is the dense array’s stored index of the best price on a side, so reading the best bid is one load. A window is the band of prices a dense array covers, since a slot for every cent up to $68,123.45 would be 6.8 million slots, 54 MB a side; a bitmap beside it keeps a bit per slot saying whether the level is occupied, and trailing_zeros and leading_zeros, instructions counting the zero bits at either end of a 64-bit word, find the next occupied level 64 slots at a time. A re-base is moving that band when the price walks out of it, by copying the array or, if the array is a ring whose start can be anywhere, by moving the start.

A burst is many updates arriving close together, as when one large order takes out several levels. A resync is the rebuild from a fresh snapshot after a gap, a missed update; a stale book is a copy that no longer matches the venue’s. Costs are set against the budget of 1 µs, 4,000 cycles at 4 GHz, and most turn on whether the cache line holding the data is in L1, the core’s nearest cache.

Read the table against the budget. The array rows are about a hundredth of a budget each: the common case is 0.2–0.5% of it, a cursor move with the bitmap 0.5–2%. A budget holds 200–500 of the common case, and the strategy barely notices the book. The Vec’s lookup is 2–6%. The tree rows and the Vec’s insert or delete are a tenth to a half: 100–500 ns. Those two tree rows are the map operation alone; the TreeBook built in this chapter also asks for its best price before and after each change, two walks of 30–100 ns, so its whole apply is 160–500 ns on an existing level and 210–700 ns on a new or emptied one, a sixth of a budget to most of one. The last four rows are not rungs, which every update pays, but additions that land on some updates and not others, each in its own unit: the burst in the queue it builds, the re-base in 50–150 budgets paid by one unlucky update, the resync in 70,000–200,000 budgets during which nothing the book says can be acted on, and the stale book not in time at all.

Direct and indirect cost

The direct cost is the apply itself, the instructions the table counts. The indirect cost is what the apply does to the cache, and the strategy pays it. A tree’s nodes lie wherever the allocator put them, and every new or emptied level also touches the allocator’s free lists, its records of which blocks are spare. Each of those lines enters L1 and evicts one already there, often the strategy’s code or data, so the strategy’s next pass misses where it used to hit, 4 ns to L2 and 10–40 ns to L3 a line. A dense array’s working set is the top few lines on each side, eight levels to a 64-byte line, and a word or two of bitmap: the same lines every time, which stay in L1 because they are always in use. The second indirect cost is the queue: updates are applied one at a time, so every one behind a slow apply waits, as the burst row shows, and the last of a burst is often the one that moved the top. None of this is particular to trading; any program with a tree on its hot path pays both bills.

Which rungs matter

The apply rows set the p50, the middle of the histogram, because most updates change a level away from the top and take the first rung: 2–5 ns on the array, 100–300 ns on the tree. The tail rows set the p99, the cost only one update in a hundred exceeds, and beyond: the 30th update of a burst is a p99, a re-base is a max. The twist is that the worst of this tail is not time but correctness. A resync is 70–200 ms in which the program must withdraw its orders from the market, and a stale book acted on loses money in a fill that shows in the profit and loss, not in any histogram. A program can make every timed rung a hundredth of a budget and still lose on the row it never timed.