Skip to content

Commit 9c8a995

Browse files
authored
Blocked BitPacked: fuse FoR decode over blocked children (#10251)
Tracking Issue: #10167 ## Summary `FoR` now decodes a blocked `BitPacked` child in one pass, the same as a global-width child. Before, the child was decoded to a primitive array first and the references were added in a second pass. A block and a FoR chunk are both 1024 values, so each block unpacks at its own width and adds its chunk's reference directly. ## Changes - `unpack_chunks` walks the blocks of a blocked child, each at its own width. - `execute_block_offsets` and `for_each_packed_block` are shared with the blocked `BitPacked` decoder. - Block offsets widen to `u64` directly instead of through a lazy `cast`. ## Benchmarks `for_decode`, per-chunk references, local M5 Max: | | Global width | Blocked, before | Blocked, after | | --- | --- | --- | --- | | u32 | 9.62 µs | 18.54 µs | 9.87 µs | | i64 | 11.95 µs | 20.04 µs | 12.29 µs | ## Testing - `fused_decode_is_wrapping_add` draws a bit width per block. - `for_fuses_blocked_child` covers partial blocks, zero and native widths, and constant and per-chunk references. ## Follow-up `FoRScheme` still bit-packs its child with `BITPACKING_V1`, so the compressor doesn't write this combination yet. That needs #10245. --------- Signed-off-by: Matt Katz <[email protected]>
1 parent df98590 commit 9c8a995

6 files changed

Lines changed: 193 additions & 64 deletions

File tree

‎encodings/fastlanes/benches/for_decode.rs‎

Lines changed: 33 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,9 @@
33

44
//! Benchmarks decoding a FoR array with a reference per 1024-element chunk, over a primitive child
55
//! and over a BitPacked child. An unsigned BitPacked child decodes through a fused unpack, and a
6-
//! signed one through BitPacked decoding followed by adding the references in place.
6+
//! signed one through BitPacked decoding followed by adding the references in place. The blocked
7+
//! BitPacked child packs every block at the same width as the global one, so the two compare the
8+
//! cost of per-block bit widths alone.
79
//!
810
//! Every benchmark carries `#[cpu_features]`, so it is measured on each walltime CPU-feature leg
911
//! rather than in simulation: the loops under test are auto-vectorized, so the build decides
@@ -26,6 +28,7 @@ use vortex_array::dtype::NativePType;
2628
use vortex_array::validity::Validity;
2729
use vortex_buffer::Buffer;
2830
use vortex_fastlanes::BitPacked;
31+
use vortex_fastlanes::BitPackedData;
2932
use vortex_fastlanes::FoR;
3033
use vortex_fastlanes::FoRArraySlotsExt;
3134
use vortex_session::VortexSession;
@@ -55,22 +58,33 @@ fn values<T: NativePType + TryFrom<usize>>(len: usize) -> Buffer<T> {
5558
.collect()
5659
}
5760

58-
fn for_array<T: NativePType + TryFrom<usize>>(len: usize, bitpacked: bool) -> ArrayRef {
61+
#[derive(Clone, Copy)]
62+
enum Child {
63+
Primitive,
64+
BitPacked,
65+
BlockedBitPacked,
66+
}
67+
68+
fn for_array<T: NativePType + TryFrom<usize>>(len: usize, child: Child) -> ArrayRef {
5969
let mut ctx = SESSION.create_execution_ctx();
6070
let array = PrimitiveArray::new(values::<T>(len), Validity::NonNullable);
6171
let for_array = FoR::encode_chunked(array, &mut ctx).unwrap();
62-
if !bitpacked {
63-
return for_array.into_array();
64-
}
65-
let packed = BitPacked::encode(for_array.encoded(), BIT_WIDTH, &mut ctx).unwrap();
72+
let packed = match child {
73+
Child::Primitive => return for_array.into_array(),
74+
Child::BitPacked => BitPacked::encode(for_array.encoded(), BIT_WIDTH, &mut ctx).unwrap(),
75+
Child::BlockedBitPacked => {
76+
let bit_widths = vec![BIT_WIDTH; len.div_ceil(1024)];
77+
BitPackedData::encode_blocked(for_array.encoded(), &bit_widths, &mut ctx).unwrap()
78+
}
79+
};
6680
FoR::try_new_chunked(packed.into_array(), for_array.references().clone(), 0)
6781
.unwrap()
6882
.into_array()
6983
}
7084

71-
fn run<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize, bitpacked: bool) {
85+
fn run<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize, child: Child) {
7286
let len = bytes / size_of::<T>();
73-
let array = for_array::<T>(len, bitpacked);
87+
let array = for_array::<T>(len, child);
7488
bencher
7589
.counter(ItemsCount::new(len))
7690
.with_inputs(|| (&array, SESSION.create_execution_ctx()))
@@ -80,11 +94,20 @@ fn run<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize, bitpacke
8094
#[vortex_bench_support::cpu_features]
8195
#[divan::bench(types = [i64], args = INPUT_BYTES)]
8296
fn decode_chunked<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize) {
83-
run::<T>(bencher, bytes, false);
97+
run::<T>(bencher, bytes, Child::Primitive);
8498
}
8599

86100
#[vortex_bench_support::cpu_features]
87101
#[divan::bench(types = [u32, i64], args = INPUT_BYTES)]
88102
fn decode_bitpacked_chunked<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize) {
89-
run::<T>(bencher, bytes, true);
103+
run::<T>(bencher, bytes, Child::BitPacked);
104+
}
105+
106+
#[vortex_bench_support::cpu_features]
107+
#[divan::bench(types = [u32, i64], args = INPUT_BYTES)]
108+
fn decode_blocked_bitpacked_chunked<T: NativePType + TryFrom<usize>>(
109+
bencher: Bencher,
110+
bytes: usize,
111+
) {
112+
run::<T>(bencher, bytes, Child::BlockedBitPacked);
90113
}

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

