Struct Packed

Source

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<'_>

Source

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

Packed words. A persisted vector also records Self::offset.

Source

pub fn offset(&self) -> usize

Bit offset, in rows, of the first value.

Source

pub fn width(&self) -> u32

How many bits one code takes, between one and PACKED_WIDTH_MAX.

Source

pub fn base(&self) -> i128

What zero means, so that the value of a row is the base plus its code.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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.

Self::codes_into into a vector of its own. A caller reading a column a chunk at a time wants that vector once rather than once a chunk, and calls the other one.

Source

pub fn codes_into<M: Fn(usize) -> usize>( &self, at: M, rows: usize, out: &mut Vec<u64>, )

The code of each of rows rows at names, in order, left in out[..rows].

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.

Rows that are not a run, which is the second conjunct of a filter reading only the rows the first one kept, unpack the span they cover into a buffer each thread keeps rather than a fresh one. The span of a selection over a chunk is about as wide as the chunk whatever the selection keeps, so the fresh buffer was an allocation and a page of zeroes a chunk for a run of zeroes that the unpack immediately writes over. Self::values_at below keeps its span the same way and for the same reason.

out is grown to hold rows and is not otherwise touched, so a buffer longer than the rows keeps whatever is past them, and a buffer already long enough is not zeroed on the way in. Every one of out[..rows] is written before this returns.

Source

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.