Finding work with bitmaps

5.5 Finding the next one: bitmaps

A hot loop asks two kinds of question. “What is the value for this one?” an array indexed by a small id answers in one load. “Which ones?” is different: which instruments have an order out, which slots of a pool are free, which instruments a batch of updates has changed. A bitmap answers it for 64 things at once.

A bitmap is one bit per thing, 1 for yes and 0 for no, packed into words. A word is the unit a core’s registers and arithmetic work on, 64 bits on current cores, a u64 in Rust, one instruction acting on all 64 bits. Thing i is bit i % 64 of word i / 64, an AND with 63 and a shift right by 6, since 64 is a power of two. Set bit b with OR, w |= 1 << b; clear it with AND NOT, w &= !(1 << b); test it with a shift and an AND, (w >> b) & 1.

Three more operations make it worth having. count_ones counts the set bits. trailing_zeros counts the zeros below the lowest set bit, which is that bit’s index: 5 for 0b1010_0000. leading_zeros counts the zeros above the highest set bit, which is therefore bit 63 minus the count: 56 here, so bit 7. On a zero word the last two return 64. On x86-64 each is a single instruction, popcnt, tzcnt and lzcnt, of 1–3 cycles whatever the word holds, and using the last two to find a set bit is a bit-scan.

A search for the next set bit above or below i masks i’s word to keep only the bits on the wanted side and takes trailing_zeros going up or leading_zeros going down; if nothing is left, it takes the next word that way whole until one is non-zero or the bitmap ends.

/// The lowest set bit strictly above `i`, or `None`; `i` must be below `bits.len() * 64`.
pub fn next_set_bit_above(bits: &[u64], i: usize) -> Option<usize> {
    let mut w = i / 64;
    let mut word = bits[w] & ((u64::MAX << (i % 64)) << 1); // bits above i; 0 at bit 63
    loop {
        if word != 0 {
            return Some(w * 64 + word.trailing_zeros() as usize);
        }
        w += 1;
        if w == bits.len() { return None; }                  // ran off the top
        word = bits[w];
    }
}

/// The highest set bit strictly below `i`, or `None`.
pub fn next_set_bit_below(bits: &[u64], i: usize) -> Option<usize> {
    let mut w = i / 64;
    let mut word = bits[w] & ((1u64 << (i % 64)) - 1);      // bits below i; 0 at bit 0
    loop {
        if word != 0 {
            return Some(w * 64 + 63 - word.leading_zeros() as usize);
        }
        if w == 0 { return None; }                           // ran off the bottom
        w -= 1;
        word = bits[w];
    }
}

The mask above i shifts left by i % 64 and then by one more, never by i % 64 + 1 at once: at bit 63 that would be a shift by 64, which panics in a debug build and in a release build shifts by zero, so that i passes its own mask and comes back as the next set bit after itself. The mask below i is likewise 0 at bit 0. Each empty word costs a load and a test, either end returns None, and the bounds check on bits[w] enforces that i lies inside the bitmap.

Word by word is still a walk, if one 64 times shorter: a 65,536-thing bitmap is 1,024 words. A summary word ends it: a bitmap over the bitmap, bit w set while word w is non-zero, so one summary word covers 64 words and 4,096 things. A search whose own word is empty bit-scans the masked summary word to find the next non-empty word, then bit-scans that: three words read, however far the answer. The upkeep is one more test on each set and clear, when a word becomes or stops being zero. Linux’s O(1) scheduler kept such a bitmap of its 140 priority levels and found the most urgent runnable task with one find-first-set instruction, a bit-scan from bit 0.

The first of three uses is orders in flight: an order is pending from its send until the venue acknowledges it, and meanwhile the strategy must not send another for that instrument, must count those in flight, and must check each on a timer for an overdue acknowledgement. With InstrumentIds 0 to 63 assigned at startup, that is one u64:

/// Bit i: instrument i has an order sent and not yet acknowledged.
#[derive(Default)]
pub struct Pending(u64);

impl Pending {
    pub fn set(&mut self, id: InstrumentId) { self.0 |= 1u64 << id; }      // on send
    pub fn clear(&mut self, id: InstrumentId) { self.0 &= !(1u64 << id); } // on ack
    pub fn is_set(&self, id: InstrumentId) -> bool { (self.0 >> id) & 1 == 1 }
    pub fn count(&self) -> u32 { self.0.count_ones() }

    pub fn for_each(&self, mut f: impl FnMut(InstrumentId)) {
        let mut w = self.0;                        // a copy
        while w != 0 {
            f(w.trailing_zeros());                 // the index of the lowest set bit
            w &= w - 1;                            // clear that bit
        }
    }
}

for_each visits only the pending instruments: trailing_zeros names the lowest set bit and w &= w - 1 clears it, since subtracting 1 turns that bit to 0 and the zeros below it to 1s. The shift 1u64 << id needs id below 64, which holds for ids assigned at startup rather than read off the wire.

The second use replaces both a pool’s stack of free slot indices and its flags with one bit per slot, set while the slot is free: 512 bytes for 4,096 slots against 16 KB of u32 indices and 4 KB of flags. alloc takes trailing_zeros of the word a summary word names and clears the bit, and free sets it. The bit is the membership test the stack needs its flags for: a slot freed twice finds its bit already set. The stack hands out the slot freed last, whose line is likely still cached; the bitmap the lowest free one, keeping the slots in use in fewer lines. The third use is the order-book chapter’s: a bit per price level, so that the next occupied price is found 64 levels at a time.

The alternative is a [bool; 64] and a loop that tests the flags in turn. Its cost depends on the data twice: it reads every flag before the next set one, about 1 ns per 8 bytes in L1, and it exits on a branch on the flag. A core does not wait for a branch’s condition; it guesses, runs ahead, and on a wrong guess throws the work away, 15–20 cycles. With few flags set it guesses “not set”, so the scan pays at exactly the flag it wanted. The bit-scan is branch-free, the same mask and tzcnt whatever the data, with nothing to guess: 1–3 cycles whether the next set bit is one place away or 63. Only the exit of a loop over set bits, such as for_each’s, depends on the data: one guess a pass, not one per thing found.