SmolBitmap

A space-efficient bitmap implementation with inline storage optimization for Rust.

Features

• Zero allocation for bitmaps up to 127 bits
• Automatic promotion to heap storage for larger bitmaps
• Rich API with all standard set operations
• Memory efficient - only 16 bytes for small bitmaps
• no_std support with alloc for embedded systems
• Optional serde support for serialization
• Excellent performance with inline storage optimization

Quick Start

Add to your Cargo.toml:

[dependencies]
smol_bitmap = "0.3.1"

Basic Operations

use smol_bitmap::SmolBitmap;

fn main() {
    let mut bitmap = SmolBitmap::new();

    // Set some bits
    bitmap.insert(5);
    bitmap.insert(10);
    bitmap.insert(100);

    // Check if bits are set
    assert!(bitmap.get(5));
    assert!(!bitmap.get(6));

    // Count set bits
    assert_eq!(bitmap.count_ones(), 3);

    // Iterate over set bits
    for bit in bitmap.iter() {
        println!("Bit {} is set", bit);
    }
}

Set Operations

use smol_bitmap::SmolBitmap;

fn main() {
    let mut a = SmolBitmap::new();
    a.insert(1);
    a.insert(2);
    a.insert(3);

    let mut b = SmolBitmap::new();
    b.insert(2);
    b.insert(3);
    b.insert(4);

    // Union: {1, 2, 3, 4}
    let union = a.union(&b);

    // Intersection: {2, 3}
    let intersection = a.intersection(&b);

    // Difference: {1}
    let difference = a.difference(&b);

    // Symmetric difference: {1, 4}
    let sym_diff = a.symmetric_difference(&b);
}

Advanced Features

use smol_bitmap::SmolBitmap;

fn main() {
    let mut bitmap = SmolBitmap::new();

    // Reserve capacity for 500 bits
    bitmap.reserve(500);

    // Bulk operations
    bitmap.extend([10, 20, 30, 40, 50]);

    // Retain only even indices
    bitmap.retain(|bit| bit % 2 == 0);

    // Find next/previous set bits
    assert_eq!(bitmap.next_set_bit(15), Some(20));
    assert_eq!(bitmap.prev_set_bit(35), Some(30));

    // Toggle bits
    bitmap.complement(25);

    // Create from iterator
    let from_iter: SmolBitmap = (0..10).step_by(2).collect();
}

Performance

SmolBitmap uses a hybrid storage strategy optimized for both small and large bitmaps:

Storage Layout

• Inline Storage (≤127 bits): Stored directly in 16 bytes, no heap allocation
• Heap Storage (>127 bits): Automatically promotes to Vec<u64> when needed

Benchmarks

Performance comparison with bitvec (lower is better):

¹ Time for N get operations
² Sparse bitmap iteration (every 10th bit set)

Key Advantages:

• Memory: 16 bytes for SmolBitmap vs 24+ bytes for BitVec
• Small bitmaps: Zero allocation for up to 127 bits
• Iteration: Word-skipping optimization provides consistent wins
• Cache locality: Better performance for small-to-medium bitmaps

Run benchmarks yourself:

cargo bench

When to Use

✅ Best when:

• You manage lots of small bitmaps (flags, sets, indexes)
• Most stay under 128 bits but a few grow larger
• Iteration speed and memory footprint matter

❌ Prefer alternatives when:

• All bitmaps are very large (>1000 bits) → bit-vec / bitvec
• You need fixed-size → fixedbitset
• You need compression → roaring

Examples

See the examples/ directory for more usage examples:

# Basic usage
cargo run --example basic

# Advanced features
cargo run --example advanced

Feature Flags

• std (default) - Use standard library (provides Error trait implementation)
• serde - Enable serialization/deserialization support

No-std Usage

SmolBitmap supports no_std environments with alloc:

[dependencies]
smol_bitmap = { version = "0.3.1", default-features = false }

This will disable the std feature but still requires an allocator for heap storage when bitmaps exceed inline capacity.

Safety

SmolBitmap uses unsafe code in a few performance-critical areas. All unsafe usage is:

• Carefully documented with safety invariants
• Minimal in scope
• Covered by tests
• Audited for correctness

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

License

This project is licensed under the MIT license.