Lines changed: 105 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
66
use std::mem;
77
use std::mem::MaybeUninit;
8+
use std::ops::Range;
89

910
use fastlanes::BitPacking;
1011
use num_traits::AsPrimitive;
@@ -15,10 +16,6 @@ use vortex_array::arrays::Primitive;
1516
use vortex_array::arrays::PrimitiveArray;
1617
use vortex_array::builders::ArrayBuilder;
1718
use vortex_array::builders::PrimitiveBuilder;
18-
use vortex_array::builtins::ArrayBuiltins;
19-
use vortex_array::dtype::DType;
20-
use vortex_array::dtype::Nullability;
21-
use vortex_array::dtype::PType;
2219
use vortex_array::dtype::PhysicalPType;
2320
use vortex_array::match_each_integer_ptype;
2421
use vortex_array::match_each_unsigned_integer_ptype;
@@ -81,23 +78,7 @@ pub(crate) fn unpack_into_primitive_builder_blocked<T: BitPackedUnpack>(
8178
"Requested type doesn't match the array ptype"
8279
);
8380

84-
// Decoding one offset type compiles the block loop once per value type.
85-
let offsets = offsets
86-
.cast(DType::Primitive(PType::U64, Nullability::NonNullable))?
87-
.execute::<PrimitiveArray>(ctx)?;
88-
let num_blocks = (array.len() + usize::from(array.offset())).div_ceil(FL_CHUNK_SIZE);
89-
vortex_ensure!(
90-
offsets.len() == num_blocks + 1,
91-
"Expected {} block boundaries, got {}",
92-
num_blocks + 1,
93-
offsets.len()
94-
);
95-
let offsets = Buffer::<u64>::from_byte_buffer(offsets.buffer_handle().try_to_host_sync()?);
96-
validate_primitive_offsets(
97-
&offsets,
98-
array.dtype().as_ptype().bit_width() as u64,
99-
array.packed().len(),
100-
)?;
81+
let offsets = execute_block_offsets(array, offsets, ctx)?;
10182

10283
let len = array.len();
10384
let validity = array.validity()?.execute_mask(len, ctx)?;
@@ -126,6 +107,66 @@ pub(crate) fn unpack_into_primitive_builder_blocked<T: BitPackedUnpack>(
126107
Ok(())
127108
}
128109

