The ordered-map book

6.5 Representing the book

Three ways to hold a thousand levels

One side of the book is a list of levels, prices each with the quantity waiting there, about a thousand on a busy crypto feed. Every delta (a side, a price and its new quantity) asks the structure holding it to find the level at a price, to write the new quantity (creating the level, or removing it at zero), and to keep the best price known, so that apply can say cheaply whether the top changed, which is all the strategy waits for.

Big-O, the textbook count of steps as the book grows, barely tells the three structures that follow apart. A tree, or a sorted array searched by halving, takes log n steps, ten at a thousand levels, and an array indexed by price takes one. What does is underneath each step: how many cache lines (the 64-byte blocks memory moves in) it touches and whether they are in L1, the nearest cache, how many branches the core cannot guess, at 15–20 cycles a wrong guess, and whether it calls the allocator, 20–50 ns and as much again to free. Counted that way, the three differ by a factor of fifty.

The ordered map: BTreeMap

A binary search tree, one key per node, is at least 10 levels deep for a thousand keys, and each level is a pointer chase to a heap node, each a possible miss to L2 (4 ns) or L3 (10–40 ns). A B-tree uses fat nodes instead. Each node holds a short sorted run of keys; an inner node also holds one more child pointer than it has keys, each child covering the range between two keys, and the nodes at the bottom, the leaves, hold none. Rust’s BTreeMap, the standard library’s sorted map, keeps 5 to 11 keys per node (fewer at the root, the top node), values beside them. A leaf of i64 pairs is 192 bytes, three lines; an inner node, with twelve child pointers, 288. A thousand keys fit in three levels. A lookup scans each node’s keys in turn (the documentation describes this linear search) to the first key not below the target, and follows the child pointer there: three pointer chases instead of ten.

Overwriting a key is a lookup and a store. A new key shifts the larger keys of its leaf along; a full leaf splits, allocating a node, moving half its keys there and the middle key up to the parent. A removal shifts keys back, and a leaf left with fewer than 5 borrows from a neighbour or merges with it, freeing a node. The best bid, the largest key, ends the rightmost leaf, three pointer chases down; BTreeMap::last_key_value walks there and first_key_value to the best ask, both stable since Rust 1.66.

use std::collections::BTreeMap;

#[derive(Default)]
pub struct TreeBook {
    bids: BTreeMap<Ticks, Lots>,
    asks: BTreeMap<Ticks, Lots>,
}

impl TreeBook {
    fn best(&self, side: Side) -> Option<(Ticks, Lots)> {
        let found = match side {
            Side::Bid => self.bids.last_key_value(),  // highest bid
            Side::Ask => self.asks.first_key_value(), // lowest ask
        };
        found.map(|(&p, &q)| (p, q))
    }
}

impl Book for TreeBook {
    fn apply(&mut self, u: &Update) -> bool {
        let before = self.best(u.side);
        let map = match u.side { Side::Bid => &mut self.bids, Side::Ask => &mut self.asks };
        if u.qty == 0 { map.remove(&u.price); } else { map.insert(u.price, u.qty); }
        self.best(u.side) != before
    }
    fn best_bid(&self) -> Option<(Ticks, Lots)> { self.best(Side::Bid) }
    fn best_ask(&self) -> Option<(Ticks, Lots)> { self.best(Side::Ask) }
}

apply compares the updated side’s best before and after; the other side cannot change. Two walks per update is wasteful on purpose, since the price alone shows whether the top could have moved. The map costs 100–300 ns (400–1,200 cycles) on an existing level and 150–500 ns on a new or emptied one, and each walk 30–100 ns more: a sixth of a budget to most of one. It is still the right first implementation: twenty lines, any price, plainly correct, and so the reference that the companion repository checks the other two against, update by update.