pixie::BitVectorInterleaved Class Reference

Interleaved, owning bit vector with rank and select. More...

#include <bitvector.h>

Public Member Functions
	BitVectorInterleaved (std::span< const uint64_t > bit_vector, size_t num_bits)
	Construct from an external array of 64-bit words.
size_t	size () const
	Returns the number of valid bits.
int	operator[] (size_t pos) const
	Returns the bit at the given position.
void	build_rank_interleaved (std::span< const uint64_t > bits, size_t num_bits)
	Build the interleaved layout and rank index.
uint64_t	rank (size_t pos) const
	Rank of 1s up to position pos (exclusive).
std::string	to_string () const
	Convert to a binary string (debug helper).

Static Public Member Functions
static uint64_t	first_bits_mask (size_t num)
	Mask with the lowest num bits set.

Detailed Description

Interleaved, owning bit vector with rank and select.

This variant interleaves data with local rank metadata to reduce cache misses for rank queries. It copies input bits into an interleaved layout.

Based on: "SPIDER: Improved Succinct Rank and Select Performance" Matthew D. Laws, Jocelyn Bliven, Kit Conklin, Elyes Laalai, Samuel McCauley, Zach S. Sturdevant

Constructor & Destructor Documentation

BitVectorInterleaved()

pixie::BitVectorInterleaved::BitVectorInterleaved ( std::span< const uint64_t > bit_vector, size_t num_bits )

inlineexplicit

Construct from an external array of 64-bit words.

Parameters

bit_vector	Backing data to copy and interleave.
num_bits	Number of valid bits in the vector.

Member Function Documentation

build_rank_interleaved()

void pixie::BitVectorInterleaved::build_rank_interleaved ( std::span< const uint64_t > bits, size_t num_bits )

inline

Build the interleaved layout and rank index.

Parameters

bits	Source bit vector as 64-bit words.
num_bits	Number of valid bits in the source.

operator[]()

int pixie::BitVectorInterleaved::operator[] ( size_t pos ) const

inline

Returns the bit at the given position.

Parameters

pos	Bit index in [0, size()).

rank()

uint64_t pixie::BitVectorInterleaved::rank ( size_t pos ) const

inline

Rank of 1s up to position pos (exclusive).

Parameters

pos	Bit index in [0, size()].

Returns

Number of 1s in [0, pos).

Ok, so here's quite the important factor to load 512-bit region at &bits_interleaved[b_block_pos], we store local rank as 16 last bits of it. Prefetch should guarantee but seems like there is no need for it.

---

The documentation for this class was generated from the following file:

• include/pixie/bitvector.h