Roaring bitmaps

Deep dive

How it works

In: a set of u32 values (or two sets, for a set operation) · Out: the set in compressed containers; operations return a new set or a cardinality · State: the bitmap itself: sorted 16-bit keys with one container each · Cost: contains O(log c + 12 steps); union/intersection O(n1 + n2) over containers

1. Top level: sorted arrays of 16-bit keys and pointers to containers (binary search, or direct index when dense).
2. Array container: sorted u16, up to 4,096 entries.
3. Bitmap container: 1,024 × u64 plus a cached cardinality.
4. Run container: sorted (start, length − 1) pairs of u16; chosen by run_optimize() when smaller.
5. Insert into a full array (4,097th value) converts it to a bitmap; operations whose result drops to ≤ 4,096 convert back.
6. Binary ops walk both key lists like a merge; matching keys combine their containers with the kernel for that pair of types.

value 0x0003_00A7  -> key 0x0003, low 0x00A7
keys:       [0x0000,        0x0003,          0x0100        ]
containers: [array(37 vals), bitmap(9000),   run[(0,65535)]]   full chunk = 4 bytes

Code

Array and bitmap containers with insert, contains and intersection (run containers omitted).

const ARRAY_MAX: usize = 4096; // 4096 u16 = 8 KB = bitmap size

pub enum Container { Array(Vec<u16>), Bitmap(Box<[u64; 1024]>, u32) } // bitmap + cardinality

fn bitmap_to_array(w: &[u64; 1024]) -> Vec<u16> {
    let mut out = Vec::new();
    for (k, &word) in w.iter().enumerate() {
        let mut x = word;
        while x != 0 { out.push((k * 64) as u16 + x.trailing_zeros() as u16); x &= x - 1; }
    }
    out
}

impl Container {
    fn len(&self) -> u32 { match self { Container::Array(a) => a.len() as u32, Container::Bitmap(_, c) => *c } }
    fn contains(&self, x: u16) -> bool {
        match self {
            Container::Array(a) => a.binary_search(&x).is_ok(),
            Container::Bitmap(b, _) => b[x as usize >> 6] >> (x & 63) & 1 == 1,
        }
    }
    fn insert(&mut self, x: u16) -> bool {
        match self {
            Container::Array(a) => match a.binary_search(&x) {
                Ok(_) => false,
                Err(i) if a.len() < ARRAY_MAX => { a.insert(i, x); true }
                Err(_) => { // array full: convert to bitmap
                    let mut b = Box::new([0u64; 1024]);
                    for &v in a.iter().chain([x].iter()) { b[v as usize >> 6] |= 1 << (v & 63); }
                    *self = Container::Bitmap(b, ARRAY_MAX as u32 + 1);
                    true
                }
            },
            Container::Bitmap(b, card) => {
                let (w, m) = (x as usize >> 6, 1u64 << (x & 63));
                if b[w] & m != 0 { return false; }
                b[w] |= m;
                *card += 1;
                true
            }
        }
    }
    fn and(&self, other: &Container) -> Container {
        use Container::*;
        match (self, other) {
            (Array(a), Array(b)) => { // merge; production code gallops when sizes differ a lot
                let (mut out, mut i, mut j) = (Vec::new(), 0, 0);
                while i < a.len() && j < b.len() {
                    if a[i] < b[j] { i += 1 } else if a[i] > b[j] { j += 1 } else { out.push(a[i]); i += 1; j += 1 }
                }
                Array(out)
            }
            (Array(a), o @ Bitmap(..)) | (o @ Bitmap(..), Array(a)) =>
                Array(a.iter().copied().filter(|&v| o.contains(v)).collect()),
            (Bitmap(a, _), Bitmap(b, _)) => {
                let mut w = Box::new([0u64; 1024]);
                let mut card = 0;
                for k in 0..1024 { w[k] = a[k] & b[k]; card += w[k].count_ones(); } // auto-vectorizes
                if card as usize <= ARRAY_MAX { Array(bitmap_to_array(&w)) } else { Bitmap(w, card) }
            }
        }
    }
}

#[derive(Default)]
pub struct Roaring { keys: Vec<u16>, containers: Vec<Container> } // sorted by key

impl Roaring {
    pub fn insert(&mut self, x: u32) -> bool {
        let (hi, lo) = ((x >> 16) as u16, x as u16);
        let i = self.keys.binary_search(&hi).unwrap_or_else(|i| {
            self.keys.insert(i, hi);
            self.containers.insert(i, Container::Array(Vec::new()));
            i
        });
        self.containers[i].insert(lo)
    }
    pub fn contains(&self, x: u32) -> bool {
        self.keys.binary_search(&((x >> 16) as u16)).map_or(false, |i| self.containers[i].contains(x as u16))
    }
    pub fn len(&self) -> u64 { self.containers.iter().map(|c| c.len() as u64).sum() }
    pub fn and(&self, other: &Roaring) -> Roaring {
        let (mut out, mut i, mut j) = (Roaring::default(), 0, 0);
        while i < self.keys.len() && j < other.keys.len() {
            if self.keys[i] < other.keys[j] { i += 1; continue; }
            if self.keys[i] > other.keys[j] { j += 1; continue; }
            let c = self.containers[i].and(&other.containers[j]);
            if c.len() > 0 { out.keys.push(self.keys[i]); out.containers.push(c); }
            i += 1;
            j += 1;
        }
        out
    }
}

