The sorted-vector book

The sorted Vec

The sorted Vec removes the scattering: each side is one Vec<(Ticks, Lots)> sorted by price, 16 bytes a pair, so a thousand levels are 16 KB in 250 consecutive lines that the prefetcher (the part of the core that spots a sequential walk and fetches ahead) can stream. Bids are stored highest first and asks lowest first, so the best is element 0, and reading it takes 1 ns.

Binary search finds a price: look at the middle element, keep the half the price belongs in, repeat. Each compare halves the range, so a thousand levels come down to one in 10 compares (2¹⁰ = 1,024). binary_search_by returns Ok(i) when it finds the target at i, or Err(i), the position that would keep the order. The time is in the branches: the core guesses each direction and loses 15–20 cycles per wrong guess, and a direction as random as the market is guessed wrong about half the time, 75–100 cycles in ten compares. With early probes on distant lines, that makes 20–60 ns (80–240 cycles).

An existing level is overwritten. A new level goes in at i, every later pair moving one slot along, and an emptied one is removed, every later pair moving back. That move is a memmove: a copy of a contiguous block of bytes to a place that overlaps its source, named after the C function that, unlike memcpy, allows the overlap. Even at tens of GB/s, moving 500 pairs, 8 KB, for a level in the middle of a thousand takes 100–300 ns (400–1,200 cycles). Vec::insert and Vec::remove do the move, and allocate only when the Vec is full, which one made with Vec::with_capacity never is.

#[derive(Default)]
pub struct VecBook {
    bids: Vec<(Ticks, Lots)>, // descending: the highest bid at index 0
    asks: Vec<(Ticks, Lots)>, // ascending: the lowest ask at index 0
}

impl Book for VecBook {
    fn apply(&mut self, u: &Update) -> bool {
        let levels = match u.side { Side::Bid => &mut self.bids, Side::Ask => &mut self.asks };
        let before = levels.first().copied();
        let found = levels.binary_search_by(|&(p, _)| match u.side {
            Side::Bid => u.price.cmp(&p), // descending order
            Side::Ask => p.cmp(&u.price), // ascending order
        });
        match (found, u.qty) {
            (Ok(i), 0) => { levels.remove(i); }           // level gone: close the gap
            (Ok(i), q) => levels[i].1 = q,                 // level exists: overwrite
            (Err(_), 0) => {}                              // removing a level we never had
            (Err(i), q) => levels.insert(i, (u.price, q)), // new level: open a gap
        }
        levels.first().copied() != before
    }
    fn best_bid(&self) -> Option<(Ticks, Lots)> { self.bids.first().copied() }
    fn best_ask(&self) -> Option<(Ticks, Lots)> { self.asks.first().copied() }
}

The sorted Vec wins on shallow books: up to about 64 levels a side is a kilobyte in L1, where a plain scan from index 0, its branch predictable and its loads prefetched, beats binary search. It loses on deep books, most where the activity is: with the best at index 0, a level created or emptied near the top moves nearly all 16 KB.