Bit-Vector and Bit-Set Optimization

Mastering High-Cardinality Booleans with Bit-Vectors

In this lesson, you will learn how to represent thousands of boolean states using minimal memory by packing individual flags into dense bit-vectors.

The Memory Problem

When tracking a large number of independent boolean flags (e.g., "Is user ID 45,002 active?"), a standard Vec<bool> is inefficient. In Rust, a bool consumes one full byte of memory to remain addressable. If you need to track one million items, a Vec<bool> requires 1MB of heap allocation. By contrast, a bit-vector stores each boolean as a single bit, reducing the footprint to roughly 125KB—an 8x memory reduction.

The Core Idea: Bit-Packing

To represent these states, we use a Vec<u64>. Each element in the vector acts as a "bucket" containing 64 individual flags. To access the state of index i, we use two operations:

1. Division (i / 64): Identifies which u64 block holds the flag.
2. Modulo (i % 64): Identifies the specific bit position within that block.

By applying bitwise operators, we can interact with these states without heap-allocating per item:

struct BitVector {
    bits: Vec<u64>,
}

impl BitVector {
    fn set(&mut self, i: usize) {
        let bucket = i / 64;
        let offset = i % 64;
        self.bits[bucket] |= 1 << offset;
    }

    fn get(&self, i: usize) -> bool {
        let bucket = i / 64;
        let offset = i % 64;
        (self.bits[bucket] & (1 << offset)) != 0
    }
}

Leveraging Iterator Pipelines

When combined with your knowledge of iterator pipelines, bit-vectors become powerful. You can perform set intersections or unions across high-cardinality sets by performing bitwise AND or OR operations directly on the underlying u64 slices. This maps perfectly to vectorized hardware instructions (SIMD), allowing you to process 64 boolean states in a single CPU cycle. Instead of iterating over 64 individual booleans, you process a single machine word, drastically reducing memory pressure and improving cache locality during bulk analysis.

Key Takeaway: Use bit-vector packing to compress high-cardinality boolean states into single bits, enabling 8x memory savings and efficient SIMD-friendly bulk operations.