110+
/// Execute the block `offsets` of `array` to host `u64` boundaries and validate them against its
111+
/// packed buffer.
112+
pub(crate) fn execute_block_offsets(
113+
array: ArrayView<'_, BitPacked>,
114+
offsets: &ArrayRef,
115+
ctx: &mut ExecutionCtx,
116+
) -> VortexResult<Buffer<u64>> {
117+
let offsets = offsets.clone().execute::<PrimitiveArray>(ctx)?;
118+
let num_blocks = (array.len() + usize::from(array.offset())).div_ceil(FL_CHUNK_SIZE);
119+
vortex_ensure!(
120+
offsets.len() == num_blocks + 1,
121+
"Expected {} block boundaries, got {}",
122+
num_blocks + 1,
123+
offsets.len()
124+
);
125+
// Decoding one offset type compiles the block loop once per value type. Widening the few
126+
// boundaries here is cheaper than executing a cast.
127+
let host = offsets.buffer_handle().try_to_host_sync()?;
128+
let offsets: Buffer<u64> = match_each_unsigned_integer_ptype!(offsets.ptype(), |I| {
129+
Buffer::<I>::from_byte_buffer(host)
130+
.iter()
131+
.map(|&offset| AsPrimitive::<u64>::as_(offset))
132+
.collect()
133+
});
134+
validate_primitive_offsets(
135+
&offsets,
136+
array.dtype().as_ptype().bit_width() as u64,
137+
array.packed().len(),
138+
)?;
139+
Ok(offsets)
140+
}
141+
142+
/// Walk the packed blocks between `offsets` from [`execute_block_offsets`] in array order, passing
143+
/// each block's packed values, bit width and range of positions counted from the start of the
144+
/// first block.
145+
pub(crate) fn for_each_packed_block<T, F>(
146+
packed: &[T::Physical],
147+
offsets: &[u64],
148+
offset: usize,
149+
len: usize,
150+
mut f: F,
151+
) where
152+
T: PhysicalPType,
153+
F: FnMut(&[T::Physical], usize, Range<usize>),
154+
{
155+
let base = offsets[0];
156+
let padded_len = offset + len;
157+
for (block, pair) in offsets.windows(2).enumerate() {
158+
// Validation bounds these differences by the packed buffer's usize length.
159+
let start = (pair[0] - base) as usize;
160+
let end = (pair[1] - base) as usize;
161+
let range_start = block * FL_CHUNK_SIZE;
162+
f(
163+
&packed[start / size_of::<T>()..end / size_of::<T>()],
164+
(end - start) / 128,
165+
range_start..(range_start + FL_CHUNK_SIZE).min(padded_len),
166+
);
167+
}
168+
}
169+
129170
/// Decode the blocks between validated `offsets` into `output`.
130171
fn decode_blocks<T: BitPackedUnpack>(
131172
array: ArrayView<'_, BitPacked>,
@@ -600,4 +641,47 @@ mod tests {
600641
assert_arrays_eq!(array, expected, &mut ctx);
601642
Ok(())
602643
}
644+
645+
/// FoR fuses with a blocked child that starts within its first block, holds zero and native
646+
/// width blocks and has encoded offsets.
647+
#[rstest]
648+
#[case::full_blocks(0, 4096)]
649+
#[case::partial_first_and_last(17, 4000)]
650+
#[case::one_value_header(1023, 2050)]
651+
fn for_fuses_blocked_child(
652+
#[values(PType::U8, PType::I16, PType::U32, PType::I64)] ptype: PType,
653+
#[case] offset: u16,
654+
#[case] len: usize,
655+
#[values(false, true)] chunked: bool,
656+
) -> VortexResult<()> {
657+
let mut ctx = SESSION.create_execution_ctx();
658+
let (array, values) = variable(ptype, offset, len, true)?;
659+
let num_chunks = (usize::from(offset) + len).div_ceil(FL_CHUNK_SIZE);
660+
match_each_integer_ptype!(ptype, |T| {
661+
let references: Vec<T> = (0..num_chunks)
662+
.map(|chunk| AsPrimitive::<T>::as_(1_000_003u64 * (chunk as u64 + 1)))
663+
.collect();
664+
let expected = PrimitiveArray::from_iter(
665+
values.as_slice::<T>().iter().enumerate().map(|(i, value)| {
666+
let chunk = if chunked {
667+
(usize::from(offset) + i) / FL_CHUNK_SIZE
668+
} else {
669+
0
670+
};
671+
value.wrapping_add(references[chunk])
672+
}),
673+
);
674+
let array = if chunked {
675+
FoR::try_new_chunked(
676+
array.into_array(),
677+
PrimitiveArray::from_iter(references).into_array(),
678+
offset,
679+
)?
680+
} else {
681+
FoR::try_new(array.into_array(), references[0].into())?
682+
};
683+
assert_arrays_eq!(array, expected, &mut ctx);
684+
});
685+
Ok(())
686+
}
603687
}

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@
44
mod blocked;
55
mod global;
66

7+
pub(crate) use blocked::execute_block_offsets;
8+
pub(crate) use blocked::for_each_packed_block;
79
pub use blocked::unpack_array_blocked;
810
pub(crate) use blocked::unpack_into_primitive_builder_blocked;
911
pub use blocked::unpack_single_blocked;

‎encodings/fastlanes/src/for_/array/for_decompress.rs‎

Lines changed: 34 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,7 @@
44
use std::iter;
55
use std::mem;
66
use std::mem::MaybeUninit;
7+
use std::ops::Range;
78

89
use fastlanes::BitPacking;
910
use fastlanes::FoR;
@@ -30,14 +31,15 @@ use vortex_compute::lane_kernels::IndexedSinkExt;
3031
use vortex_compute::lane_kernels::IndexedSourceExt;
3132
use vortex_error::VortexExpect;
3233
use vortex_error::VortexResult;
33-
use vortex_error::vortex_bail;
3434
use vortex_error::vortex_err;
3535

