repository·main·Indexed 21 days ago
https://github.com/roaringbitmap/roaring-rsA high-performance Rust implementation of the Roaring bitmap data structure optimized for compressed bitset operations. It provides efficient set operations (Union, Intersection, Difference, XOR), container management with multiple storage formats (Array, Bitmap, Run), and detailed composition statistics. Includes an experimental SIMD feature requiring the Rust nightly toolchain.
simd feature is currently under active development and has not been fully tested. To use this feature, you must use a Rust nightly toolchain, as it relies on std::simd.Benchmarks are implemented using the Criterion library and are located in the ./benchmarks directory. They utilize real-world datasets to measure performance. For accurate results, it is recommended to run benchmarks on a bare-metal machine and compare the base branch against your contribution branch.
cargo benchTo maintain project standards, ensure you have the necessary components installed via rustup and run the following checks before submitting changes:
rustup component add clippy rustfmtcargo fmt -- --checkcargo clippy --all-targets -- -D warningscargo testrustup component add clippy rustfmt
cargo fmt -- --check
cargo clippy --all-targets -- -D warnings
cargo testA RoaringTreemap is a compressed bitmap structure designed to map u32 keys to u64 values. It is implemented as a BTreeMap where each key is a u32 and the associated value is a RoaringBitmap. This allows for efficient storage and querying of sparse sets of values associated with specific integer keys.
use roaring::RoaringTreemap;
let mut rb = RoaringTreemap::new();
// insert all primes less than 10
rb.insert(2);
rb.insert(3);
rb.insert(5);
rb.insert(7);
println!("total bits set to true: {}", rb.len());The BinaryOperationVisitor trait allows you to define custom logic for processing elements during bitmap operations. This pattern separates the traversal algorithm (which handles the complexity of SIMD or scalar iteration) from the actual operation performed on the data.
By implementing this trait, you can perform tasks like collecting results into a collection or calculating statistics (like cardinality) without needing to materialize a new bitmap intermediate.
Methods to implement:
visit_vector(&mut self, value: core::simd::u16x8, mask: u8): Called when a SIMD vector is processed. The mask indicates which elements in the vector are valid.visit_scalar(&mut self, value: u16): Called for individual scalar values.visit_slice(&mut self, values: &[u16]): Called when a contiguous slice of values is available.impl BinaryOperationVisitor for MyCustomVisitor {
#[cfg(feature = "simd")]
fn visit_vector(&mut self, value: core::simd::u16x8, mask: u8) {
// Handle SIMD vector with mask
}
fn visit_scalar(&mut self, value: u16) {
// Handle scalar
}
fn visit_slice(&mut self, values: &[u16]) {
// Handle slice
}
}The VecWriter struct is a built-in implementation of BinaryOperationVisitor that collects the results of a binary operation into a Vec<u16>.
Use VecWriter::new(capacity) to initialize it with a pre-allocated capacity, and call into_inner() to retrieve the final Vec<u16> after the operation is complete.
let mut writer = VecWriter::new(1024);
// ... perform operation using writer ...
let results: Vec<u16> = writer.into_inner();The CardinalityCounter struct is a built-in implementation of BinaryOperationVisitor used to count the number of elements produced by an operation.
Initialize it with CardinalityCounter::new() and retrieve the total count using into_inner(), which returns the count as a u64.
let mut counter = CardinalityCounter::new();
// ... perform operation using counter ...
let count: u64 = counter.into_inner();To efficiently clear bits from the boundaries of the set, use:
remove_smallest(n): Removes the $n$ smallest set bits.remove_biggest(n): Removes the $n$ largest set bits.If $n$ is greater than or equal to the current cardinality, the entire store is cleared.
Use RoaringTreemap::from_bitmaps to create a new treemap from an iterator of (u32, RoaringBitmap) pairs. Note that if the iterator contains repeated partition numbers, the later partitions will replace the previous ones.
use roaring::RoaringTreemap;
use core::iter::FromIterator;
let original = (0..6000).collect::<RoaringTreemap>();
let clone = RoaringTreemap::from_bitmaps(original.bitmaps().map(|(p, b)| (p, b.clone())));
assert_eq!(clone, original);Containers support standard bitwise set operations via operator overloading:
BitOr / | / |=): Combines bits from two containers.BitAnd / & / &=): Keeps only bits present in both containers.Sub / - / -=): Removes bits of the second container from the first.BitXor / ^ / ^=): Keeps bits present in one container but not both.You can also check relationships without creating new containers:
is_disjoint(&other): Returns true if the containers share no bits.is_subset(&other): Returns true if all bits in this container are also in other.intersection_len(&other): Returns the number of bits shared by both containers.let mut c1 = Container::new(1);
let c2 = Container::new(1);
c1.insert(10);
c1.insert(20);
c2.insert(20);
c2.insert(30);
// Intersection
let intersection = &c1 & &c2; // Contains only {20}
// Union
let union = &c1 | &c2; // Contains {10, 20, 30}
// Difference
let diff = &c1 - &c2; // Contains {10}
// Check subset
let is_sub = c1.is_subset(&union);Use insert(index) to set a specific bit, or insert_range(range) to set all bits within a RangeInclusive<u16>. To remove bits, use remove(index) or remove_range(range). The insert_range and remove_range methods return the number of bits that were actually changed (newly set or newly removed).
use std::ops::core::ops::RangeInclusive;
let mut store = BitmapStore::new();
// Insert a single bit
store.insert(42);
// Insert a range of bits and get the count of newly set bits
let newly_set = store.insert_range(10..=20);
// Remove a single bit
store.remove(42);
// Remove a range of bits and get the count of bits removed
let removed_count = store.remove_range(10..=20);