Module bitpack 

Bit packing in the FastLanes unified transposed layout.

Packing N values of a fixed bit width into a dense buffer is the bottom of every integer encoding in spec/06-compression.md section 6.2. FOR subtracts a base and packs. DELTA differences and packs. DICT produces codes and packs them. So this is the one kernel that runs over more bytes than anything else in the system, and the layout it uses decides whether the decoder can be data parallel or has to walk a dependency chain.

The obvious layout writes value 0 in the low bits of the first word, value 1 above it, and so on. Unpacking that requires knowing where the previous value ended, which is a sequential dependency, and a SIMD implementation has to fight it with shuffles that differ per width and per instruction set. FastLanes takes the other road. The 1024 values of a vector are seen as a matrix of T rows by 1024 / T lanes, where T is the bit width of the type, and the packing runs down the rows of every lane at once. Every lane has the same bit schedule, so unpacking lane 0 and lane 31 is the same instruction sequence with no cross lane data movement at all. That is what makes one scalar reference implementation and one AVX-512 implementation and one NEON implementation agree bit for bit, and it is why the vector size is 1024 rather than a rounder number.

The price is that the values come out permuted within the vector. Row r lane l is not the r * lanes + lth value of the input. Section 6.2 says why that is acceptable: an operator working inside one vector does not care what order the rows are in, so the permutation only has to be undone when a vector is materialized in row order. transpose and untranspose are that step, and they are deliberately separate from pack_transposed and unpack_transposed so that the engine can keep data permuted through a whole pipeline and pay for the reordering once at the end rather than twice per operator.

There is a second layout in here, in pack_tail, and it is the sequential one this module opens by arguing against. The transposed layout is all or nothing: a value lives at a row and a lane, the lanes are interleaved through the whole buffer, and no prefix of a packed unit holds a prefix of the values. So a unit holding 3 values costs exactly what a unit holding 1024 costs, and a cascade is full of short arrays. A five entry dictionary, a run length array, an exception list. Storing three numbers in 5 KB is not a compressed format. The tail packer handles anything shorter than a unit, it has the dependency chain the transposed layout exists to avoid, and that is affordable there and nowhere else, because a tail is at most 1023 values and is decoded once while a full unit is on the hot path of every scan in the system.

The permutation itself is a fixed shuffle of the eight bit groups of a row index, in the order 0, 4, 2, 6, 1, 5, 3, 7. That order is not arbitrary. It is the one that makes an eight way interleave of the rows land back in sequence under the pairwise unpacking pattern the paper uses, and the important property for us is only that it is a bijection that both directions agree on.

Constants

VALUES

How many values a packed unit holds. One vector, per spec/06-compression.md section 6.2.

Traits

Packable

An unsigned integer type that can be bit packed.

Functions

pack

Packs a vector given in row order, transposing it first.

pack_tail

Packs fewer than VALUES values, sequentially and to a byte boundary.

pack_transposed

Packs a transposed vector at a fixed bit width.

packed_len

How many words of T a packed vector of the given width occupies.

required_width

The smallest bit width that can hold every value in the slice. Zero for an empty slice or a slice of zeros, which pack_transposed handles as the degenerate case that stores nothing.

source_index

Where the value at row row lane lane of the transposed matrix came from in the input.

tail_len

How many bytes pack_tail writes for count values at width bits.

transpose

Rewrites 1024 values from row order into the transposed layout.

unpack

Unpacks into row order. The inverse of pack, and see its note about who should call it.

unpack_tail

Unpacks what pack_tail wrote.

unpack_transposed

Unpacks into the transposed layout. The inverse of pack_transposed.

untranspose

Rewrites 1024 values from the transposed layout back into row order.