3636
use crate::BitPacked;
3737
use crate::BitPackedArrayExt;
3838
use crate::BitWidthsView;
3939
use crate::FL_CHUNK_SIZE;
4040
use crate::FoRArray;
41+
use crate::bitpack_decompress::execute_block_offsets;
42+
use crate::bitpack_decompress::for_each_packed_block;
4143
use crate::for_::array::FoRArrayExt;
4244
use crate::for_::array::FoRArraySlotsExt;
4345
use crate::unpack_iter::for_each_packed_chunk;
@@ -284,7 +286,7 @@ fn fused_unpack<
284286

285287
// SAFETY: `unpack_chunks` initializes every value in this range.
286288
let output = unsafe { uninit_range.slice_uninit_mut(0, len) };
287-
unpack_chunks(bp, &chunk_reference, output)?;
289+
unpack_chunks(bp, &chunk_reference, output, ctx)?;
288290

289291
if let Some(patches) = bp.patches() {
290292
let offset = usize::from(bp.offset());
@@ -310,37 +312,43 @@ fn unpack_chunks<
310312
bp: ArrayView<'_, BitPacked>,
311313
chunk_reference: impl Fn(usize) -> T,
312314
output: &mut [MaybeUninit<T>],
315+
ctx: &mut ExecutionCtx,
313316
) -> VortexResult<()> {
314317
let offset = usize::from(bp.offset());
315-
let BitWidthsView::Global(bit_width) = bp.bit_widths() else {
316-
vortex_bail!("BitPacked array has per-block bit widths");
317-
};
318-
let bit_width = bit_width as usize;
319318
// SAFETY: `T::Physical` is `T` with the same size and alignment, and the unpack is the same
320319
// wrapping addition in two's complement whichever signedness `T` has.
321320
let output =
322321
unsafe { mem::transmute::<&mut [MaybeUninit<T>], &mut [MaybeUninit<T::Physical>]>(output) };
323322
let mut scratch = [const { MaybeUninit::<T::Physical>::uninit() }; FL_CHUNK_SIZE];
324-
for_each_packed_chunk::<T, _>(
325-
bp.packed_slice::<T::Physical>(),
326-
bit_width,
327-
offset,
328-
bp.len(),
329-
|packed, range| {
330-
let reference = chunk_reference(range.start / FL_CHUNK_SIZE).as_();
331-
// `range` counts from the start of the first chunk, and the output starts at `offset`.
332-
let skip = offset.saturating_sub(range.start);
333-
let dst = &mut output[range.start + skip - offset..range.end - offset];
334-
if dst.len() == FL_CHUNK_SIZE {
335-
// SAFETY: `packed` holds one chunk at `bit_width` and `dst` has room for a chunk.
336-
unsafe { unfor_pack_into(bit_width, packed, reference, dst) };
337-
} else {
338-
// SAFETY: as above, with `scratch` as the destination.
339-
unsafe { unfor_pack_into(bit_width, packed, reference, &mut scratch) };
340-
dst.copy_from_slice(&scratch[skip..range.len()]);
341-
}
342-
},
343-
)
323+
let mut unpack_chunk = |packed: &[T::Physical], bit_width: usize, range: Range<usize>| {
324+
let reference = chunk_reference(range.start / FL_CHUNK_SIZE).as_();
325+
// `range` counts from the start of the first chunk, and the output starts at `offset`.
326+
let skip = offset.saturating_sub(range.start);
327+
let dst = &mut output[range.start + skip - offset..range.end - offset];
328+
if dst.len() == FL_CHUNK_SIZE {
329+
// SAFETY: `packed` holds one chunk at `bit_width` and `dst` has room for a chunk.
330+
unsafe { unfor_pack_into(bit_width, packed, reference, dst) };
331+
} else {
332+
// SAFETY: as above, with `scratch` as the destination.
333+
unsafe { unfor_pack_into(bit_width, packed, reference, &mut scratch) };
334+
dst.copy_from_slice(&scratch[skip..range.len()]);
335+
}
336+
};
337+
let packed = bp.packed_slice::<T::Physical>();
338+
match bp.bit_widths() {
339+
BitWidthsView::Global(bit_width) => {
340+
let bit_width = usize::from(bit_width);
341+
for_each_packed_chunk::<T, _>(packed, bit_width, offset, bp.len(), |packed, range| {
342+
unpack_chunk(packed, bit_width, range)
343+
})
344+
}
345+
BitWidthsView::Blocked(offsets) => {
346+
// The validated offsets bound every block to its bit width within `packed`.
347+
let offsets = execute_block_offsets(bp, offsets, ctx)?;
348+
for_each_packed_block::<T, _>(packed, &offsets, offset, bp.len(), unpack_chunk);
349+
Ok(())
350+
}
351+
}
344352
}
345353

346354
/// Unpack one chunk into `dst` and add `reference` to every value.

0 commit comments

Comments
 (0)