Struct hi_sparse_bitset::SmallBitSet

pub struct SmallBitSet<Conf: SmallConfig>(/* private fields */);

Same as BitSet, but sparsely populated hierarchy blocks 9 times smaller.

Which means that sparse sets virtually do not have indirection-related memory overhead!

Memory

For _128bit each Level1 block consumes just 32 bytes, if less than 8 data blocks pointed from. 256+32 bytes otherwise.

Performance

All operations still have O(1) complexity. But in terms of raw performance, (due to additional layer of indirection) this is x1.5 - x2 slower than BitSet. Which is still very fast.

Implementation details

Level0          128bit SIMD                                        
                 [u8;128]                                          

            ┌   128bit SIMD    ┐    ╭─ ── ── ── ── ── ── ── ── ── ╮
            │ ╭──────────────╮ │      Act as SBO:                 │
Level1   Vec│ │   [u16;7]    │ │    │- Inline SparseBitMap, for    
            │ │ ──────────── │◁┼────┤small size.                  │
            │ │Box<[u16;128]>│ │     - Boxed full-size array with │
            └ ╰──────────────╯ ┘    │direct access for a big one.    
            ┌                  ┐    ╰ ── ── ── ── ── ── ── ── ── ─╯
Data     Vec│   128bit SIMD    │                                   
            └                  ┘                                   

SparseBitMap - bit_block acts as a sparse array:

                  0 1       2 3          ◁═ popcnt before element
                                            (dense_array indices)
 bit_block      0 1 1 0 0 0 1 1 0 0 ...                          
              └───┬─┬───────┬─┬─────────┘                        
               ┌──┘┌┘ ┌─────┘ │                                  
               │   │  │  ┌────┘                                  
               ▼   ▼  ▼  ▼                                       
dense_array    1, 32, 4, 5               len = bit_block popcnt  

As you can see, SparseBitMap has fast O(1) per-index access. Insert and remove - are O(N) operations, because dense_array must keep its element order.

Why not just use SparseBitMap for everything? Big-sized dense_array should be placed somewhere outside of LevelBlock struct to be memory efficient (e.g., in dynamic-sized heap). Hence - it will be accessed through the pointer (which is yet another layer of indirection). Due to this, and the O(N) insert/remove - SparseBitMap is used only for small-sized arrays. We aim for a 16-element array - as with this size, data blocks pointed from level1 block will have the same size in total, as a full-sized level1 block indirection array.

Implementations

impl<Conf> SmallBitSet<Conf>

where Conf: SmallConfig,

pub fn new() -> Self

pub const fn max_capacity() -> usize

Max usize, bitset with this Conf can hold.

pub fn insert(&mut self, index: usize)

Safety

Will panic, if index is out of range.

pub fn remove(&mut self, index: usize) -> bool

Returns false if index is invalid/not in bitset.

pub unsafe fn remove_unchecked(&mut self, index: usize)

Safety

index MUST exists in HiSparseBitset!

impl<Conf> SmallBitSet<Conf>

where Conf: SmallConfig,

pub fn block_iter<'a>(&'a self) -> CachingBlockIter<&'a Self>

pub fn iter<'a>(&'a self) -> CachingIndexIter<&'a Self>

pub fn contains(&self, index: usize) -> bool

pub fn is_empty(&self) -> bool

See BitSetInterface::is_empty()

Trait Implementations

impl<Conf, Rhs> BitAnd<Rhs> for &SmallBitSet<Conf>

where Rhs: BitSetInterface<Conf = <Self as BitSetBase>::Conf>, Conf: SmallConfig,

fn bitand(self, rhs: Rhs) -> Self::Output

Returns intersection of self and rhs bitsets.

type Output = Apply<And, &SmallBitSet<Conf>, Rhs>

The resulting type after applying the & operator.

impl<Conf, Rhs> BitOr<Rhs> for &SmallBitSet<Conf>

where Rhs: BitSetInterface<Conf = <Self as BitSetBase>::Conf>, Conf: SmallConfig,

fn bitor(self, rhs: Rhs) -> Self::Output

Returns union of self and rhs bitsets.

type Output = Apply<Or, &SmallBitSet<Conf>, Rhs>

The resulting type after applying the | operator.

impl<Conf: SmallConfig> BitSetBase for SmallBitSet<Conf>

type Conf = Conf

const TRUSTED_HIERARCHY: bool = true

Does each raised bit in hierarchy bitblock correspond to non-empty data block?

impl<Conf> BitSetInterface for &SmallBitSet<Conf>

where Conf: SmallConfig,

fn block_iter(&self) -> CachingBlockIter<&Self>

fn iter(&self) -> CachingIndexIter<&Self>

fn into_block_iter(self) -> CachingBlockIter<Self>

fn contains(&self, index: usize) -> bool

fn is_empty(&self) -> bool

O(1) if TRUSTED_HIERARCHY, O(N) otherwise.

