Struct Bitmap 

pub struct Bitmap { /* private fields */ }

One bit per value, set meaning valid.

Words are u64 because that is the width the popcount and the mask tests want, and because a 1024 value vector is exactly 16 of them, which fits in a quarter of a cache line pair and is the reason the vector size is 1024 rather than DuckDB’s 2048.

Implementations

impl Bitmap

pub fn footprint(&self) -> usize

How many bytes of memory this bitmap is holding.

pub fn all_valid(len: usize) -> Self

A bitmap with room for len values, all valid.

pub fn all_invalid(len: usize) -> Self

A bitmap with room for len values, all null.

pub fn words(&self) -> &[u64]

The words themselves, for a loop that would rather read them than ask per row.

Self::get is written for one row: it reaches through the Vec, bounds checks the word and then tests the bit. A loop over a whole chunk pays all three per row for the first two of which nothing changes, so a kernel that walks every row takes the slice once and indexes it. What a caller has to remember is the part get handles and this does not, which is that a row past words.len() * 64 is not there and reads as invalid.

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

Whether the value at index is valid. Past the end reads as invalid.

pub fn set(&mut self, index: usize, valid: bool)

Sets whether the value at index is valid, growing the bitmap if it has to.

pub fn count_valid(&self, len: usize) -> usize

How many of the first len values are valid.

pub fn word(&self, at: usize) -> u64

Sixty four validity bits at once, the lowest numbered row in the lowest bit.

Past the end reads as all null, which is the same answer Self::get gives one bit at a time. This exists because a kernel that asks Self::get once per row pays a bounds check, a divide and a shift for each of them, and the word it wants was already in a register for the previous sixty three. A loop that reads the word once and walks its bits is the same answer at a fraction of the cost, and the three call sites that do that are the difference between a nullable column being free and being the slowest thing in the kernel.

pub fn slice(&self, at: usize, len: usize) -> Self

The len bits starting at at, moved down to start at bit zero.

A word at a time, because a cut is almost never on a word boundary and doing it a bit at a time is a divide, a shift and a read modify write per row. Each output word is the high part of one input word and the low part of the next, which is two loads and three shifts for sixty four rows.

The bits past len in the last word are set rather than clear, for the reason Validity::from_run gives: this type has no length, so its equality is over whole words and a constructor that left them clear would compare unequal to one that did not.

pub fn and_with(&mut self, other: &Self)

Intersects this bitmap with another, in place.

Trait Implementations

impl Clone for Bitmap

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Bitmap

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

Formats the value using the given formatter.

impl Eq for Bitmap

impl PartialEq for Bitmap

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

Equality operator ==.

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

Inequality operator !=.

impl StructuralPartialEq for Bitmap