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.
Rows that turn out to be a run, which is every row of the vector in order and is what a
comparison over a whole chunk asks for, are unpacked straight into the answer. The span and
the answer are the same rows in the same order there, so the buffer, the zeroing of it and
the pass copying it out are all a copy of a thing onto itself. A filter over a packed DATE
column of six million rows spent 37 percent of the query in here and the compare it fed 4.8
percent, which is the shape of paying three passes for one. Whether the rows are a run is one
compare a row in the pass that was already reading them.
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.