Complexity and constants

• Memory: array 2 bytes/value; bitmap 8 KB per chunk (≥ 4,097 values, so ≤ 2 bytes/value and down to 1 bit/value when full); run 4 bytes/run; plus ~8-16 bytes per container of top-level overhead.
• contains: binary search over keys (L1-resident for < few thousand chunks) + binary search over ≤ 4,096 u16 (12 steps, within 8 KB) or one bit test.
• Bitmap∩bitmap: 1,024 ANDs + popcounts; with AVX2 that is 256 vector ops, order of 100 ns. Array∩array: SIMD intersection kernels compare 8×8 u16 blocks at a time; galloping when one side is 32×+ smaller.
• Cardinality is cached per bitmap container, so len() is O(containers).

Efficiency

• Cost: array container 2 bytes per value, bitmap container 8 KB per 65,536 values (1 bit per value when full), run container 4 bytes per run, plus about 8-16 bytes per container of top-level overhead. Bitmap AND is 1,024 ANDs plus popcounts, 256 vector ops with AVX2, order of 100 ns per container; array intersection compares 8x8 u16 blocks per SIMD step and gallops when one side is 32x+ smaller. Bound: compute on dense containers, cache misses on the top-level key search for sparse sets.
• Levers:
  • run_optimize() after bulk build — sorted, clustered IDs collapse to a few runs, down to 4 bytes per full chunk — time-ordered rows
  • lazy OR (lazy_or, fast_or) — skips cardinality recomputation across many unions — merging many bitmaps
  • cardinality-only ops (and_cardinality) — no result materialized — counting queries
  • frozen/mmap views — query without deserializing — read-only indexes
  • renumber rows densely — keeps IDs in the efficient 32-bit range with locality — any ID assignment you control
• Naive → standard → state of the art:
  • plain bitset over the universe · 1 bit per possible value, even when sparse
  • run-length word-aligned bitmaps (WAH, EWAH) · good for long runs, poor random access
  • Roaring containers with SIMD kernels · at most about 2 bytes per value, set operations in order of 100 ns per container pair

Implementation notes

• Call run_optimize() after bulk building: sorted, clustered IDs (time-ordered rows) often collapse to a few runs.
• Lazy operations: for unions of many bitmaps, OR into bitmaps without recomputing cardinality, then repair once at the end (CRoaring lazy_or, fast_or).
• In-place AND/OR avoid allocations; reuse a destination bitmap in hot loops.
• Frozen / portable serialization: the format can be memory-mapped and queried without deserializing (CRoaring "frozen" views, Java ImmutableRoaringBitmap).
• Cardinality-only ops (and_cardinality) skip materializing the result: faster for counting queries.
• 64-bit: Roaring64 (a map from high 32 bits to 32-bit Roaring) or ART-keyed variants; keep IDs dense (renumber rows) to stay in the efficient 32-bit range.

Pitfalls

• Random 32-bit hashes as IDs: no locality, mostly 1-2 values per chunk; the result is bigger than a plain sorted array.
• Iterating with contains instead of iterators or batch ops: thousands of times slower than container-level operations.
• Forgetting to convert bitmap results back to arrays (or the reverse) keeps memory high after deletes.
• Mixing serialization formats: the portable spec differs from some implementations' native formats (e.g., Java's RoaringBitmap.serialize vs 64-bit variants); test cross-language.
• Mutating a shared immutable/mapped bitmap: copy-on-write first.

Variants and alternatives

In production

Search: Apache Lucene (RoaringDocIdSet, filter caching), Elasticsearch/OpenSearch. Analytics databases: Apache Druid and Pinot bitmap indexes, ClickHouse (groupBitmap*, bitmap functions), Apache Doris and StarRocks BITMAP type, InfluxDB IOx. Big data and monitoring: Apache Spark, Netflix Atlas.

Implementations

Sources

• S. Chambi, D. Lemire, O. Kaser, R. Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience, 2016. paper · arXiv
• D. Lemire, G. Ssi-Yan-Kai, O. Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience, 2016. paper · arXiv
• D. Lemire et al., Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience, 2018. paper · arXiv · code
• RoaringBitmap, RoaringFormatSpec, github.com/RoaringBitmap/RoaringFormatSpec. spec