Rank/select bitvectors

Deep dive

How it works

In: a bitvector and a position i (rank) or an index k (select) · Out: ones before i, or the position of the k-th one · State: the bits plus count tables (3-25 % extra) and select hints · Cost: rank O(1), 1-2 cache misses; select a few binary-search steps rank9 (Vigna):

1. Split the bits into 512-bit blocks of 8 words. Per block store abs = ones before the block (64 bits) and rel = ones before words 1..7 inside the block, 7 × 9 bits packed in one more u64. Both counts sit side by side: one cache line for the counts, one for the word.
2. rank1(p) = abs[b] + rel[b][w] + popcount(word & mask_below(p)). Word 0 has relative count 0; a wraparound trick reads bit 63, which is always 0, instead of branching.

select (sampled):

1. While building, record the block that contains every 8192-th one (and every 8192-th zero).
2. select1(k): binary search abs between the hints around k, then scan the 7 relative counts, then find the r-th set bit inside the word.

Elias-Fano for sorted v₀ ≤ v₁ ≤ … < u:

1. l = ⌊log₂(u/n)⌋. Store the low l bits of each value packed: n·l bits.
2. High parts vᵢ >> l go into a bitvector, unary-coded by setting bit (vᵢ >> l) + i: at most 2n bits.
3. get(i) = (select1(i) − i) << l | low(i). lower_bound(x): select0 jumps to the start of bucket x >> l, then scan the few values in it.

values 3 4 7 13 14 15 21 43, u = 64, n = 8 → l = 3
high = v >> 3: 0 0 0 1 1 1 2 5      unary: 1110 1110 10 0 0 10   (1 = value, 0 = next bucket)
low  = v & 7 : 3 4 7 5 6 7 5 3      get(4): select1(4) = 5, 5 − 4 = 1 → 1 << 3 | 6 = 14

Code

/// Bitvector with rank9 (Vigna 2008): per 512-bit block one absolute count (u64) and
/// seven 9-bit in-block prefix counts packed in a second u64. 25 % extra space.
/// Select hints: the block holding every HINT-th one / zero (about 0.4 % extra).
pub struct BitVec { pub words: Vec<u64>, counts: Vec<u64>, pub ones: u64, hints: [Vec<u32>; 2] }
const HINT: u64 = 8192;

impl BitVec {
    pub fn new(words: Vec<u64>) -> BitVec {
        let blocks = words.len().div_ceil(8);
        let (mut counts, mut total) = (Vec::with_capacity(2 * blocks + 2), 0u64);
        for b in 0..blocks {
            counts.push(total);
            let (mut packed, mut inblock) = (0u64, 0u64);
            for j in 0..8 {
                if j > 0 { packed |= inblock << (9 * (j - 1)); } // prefix count before word j
                inblock += words.get(8 * b + j).map_or(0, |w| w.count_ones() as u64);
            }
            counts.push(packed);
            total += inblock;
        }
        counts.push(total); counts.push(0);                    // sentinel block
        let mut hints = [Vec::new(), Vec::new()];               // [ones, zeros]
        for b in 0..blocks {
            let ends = [counts[2 * b + 2], 512 * (b as u64 + 1) - counts[2 * b + 2]];
            for z in 0..2 { while (hints[z].len() as u64) * HINT < ends[z] { hints[z].push(b as u32) } }
        }
        BitVec { words, counts, ones: total, hints }
    }
    /// Number of ones in positions [0, pos). pos <= 64 * words.len().
    #[inline] pub fn rank1(&self, pos: u64) -> u64 {
        let (w, b) = ((pos / 64) as usize, (pos / 512) as usize);
        let t = (w % 8).wrapping_sub(1) as u64;           // word 0: t = 2^64-1, wraps to 7,
        let sub = (self.counts[2 * b + 1] >> (t.wrapping_add(t >> 60 & 8) * 9)) & 0x1FF; // bit 63 = 0
        let tail = if pos % 64 == 0 { 0 } else { (self.words[w] << (64 - pos % 64)).count_ones() };
        self.counts[2 * b] + sub + tail as u64
    }
    /// Position of the k-th one / zero (k from 0, k < count).
    pub fn select1(&self, k: u64) -> u64 { self.select(k, false) }
    pub fn select0(&self, k: u64) -> u64 { self.select(k, true) }

    fn select(&self, k: u64, zero: bool) -> u64 {
        let before = |b: usize| { let ones = self.counts[2 * b];
            if zero { 512 * b as u64 - ones } else { ones } };
        // binary search for the last block with before(b) <= k, inside one hint gap
        let h = &self.hints[zero as usize];
        let mut lo = h[(k / HINT) as usize] as usize;
        let mut hi = h.get((k / HINT) as usize + 1).map_or(self.counts.len() / 2 - 1, |&b| b as usize + 1);
        while hi - lo > 1 { let mid = (lo + hi) / 2; if before(mid) <= k { lo = mid } else { hi = mid } }
        let mut r = k - before(lo);
        let packed = self.counts[2 * lo + 1];
        let mut j = 0;                                    // word within block (linear: 7 compares)
        while j < 7 {
            let ones_before = (packed >> (9 * j)) & 0x1FF; // prefix before word j+1
            let c = if zero { 64 * (j as u64 + 1) - ones_before } else { ones_before };
            if c > r { break; }
            j += 1;
        }
        if j > 0 { let ob = (packed >> (9 * (j - 1))) & 0x1FF; r -= if zero { 64 * j as u64 - ob } else { ob }; }
        let w = self.words[8 * lo + j];
        (8 * lo + j) as u64 * 64 + select_in_word(if zero { !w } else { w }, r as u32) as u64
    }
}

