Crate hi_sparse_bitset

Hierarchical sparse bitset.

Memory consumption does not depends on max index inserted.

The very structure of BitSet acts as acceleration structure for intersection operation. All operations are incredibly fast - see benchmarks. (insert/contains in “traditional bitset” ballpark, intersection/union - orders of magnitude faster)

It is multi-level structure. Last level contains actual bit-data. Each previous level have bitmask, where each bit corresponds to !is_empty of bitblock in next level.

In addition to “non-empty-marker” bitmasks, there is pointers(indices) to non-empty blocks in next level. In this way, only blocks with actual data allocated.

For inter-bitset operations, for example intersection:

• root level bitmasks AND-ed.
• resulting bitmask traversed for bits with 1.
• indexes of bits with 1, used for getting pointers to the next level for each bitset.
• repeat for next level until the data level, then for each next 1 bit in each level.

Bitmasks allow to cutoff empty tree/hierarchy branches early for intersection operation, and traverse only actual data during iteration.

In addition to this, during the inter-bitset operation, level1 blocks of bitsets are cached for faster access. Empty blocks are skipped and not added to the cache container, which algorithmically speeds up bitblock computations at the data level. This has observable effect in a merge operation between N non-intersecting bitsets: without this optimization - the data level bitmask would be OR-ed N times; with it - only once.

Config

Max index BitSet can hold, depends on used bitblocks capacity. The bigger the bitblocks - the higher BitSet index range. The lower - the smaller memory footprint it has.

Max index for 64bit blocks = 262_144; for 256bit blocks = 16_777_216.

Use BitSet with predefined config:

type BitSet = hi_sparse_bitset::BitSet<hi_sparse_bitset::config::_128bit>;

Inter-bitset operations

Inter-bitset operations can be applied between ANY BitSetInterface. Output of inter-bitset operations are lazy bitsets(which are BitSetInterfaces too). This means that you can combine different operations however you want without ever materializing them into actual BitSet.

Use reduce() to apply inter-bitset operation between elements of bitsets iterator.

Use apply() to apply inter-bitset operation between two bitsets. Also &, |, ^, -.

You can define your own inter-bitset operation, by implementing BinaryOp.

Cursor

BitSetInterface iterators can return cursor(), pointing to current iterator position. You can use Cursor to move ANY BitSetInterface iterator to it’s position with move_to.

DataBlocks

You can iterate DataBlocks instead of individual indices. DataBlocks can be moved, cloned and iterated for indices.

SIMD

128 and 256 bit configurations use SIMD. Make sure you compile with simd support enabled (sse2 for _128bit, avx for _256bit) to achieve best performance. sse2 enabled by default in Rust for most desktop environments

If you don’t need “wide” configurations, you may disable default feature “simd”.

Modules

• binary_op
  Operations for apply and reduce.
• bit_queue
  Bit iterator for BitBlock.
• cache
  Cache used by CachingBlockIter for reduce operations.
• config
  Configurations for BitSet.
• iter
  Iteration always return ordered (or sorted) index sequences.

Structs

• BitSet
  Hierarchical sparse bitset.
• BitSetOp
  Binary operation application, as lazy bitset.
• DataBlock
• DataBlockIter
• Reduce
  Bitsets iterator reduction, as lazy bitset.

Traits

• BitBlock
• BitSetBase
• BitSetInterface
• Primitive

Functions

• apply
  Creates a lazy bitset, as BinaryOp application between two bitsets.
• reduce
  Creates a lazy bitset, as bitsets iterator reduction.
• reduce_w_cache
  reduce, using specific cache for iteration.