Expand description
64-bit roaring-style compressed bitmap.
Provides a memory-efficient representation for sets of 64-bit integers using run-length encoding and adaptive container types. This implementation partitions integers into chunks of 2^16 values using the high 48 bits as the chunk key, with each chunk stored in one of three container types optimized for different data densities.
§Architecture
Each 64-bit value is split into a high 48-bit key (selecting a container) and a low 16-bit index (stored within that container):
64-bit value
+-----------------------------------------------+---------------+
| high 48 bits (key) | low 16 bits |
+-----------------------------------------------+---------------+
| |
v v
BTreeMap key Container indexThe bitmap stores containers in a sorted map, where each container holds
values in the range [key * 2^16, (key + 1) * 2^16):
Bitmap
+------------------------------------------------------------------+
| BTreeMap<u64, Container> |
+------------------------------------------------------------------+
| Key 0 | Key 1 | Key 2 | ... |
| [0, 65535] | [65536, 131071]| [131072, ...] | |
+-----------------+-----------------+-----------------+------------+
| | |
v v v
+--------------+ +--------------+ +--------------+
| Array | | Bitmap | | Run |
| [3, 7, 42, | | 1011010... | | [(0, 4095), |
| 100, 8000] | | (8KB bits) | | (8200, ..)] |
+--------------+ +--------------+ +--------------+
Sparse data Dense data Few runs
(<= 4096 vals) (many runs) (any density)§Container Types
| Type | Use Case | Storage |
|---|---|---|
| Array | Sparse data | Sorted Vec<u16> |
| Bitmap | Dense data with many disjoint runs | [u64; 1024] (8 KB) |
| Run | Data with few maximal runs (any density) | Sorted Vec<(u16, u16)> |
Containers automatically convert between variants on each insert /
insert_range to maintain a compact representation. The Bitmap→Run
transition uses a hysteresis band on the bitmap’s run count, so a container
that hovers near break-even doesn’t thrash between variants. See the container module
for the full transition table and threshold values.
Array --[> 4096 values]--> Bitmap <--[run-count threshold]--> Run§References
- https://arxiv.org/pdf/1402.6407: Better bitmap performance with Roaring bitmaps
- https://github.com/RoaringBitmap/RoaringFormatSpec: Roaring Bitmap Format Specification
- https://github.com/RoaringBitmap/roaring-rs: roaring-rs Crate