pub struct Packed<'a> { /* private fields */ }Expand description
The bits of a packed vector and what they mean, for a kernel that wants to stay in code space.
Borrowed from the vector rather than owning anything, so getting one costs nothing and a kernel that finds it cannot use them has given up nothing by asking.
Implementations§
Source§impl Packed<'_>
impl Packed<'_>
Sourcepub fn words(&self) -> &[u64]
pub fn words(&self) -> &[u64]
Packed words. A persisted vector also records Self::offset.
Sourcepub fn width(&self) -> u32
pub fn width(&self) -> u32
How many bits one code takes, between one and PACKED_WIDTH_MAX.
Sourcepub fn base(&self) -> i128
pub fn base(&self) -> i128
What zero means, so that the value of a row is the base plus its code.
Sourcepub fn ceiling(&self) -> i128
pub fn ceiling(&self) -> i128
The largest value this vector can be holding, whatever it is actually holding.
With Self::base this is the pair a comparison kernel wants first. A literal outside the
two answers every row of the vector the same way, which is a whole chunk decided without a
bit being read, and that is the case a zone map would have caught if there were one here.
Sourcepub fn code(&self, row: usize) -> u64
pub fn code(&self, row: usize) -> u64
The code of row row, which is its value minus Self::base.
Out of range rows read as zero rather than panicking, the way every other accessor in this file answers for a row that is not there.
Marked inline because every caller that matters is a kernel in another crate reading one code per row, and thin LTO was leaving it as a call there. On TPC-H SF1 that call was 1.5 percent of the suite and a tenth of q12.
Sourcepub fn code_of(&self, value: i128) -> Option<u64>
pub fn code_of(&self, value: i128) -> Option<u64>
Which code a value would have, and None for a value this vector cannot be holding.
The translation a comparison does once per vector so that it does not have to unpack once per
row. None is the useful answer rather than a failure: it says the literal is outside the
packed range, so every row compares against it the same way.
Sourcepub fn unpack(&self, from: usize, out: &mut [u64])
pub fn unpack(&self, from: usize, out: &mut [u64])
The codes of rows from to from + out.len(), in one pass over the words.
Self::code is a code at a time, and every one of them works out which word it is in, reads
it through a bound, and asks whether it straddles into the next. Sixty four codes of one
width fill exactly that many words and the straddles fall in the same places every time, so a
block of them is unpacked by a loop the width is a constant in, where every shift and every
straddle is known before it runs. On TPC-H q1 the code at a time reads were a third of the
instructions the query ran. The rows before the first whole block and after the last one
still go a code at a time.
Sourcepub fn codes_at<M: Fn(usize) -> usize>(&self, at: M, rows: usize) -> Vec<u64>
pub fn codes_at<M: Fn(usize) -> usize>(&self, at: M, rows: usize) -> Vec<u64>
The code of each of rows rows at names, in order.
A filter’s selection names rows close together and in order, so the span they cover is
unpacked whole with Self::unpack and each row read out of it. Rows spread too far apart
for that to pay are read a code at a time.
Unpacking a block at a time into a buffer on the stack, and reading each row out of the block it falls in, keeps less in the cache and was tried. The question of which block a row is in, asked for every row, cost more than the misses it saved, 40.2 G instructions for ten runs of q1 against 34.1 G this way.
Sourcepub fn values_at<T>(&self, at: &[u32], value: impl Fn(u64) -> T) -> Vec<T>
pub fn values_at<T>(&self, at: &[u32], value: impl Fn(u64) -> T) -> Vec<T>
The value of each row at names, in order, made from its code by value.
Self::codes_at for a filter’s u32 positions, with the value made as each row is read
rather than in a second pass over the codes. Three things it did cost more than the reads on
q01, where a filter keeps nearly every row of every packed column. The smallest and largest
position were a scalar compare and move a row, because SSE2 has no unsigned or 64 bit
minimum, and here they are signed 32 bit ones, which it has. The span was a fresh buffer
of zeroes, and here each thread keeps one. And the codes were written out whole before the
values were made from them.