impl<Conf, Rhs> BitXor<Rhs> for &SmallBitSet<Conf>

where Rhs: BitSetInterface<Conf = <Self as BitSetBase>::Conf>, Conf: SmallConfig,

fn bitxor(self, rhs: Rhs) -> Self::Output

Returns symmetric difference of self and rhs bitsets.

type Output = Apply<Xor, &SmallBitSet<Conf>, Rhs>

The resulting type after applying the ^ operator.

impl<Conf> Clone for SmallBitSet<Conf>

where Conf: SmallConfig,

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Conf> Debug for SmallBitSet<Conf>

where Conf: SmallConfig,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<Conf> Default for SmallBitSet<Conf>

where Conf: SmallConfig,

fn default() -> Self

Returns the “default value” for a type.

impl<Conf, const N: usize> From<[usize; N]> for SmallBitSet<Conf>

where Conf: SmallConfig,

fn from(value: [usize; N]) -> Self

Converts to this type from the input type.

impl<Conf> FromIterator<usize> for SmallBitSet<Conf>

where Conf: SmallConfig,

fn from_iter<T: IntoIterator<Item = usize>>(iter: T) -> Self

Creates a value from an iterator.

impl<Conf> IntoIterator for &SmallBitSet<Conf>

where Conf: SmallConfig,

type Item = usize

The type of the elements being iterated over.

type IntoIter = CachingIndexIter<&SmallBitSet<Conf>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<Conf> LevelMasks for SmallBitSet<Conf>

where Conf: SmallConfig,

fn level0_mask(&self) -> <Self::Conf as Config>::Level0BitBlock

unsafe fn level1_mask( &self, level0_index: usize ) -> <Self::Conf as Config>::Level1BitBlock

Safety

unsafe fn data_mask( &self, level0_index: usize, level1_index: usize ) -> <Self::Conf as Config>::DataBitBlock

Safety

impl<Conf> LevelMasksIterExt for SmallBitSet<Conf>

where Conf: SmallConfig,

type IterState = <RawBitSet<Conf, Block<<Conf as Config>::Level0BitBlock, <Conf as Config>::Level0BlockIndices>, CompactBlock<<Conf as Config>::Level1BitBlock, <Conf as SmallConfig>::Level1MaskU64Populations, <Conf as Config>::Level1BlockIndices, <Conf as SmallConfig>::Level1SmallBlockIndices>, Block<<Conf as Config>::DataBitBlock, [usize; 0]>> as LevelMasksIterExt>::IterState

Consists from child states (if any) + Self state.

type Level1BlockData = <RawBitSet<Conf, Block<<Conf as Config>::Level0BitBlock, <Conf as Config>::Level0BlockIndices>, CompactBlock<<Conf as Config>::Level1BitBlock, <Conf as SmallConfig>::Level1MaskU64Populations, <Conf as Config>::Level1BlockIndices, <Conf as SmallConfig>::Level1SmallBlockIndices>, Block<<Conf as Config>::DataBitBlock, [usize; 0]>> as LevelMasksIterExt>::Level1BlockData

Level1 block related data, used to speed up data_mask access.

fn make_iter_state(&self) -> Self::IterState

unsafe fn drop_iter_state(&self, state: &mut ManuallyDrop<Self::IterState>)

Having separate function for drop not strictly necessary, since IterState can actually drop itself. But! This allows not to store cache size within IterState. Which makes FixedCache CacheData ZST, if its childs are ZSTs, and which makes cache construction and destruction noop. Which is important for short iteration sessions.

unsafe fn init_level1_block_data( &self, state: &mut Self::IterState, level1_block_data: &mut MaybeUninit<Self::Level1BlockData>, level0_index: usize ) -> (<Self::Conf as Config>::Level1BitBlock, bool)

Init level1_block_data and return (Level1Mask, is_not_empty).

unsafe fn data_mask_from_block_data( level1_block_data: &Self::Level1BlockData, level1_index: usize ) -> <Self::Conf as Config>::DataBitBlock

Safety

impl<Conf, Rhs> PartialEq<Rhs> for SmallBitSet<Conf>

where Rhs: LevelMasksIterExt<Conf = <Self as BitSetBase>::Conf>, Conf: SmallConfig,

fn eq(&self, other: &Rhs) -> bool

Works faster with TRUSTED_HIERARCHY.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<Conf, Rhs> Sub<Rhs> for &SmallBitSet<Conf>

where Rhs: BitSetInterface<Conf = <Self as BitSetBase>::Conf>, Conf: SmallConfig,

fn sub(self, rhs: Rhs) -> Self::Output

Returns difference of self and rhs bitsets.

Or relative complement of rhs in self.

type Output = Apply<Sub, &SmallBitSet<Conf>, Rhs>

The resulting type after applying the - operator.

impl<Conf> Eq for SmallBitSet<Conf>

where Conf: SmallConfig,