/// Position of the k-th set bit of w. BMI2: one pdep (slow microcode on AMD Zen 1/2).
#[cfg(all(target_arch = "x86_64", target_feature = "bmi2"))]
#[inline] fn select_in_word(w: u64, k: u32) -> u32 {
    unsafe { core::arch::x86_64::_pdep_u64(1u64 << k, w).trailing_zeros() }
}
#[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
#[inline] fn select_in_word(mut w: u64, mut k: u32) -> u32 {
    let mut shift = 0;
    loop {                                                // find the byte, then the bit
        let c = (w as u8).count_ones();
        if k < c { break; } k -= c; w >>= 8; shift += 8;
    }
    let mut b = w as u8;
    for _ in 0..k { b &= b - 1; }                         // clear the k lowest ones
    shift + b.trailing_zeros()
}

/// Elias-Fano: n sorted values < u in n * (2 + ceil(log2(u/n))) bits.
/// Low l bits packed; high parts in unary: value i sets bit (v >> l) + i.
pub struct EliasFano { l: u32, low: Vec<u64>, high: BitVec, n: usize }

impl EliasFano {
    pub fn new(vals: &[u64], u: u64) -> EliasFano {
        let n = vals.len();
        let l = if n == 0 || u <= n as u64 { 0 } else { 63 - (u / n as u64).leading_zeros() };
        let mut low = vec![0u64; (n * l as usize).div_ceil(64) + 1];
        let mut high = vec![0u64; (n + (u >> l) as usize + 1).div_ceil(64)];
        for (i, &v) in vals.iter().enumerate() {
            if l > 0 {
                let (pos, lv) = (i * l as usize, v & ((1u64 << l) - 1));
                low[pos / 64] |= lv << (pos % 64);
                if pos % 64 + l as usize > 64 { low[pos / 64 + 1] |= lv >> (64 - pos % 64); }
            }
            let h = (v >> l) as usize + i;
            high[h / 64] |= 1u64 << (h % 64);
        }
        EliasFano { l, low, high: BitVec::new(high), n }
    }
    #[inline] fn low_bits(&self, i: usize) -> u64 {
        if self.l == 0 { return 0; }
        let pos = i * self.l as usize;
        let two = self.low[pos / 64] as u128 | (self.low[pos / 64 + 1] as u128) << 64;
        (two >> (pos % 64)) as u64 & ((1u64 << self.l) - 1)
    }
    /// The i-th value: one select1 on the high bits plus one unaligned read.
    pub fn get(&self, i: usize) -> u64 {
        (self.high.select1(i as u64) - i as u64) << self.l | self.low_bits(i)
    }
    /// Index of the first value >= x (n if none): select0 jumps to bucket x >> l.
    pub fn lower_bound(&self, x: u64) -> usize {
        let hb = x >> self.l;
        let mut i = if hb == 0 { 0 } else { (self.high.select0(hb - 1) + 1 - hb) as usize };
        while i < self.n && self.get(i) < x { i += 1; }  // scan within one bucket (~1-2 values)
        i
    }
}

Checked against a naive scan for rank, select1 and select0 on every position of random, sparse, dense, all-zero and all-one vectors, and Elias-Fano get/lower_bound against partition_point. On a 128 MB random bitvector (Apple M-series, independent random queries): rank order of 10 ns, select order of 150 ns. The x86 BMI2 path type-checks.

Complexity and constants

