Dense arrays and best-price bitmaps

The dense array indexed by price

The tree and the Vec search because they store only the prices that exist. A dense array, the data-structures chapter’s array indexed by a small integer, stores every price in a range, an empty level as zero, and never searches: prices are integers on a grid, counts of ticks, so the price is the index once the lowest price covered, the base, is subtracted. The quantity at price p lives in slot p − base, and that subtraction is the whole of the index arithmetic, since decode already turned $68,123.45 into 6,812,345 ticks.

At 8 bytes a slot, 65,536 levels take 512 KB a side and 1 MB for the book. With a base of 6,779,577 ($67,795.77), the bid at $68,123.45 is bids[32,768], and the cent below bids[32,767], the slot next to it. An update is a subtraction, a load, a compare and a store, on lines near the top that are nearly always in L1: 2–5 ns, 8–20 cycles.

The array does not know its best price, so the best-price cursor, the best level’s index, is kept beside it and moved in the three ways an update allows: out to a better price, not at all, or inward (for bids, to lower indices) to the next non-zero slot when the best empties. The walk costs about 1 ns a level in L1 and 4 ns per line beyond. Away from the top, a cent is far finer than the gaps between orders: a thousand bid levels spread over 32,768 ticks, half the array, average 32 empty levels apart, and if the top $50 of bids vanishes in a fast market the walk crosses 5,000 levels and 625 lines in microseconds, several budgets, just when the strategy needs the new best.

The bitmap that ends the walk

The data-structures chapter’s bitmap checks 64 levels at once: one bit per level, set while it holds a quantity, 64 to a u64. A 65,536-level side needs 1,024 words, 8 KB, kept in step by an OR when a level fills and an AND when it empties.

Finding the next occupied level is then a question about one word, answered by the bit-scan instructions, trailing_zeros and leading_zeros, in 1–3 cycles: for the next bid below level i, mask off the bits at and above i in its word and take the highest left, or move to the word below if none is, 64 levels a step instead of one. The two helpers that do it, next_set_bit_below and next_set_bit_above over &[u64], are the data-structures chapter’s, reused unchanged.

Word by word is still a walk: 1,024 words in the worst case on a 65,536-level side. The summary word of the data-structures chapter ends it: one bit per bitmap word, so a search within 4,096 levels reads at most three words, the start, the summary, and the word it names. A 65,536-level side has 16 summary words, two lines, and a third level of one word over them makes the worst case five. For one extra test when a word turns zero or non-zero, moving the cursor costs 5–20 ns (20–80 cycles) however far the next level is.

The whole ArrayBook, with one level of bitmap to keep it short:

const LEVELS: usize = 65_536;     // prices covered, in ticks

pub struct ArrayBook {
    base: Ticks,              // the price held at index 0
    bids: Vec<Lots>,          // bids[i]: quantity bid at price base + i
    asks: Vec<Lots>,          // asks[i]: quantity offered at price base + i
    bid_bits: Vec<u64>,       // bit i is set when bids[i] != 0
    ask_bits: Vec<u64>,       // bit i is set when asks[i] != 0
    best_bid: Option<usize>,  // index of the highest non-empty bid
    best_ask: Option<usize>,  // index of the lowest non-empty ask
}

impl ArrayBook {
    /// Every byte is allocated here, once; `apply` never allocates.
    pub fn new(base: Ticks) -> Self {
        ArrayBook {
            base,
            bids: vec![0; LEVELS], asks: vec![0; LEVELS],
            bid_bits: vec![0; LEVELS / 64], ask_bits: vec![0; LEVELS / 64],
            best_bid: None, best_ask: None,
        }
    }
}

impl Book for ArrayBook {
    fn apply(&mut self, u: &Update) -> bool {
        let offset = u.price - self.base;          // index arithmetic
        if offset < 0 || offset >= LEVELS as Ticks {
            return false;                          // outside the range: see below
        }
        let i = offset as usize;
        let (levels, bits, best) = match u.side {
            Side::Bid => (&mut self.bids, &mut self.bid_bits, &mut self.best_bid),
            Side::Ask => (&mut self.asks, &mut self.ask_bits, &mut self.best_ask),
        };
        if levels[i] == u.qty {
            return false;                          // nothing changed
        }
        levels[i] = u.qty;
        let (word, bit) = (i / 64, i % 64);        // where level i's bit lives
        if u.qty != 0 { bits[word] |= 1 << bit; } else { bits[word] &= !(1 << bit); }

        let better = |a: usize, b: usize| match u.side { Side::Bid => a > b, Side::Ask => a < b };
        match *best {
            Some(c) if i == c && u.qty == 0 => {   // the best emptied: walk inward
                *best = match u.side {
                    Side::Bid => next_set_bit_below(bits, c),
                    Side::Ask => next_set_bit_above(bits, c),
                };
                true
            }
            Some(c) if i == c => true,             // the best's quantity changed
            Some(c) if !better(i, c) => false,     // a deeper level: top untouched
            _ => { *best = Some(i); true }         // a new best, or the side's first level
        }
    }
    fn best_bid(&self) -> Option<(Ticks, Lots)> {
        self.best_bid.map(|i| (self.base + i as Ticks, self.bids[i]))
    }
    fn best_ask(&self) -> Option<(Ticks, Lots)> {
        self.best_ask.map(|i| (self.base + i as Ticks, self.asks[i]))
    }
}

A None cursor means an empty side, and the last arm runs only when the slot was empty before, so its new quantity cannot be zero. With the best bid at index 32,768 ($68,123.45) and the next at $68,123.42, a zero at the best clears bit 0 of word 512, finds nothing below it there, and takes word 511’s highest set bit, 61: index 32,765, $68,123.42, in two word reads.