Skip to content

Commit e8e48c8

Browse files
authored
Blocked BitPacked: store block offsets as a child (#10004)
Tracking Issue: #10167 ## Summary Add an optional `block_offsets` child to `BitPackedArray` that stores the byte boundaries of independently sized packed blocks, and make the shared bit width in `BitPackedData` optional. An array has exactly one of the two: a global bit width, as today, or block offsets. ## Design ### Bit widths `BitPackedData::global_bit_width` is `Some(width)` when every block shares a width, and `None` when `block_offsets` is `Some`. Validation requires exactly one of them. `BitPackedArrayExt::bit_widths()` replaces `bit_width()`: ```rust pub enum BitWidths { /// Every block is packed at this bit width. Global(u8), /// Byte boundaries of the packed blocks, from which each block's bit width is derived. Blocked(ArrayRef), } ``` Paths that need one width (decoding, `scalar_at`, v1 serialization and CUDA) return an error for blocked arrays until the decoder follow-ups. There is a viewed and owned version of this. ### Block offsets `block_offsets` is a non-nullable unsigned integer array with `num_blocks + 1` entries, including a trailing end boundary. Boundaries are relative to the first entry. Block `i` occupies bytes `block_offsets[i] - block_offsets[0]` to `block_offsets[i + 1] - block_offsets[0]` of the packed buffer, at `(block_offsets[i + 1] - block_offsets[i]) / 128` bits, because a 1024-value block at width `w` takes `128 * w` bytes. For example, three blocks at widths 3, 0 and 7 have offsets `[0, 384, 384, 1280]`. Offsets with equal steps are still blocked; nothing converts them to a global width. ## Validation - A global width must be at most `ptype.bit_width()` (previously at most 64), and the packed buffer must hold `num_blocks * 128 * width` bytes, as before. - Block offsets must have a non-nullable unsigned integer dtype and `num_blocks + 1` entries. Host-resident primitive offsets are also checked boundary by boundary: they must be nondecreasing, each block must be a whole number of 128-byte rows at most `ptype.bit_width()` bits wide, and together they must span exactly the packed buffer. Other encodings and device-resident offsets only get the dtype and length checks. ## Scope Nothing in this PR produces block offsets, but arrays built with `try_new_with_block_offsets` can be constructed and inspected. Kernels decline them, and decoding, scalar access, serialization and CUDA return an error. ## Wire format and compatibility `fastlanes.bitpacked` is unchanged. A global-width array has no block offsets child, so it serializes exactly as before, and the reader builds a global-width array from the metadata `bit_width`. Serializing a blocked array with this plugin returns an error. Compression goldens are unchanged. ## API changes - `BitPackedArrayExt::bit_width()` and `BitPackedData::bit_width()` are replaced by `BitPackedArrayExt::bit_widths() -> BitWidths`. - `BitPackedDataParts::bit_width: u8` is replaced by `bit_widths: BitWidths`. - `BitPacked::try_new_with_block_offsets` constructs an array from packed data and block boundaries. `BitPacked::try_new` and `BitPackedData::try_new` are unchanged. - `BitUnpackedChunks::try_new` and both `unpacked_chunks` accessors return an error for blocked arrays. - `bitpack_decompress::unpack_single` returns `VortexResult<Scalar>`. - The unused `max_packed_value()` accessor is removed. - The Python `FastLanesBitPackedArray.bit_width` property returns `int | None`. --------- Signed-off-by: Matt Katz <[email protected]>
1 parent 750b36d commit e8e48c8

27 files changed

Lines changed: 809 additions & 95 deletions

File tree

‎encodings/fastlanes/benches/bitpack_compare.rs‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@ use vortex_buffer::BufferMut;
3030
use vortex_fastlanes::BitPacked;
3131
use vortex_fastlanes::BitPackedArray;
3232
use vortex_fastlanes::BitPackedData;
33+
use vortex_fastlanes::BitWidths;
3334
use vortex_session::VortexSession;
3435

3536
#[global_allocator]
@@ -58,12 +59,15 @@ const BIT_WIDTHS: &[u8] = &[4, 16];
5859
fn page_aligned(array: BitPackedArray) -> BitPackedArray {
5960
let ptype = array.dtype().as_ptype();
6061
let parts = BitPacked::into_parts(array);
62+
let BitWidths::Global(bit_width) = parts.bit_widths else {
63+
unreachable!("bitpack_encode packs every block at one bit width")
64+
};
6165
BitPacked::try_new(
6266
parts.packed.ensure_aligned(Alignment::new(4096)).unwrap(),
6367
ptype,
6468
parts.validity,
6569
parts.patches,
66-
parts.bit_width,
70+
bit_width,
6771
parts.len,
6872
parts.offset,
6973
)

‎encodings/fastlanes/benches/bitpack_compare_sweep.rs‎

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ use vortex_buffer::BufferMut;
3434
use vortex_fastlanes::BitPacked;
3535
use vortex_fastlanes::BitPackedArray;
3636
use vortex_fastlanes::BitPackedData;
37+
use vortex_fastlanes::BitWidths;
3738
use vortex_session::VortexSession;
3839

3940
#[global_allocator]
@@ -84,12 +85,15 @@ impl_bench_int!(u8, u16, u32, u64, i8, i16, i32, i64);
8485
fn page_aligned(array: BitPackedArray) -> BitPackedArray {
8586
let ptype = array.dtype().as_ptype();
8687
let parts = BitPacked::into_parts(array);
88+
let BitWidths::Global(bit_width) = parts.bit_widths else {
89+
unreachable!("bitpack_encode packs every block at one bit width")
90+
};
8791
BitPacked::try_new(
8892
parts.packed.ensure_aligned(Alignment::new(4096)).unwrap(),
8993
ptype,
9094
parts.validity,
9195
parts.patches,
92-
parts.bit_width,
96+
bit_width,
9397
parts.len,
9498
parts.offset,
9599
)

‎encodings/fastlanes/src/bitpacking/array/bitpack_decompress.rs‎

Lines changed: 14 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -17,11 +17,12 @@ use vortex_array::match_each_integer_ptype;
1717
use vortex_array::match_each_unsigned_integer_ptype;
1818
use vortex_array::patches::Patches;
1919
use vortex_array::scalar::Scalar;
20-
use vortex_error::VortexExpect;
2120
use vortex_error::VortexResult;
21+
use vortex_error::vortex_bail;
2222

2323
use crate::BitPacked;
2424
use crate::BitPackedArrayExt;
25+
use crate::BitWidthsView;
2526
use crate::FL_CHUNK_SIZE;
2627
use crate::unpack_iter::BitPacked as BitPackedUnpack;
2728
use crate::unpack_iter::BitUnpackedChunks;
@@ -114,18 +115,19 @@ where
114115
}
115116

116117
let len = array.len();
118+
let mut scratch = [const { MaybeUninit::<F>::uninit() }; FL_CHUNK_SIZE];
119+
let mut chunks = array.unpacked_chunks::<F>(&mut scratch)?;
120+
let validity = array.validity()?.execute_mask(len, ctx)?;
117121
let mut uninit_range = builder.uninit_range(len);
118122

119123
// SAFETY: We initialize all `len` values below via `decode` and the patch loop.
120124
unsafe {
121-
uninit_range.append_mask(&array.validity()?.execute_mask(len, ctx)?);
125+
uninit_range.append_mask(&validity);
122126
}
123127

124128
// SAFETY: `decode` writes a value to every slot in this range.
125129
let uninit_slice = unsafe { uninit_range.slice_uninit_mut(0, len) };
126130

127-
let mut scratch = [const { MaybeUninit::<F>::uninit() }; FL_CHUNK_SIZE];
128-
let mut chunks = array.unpacked_chunks::<F>(&mut scratch)?;
129131
decode(&mut chunks, uninit_slice, &map);
130132

131133
if let Some(patches) = array.patches() {
@@ -164,8 +166,11 @@ pub(crate) fn apply_patches_to_uninit_range<S: NativePType, T: NativePType, F: F
164166
Ok(())
165167
}
166168

167-
pub fn unpack_single(array: ArrayView<'_, BitPacked>, index: usize) -> Scalar {
168-
let bit_width = array.bit_width() as usize;
169+
pub fn unpack_single(array: ArrayView<'_, BitPacked>, index: usize) -> VortexResult<Scalar> {
170+
let BitWidthsView::Global(bit_width) = array.bit_widths() else {
171+
vortex_bail!("BitPacked array has per-block bit widths");
172+
};
173+
let bit_width = bit_width as usize;
169174
let ptype = array.dtype().as_ptype();
170175
// let packed = array.packed().into_primitive()?;
171176
let index_in_encoded = index + array.offset() as usize;
@@ -176,7 +181,7 @@ pub fn unpack_single(array: ArrayView<'_, BitPacked>, index: usize) -> Scalar {
176181
}
177182
});
178183
// Cast to fix signedness and nullability
179-
scalar.cast(array.dtype()).vortex_expect("cast failure")
184+
scalar.cast(array.dtype())
180185
}
181186

182187
/// # Safety
@@ -227,6 +232,7 @@ mod tests {
227232
use vortex_buffer::Buffer;
228233
use vortex_buffer::BufferMut;
229234
use vortex_buffer::buffer;
235+
use vortex_error::VortexExpect;
230236
use vortex_session::VortexSession;
231237

232238
use super::*;
@@ -259,7 +265,7 @@ mod tests {
259265
.iter()
260266
.enumerate()
261267
.for_each(|(i, v)| {
262-
let scalar: u16 = (&unpack_single(compressed.as_view(), i))
268+
let scalar: u16 = (&unpack_single(compressed.as_view(), i).unwrap())
263269
.try_into()
264270
.unwrap();
265271
assert_eq!(scalar, *v);

0 commit comments

Comments
 (0)