• rank9: two reads, one of them in the 16-byte count pair and one in the data word, plus a popcount; order of 1-2 cache misses on large vectors, a few ns when cached.
• select: the hint gap holds 8192 ones, which is about 32 blocks for a half-full vector: about 5 binary-search steps, each a likely cache miss on large vectors. Denser hints (every 1024-2048 ones) or a second hint level (sdsl select_support_mcl, Vigna's select9/simple_select) cut it to 1-2 misses at a few percent more space.
• Space: rank9 25 %, hints 32 bits per 8192 ones or zeros (about 0.4 %). Poppy (3.125 %) packs, per 2048 bits, one 32-bit cumulative count and three 10-bit counts of its 512-bit sub-blocks into one u64, plus a 64-bit count per 2³² bits.
• Elias-Fano: within 2 bits per value of the information-theoretic minimum ⌈log₂ C(u, n)⌉; plus the select structure on the high bits. Random access is one select plus one unaligned read; sequential decoding walks the high bits with tzcnt, order of a few cycles per value.

Efficiency

• Cost: rank is one count read plus one data word plus a popcount: a few ns cached, 1-2 cache misses on large vectors. Select costs about 5 binary-search steps (likely misses) with 8192-one hints. Extra space is 25 % (rank9) or 3.125 % (Poppy). Bound: memory latency; the popcount is cheap with popcnt.
• Levers:
  • interleave counts and data in one cache line — one miss instead of two (Vigna 2008) — random queries
  • Poppy layout — 3.125 % instead of 25 % space at one or two misses (Zhou et al. 2013) — memory-tight indexes
  • denser or two-level select hints — 1-2 misses instead of about 5, a few percent more space (sdsl, Sux) — select-heavy workloads
  • pdep + tzcnt inside the word — select in a word in a few cycles (not on Zen 1/2, where pdep is slow) — BMI2 hardware
  • scan from the current position for next_geq — avoids select0 jumps when targets are close — posting-list intersection
• Naive → standard → state of the art:
  • count bits from the start · O(n) per rank
  • rank9 plus sampled select · O(1) rank, 25 % space
  • Poppy / interleaved layout with two-level select hints · 3-6 % space, 1-2 misses

Implementation notes

• Popcount: u64::count_ones compiles to popcnt only when the target has it. Build with -C target-cpu=x86-64-v2 or later, or the compiler emits a bit-twiddling fallback. AArch64 uses NEON cnt + addv.
• pdep: _pdep_u64(1 << k, w).trailing_zeros() is the k-th set bit. On AMD Zen 1 and Zen 2, pdep is microcoded and slow (data-dependent, up to hundreds of cycles); Zen 3 and Intel since Haswell run it in about 3 cycles. Dispatch at runtime or use the byte-wise fallback.
• Interleave count and data (one cache line per block holding counts + words) when queries are random: one miss instead of two.
• Elias-Fano parameters: l = ⌊log₂(u/n)⌋ minimises space. Store u as last + 1 to keep l small. For posting lists, split into chunks, each stored as EF, as a bitmap when dense, or implicitly when it is a full range; partitioned Elias-Fano picks the chunk boundaries that minimise space.
• Skip pointers for next_geq: lower_bound above jumps with select0; a scan from the current position (next_geq after the last result) is cheaper when targets are close.
• Bit order: bit i of the vector is bit i % 64 of word i / 64 (LSB-first). Mixing in MSB-first data breaks every popcount mask.

Pitfalls

• Rank tables with relative counts that overflow: 9 bits hold up to 511, enough for 7 words (448 bits). Bigger blocks need wider fields.
• Debug-build overflow in the wraparound trick: t + 8 with t = 2⁶⁴ − 1 panics in Rust debug; use wrapping_add (as in the code).
• select0 over a padded last word counts padding zeros; keep the real length and reject k beyond it.
• Elias-Fano for non-monotone data: it only stores sorted sequences. Store prefix sums of gaps instead (e.g. document lengths → offsets).
• Binary search over counts without hints on a 10⁹-bit vector: about 20 cache misses per select.

Variants and alternatives

In production

• Search engines: Lucene (EliasFanoDocIdSet), folly (folly/compression/elias_fano/EliasFanoCoding.h, posting lists at Facebook).
• Graphs and web data: Sux and Sux4J (Rank9, SimpleSelect, Elias-Fano lists, used in Vigna's WebGraph).
• Libraries for succinct trees and text indexes (wavelet trees, FM-indexes in genomics tools): sdsl-lite (rank_support_v, select_support_mcl, sd_vector), the Rust sucds crate.

Implementations

Sources

• Guy Jacobson, Space-efficient Static Trees and Graphs, FOCS 1989. paper
• David Clark, Compact Pat Trees, PhD thesis, University of Waterloo, 1996.
• Sebastiano Vigna, Broadword Implementation of Rank/Select Queries, WEA 2008. paper
• Dong Zhou, David G. Andersen, Michael Kaminsky, Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences, SEA 2013.
• Peter Elias, Efficient Storage and Retrieval by Content and Address of Static Files, JACM, 1974. paper
• Robert M. Fano, On the Number of Bits Required to Implement an Associative Memory, MIT Project MAC Memorandum 61, 1971.
• Daisuke Okanohara, Kunihiko Sadakane, Practical Entropy-Compressed Rank/Select Dictionary, ALENEX 2007. paper
• Sebastiano Vigna, Quasi-Succinct Indices, WSDM 2013. paper
• Giuseppe Ottaviano, Rossano Venturini, Partitioned Elias-Fano Indexes, SIGIR 2014. paper
• Gonzalo Navarro, Compact Data Structures, Cambridge University Press, 2016.