Skip to content

Commit 583a985

Browse files
authored
Blocked BitPacked: decode blocked bitwidths (#10202)
Tracking Issue: #10167 ## Summary Adds support for decoding `BitPacked` arrays with blocked bitwidths. Now each public function that decodes bitpacked arrays with global bitwidths has a version for blocked bitwidths. | Global width | Blocked | |---|---| | `unpack_array(array, ctx)` | `unpack_array_blocked(array, offsets, ctx)` | | `unpack_primitive_array` | `unpack_primitive_array_blocked` | | `unpack_into_primitive_builder` | `unpack_into_primitive_builder_blocked` | | `unpack_single(array, index)` | `unpack_single_blocked(array, offsets, index, ctx)` | Callers choose between them by matching on `bit_widths()`. There is no blocked `unpack_map_into_builder`: its only caller, the widening `CastKernel`, declines blocked arrays, so the mapped path would only run in tests. ## Design #10004 only checks block boundary values in debug builds, so the decoder checks them itself: - Bulk decode casts the offsets child to `u64` and executes it once, checks that it holds one boundary per block plus a trailing one, and validates every boundary before writing to the builder. A single offset type keeps one copy of the block loop per value type, for 8 bytes per 1024 values. Each block must be a whole number of 128-byte rows, no wider than the array's type, and the boundaries must span the packed buffer. - `scalar_at` reads only the selected block's boundaries, directly for host primitive offsets and through `execute_scalar` otherwise, and validates just that block. Both use `block_range` in `bitpacking/array/mod.rs`, which `validate_primitive_offsets` now also uses. Boundaries are relative to the first one, which may be nonzero. Full blocks unpack straight into the output, like the global decoder's full chunks. A partial first or last block unpacks into one 1024-value scratch block. --------- Signed-off-by: Matt Katz <[email protected]>
1 parent 9d5a844 commit 583a985

9 files changed

Lines changed: 799 additions & 34 deletions

File tree

‎encodings/fastlanes/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,10 @@ harness = false
5555
name = "bitpacking_filter"
5656
harness = false
5757

58+
[[bench]]
59+
name = "bitpack_blocked_decompress"
60+
harness = false
61+
5862
[[bench]]
5963
name = "canonicalize_bench"
6064
harness = false
Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Benchmarks decoding a `BitPacked` array whose 1024-value blocks each have their own bit width.
5+
6+
#![expect(clippy::unwrap_used)]
7+
8+
use std::sync::LazyLock;
9+
10+
use divan::Bencher;
11+
use divan::counter::ItemsCount;
12+
use mimalloc::MiMalloc;
13+
use num_traits::AsPrimitive;
14+
use vortex_array::VortexSessionExecute;
15+
use vortex_array::arrays::PrimitiveArray;
16+
use vortex_array::dtype::NativePType;
17+
use vortex_fastlanes::BitPackedArraySlotsExt;
18+
use vortex_fastlanes::bitpack_compress::bitpack_encode_blocked;
19+
use vortex_fastlanes::bitpack_decompress::unpack_array_blocked;
20+
use vortex_session::VortexSession;
21+
22+
#[global_allocator]
23+
static GLOBAL: MiMalloc = MiMalloc;
24+
25+
fn main() {
26+
divan::main();
27+
}
28+
29+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
30+
let session = vortex_array::array_session();
31+
vortex_fastlanes::initialize(&session);
32+
session
33+
});
34+
35+
/// 64 blocks per array: shorter iterations are noisy on the walltime legs.
36+
const NUM_BLOCKS: usize = 64;
37+
38+
#[vortex_bench_support::cpu_features]
39+
#[divan::bench(types = [u32, u64])]
40+
fn bitpack_blocked_decompress<T>(bencher: Bencher)
41+
where
42+
T: NativePType,
43+
u64: AsPrimitive<T>,
44+
{
45+
// Block widths cycle from 1 to 16 bits, so the blocks take different unpacking kernels.
46+
let bit_widths: Vec<u8> = (1..=16).cycle().take(NUM_BLOCKS).collect();
47+
let values = PrimitiveArray::from_iter(bit_widths.iter().flat_map(|&bit_width| {
48+
(0..1024u64)
49+
.map(move |i| AsPrimitive::<T>::as_(i.wrapping_mul(7919) & ((1 << bit_width) - 1)))
50+
}));
51+
let array = bitpack_encode_blocked(
52+
&values,
53+
&bit_widths,
54+
Some(0),
55+
&mut SESSION.create_execution_ctx(),
56+
)
57+
.unwrap();
58+
let offsets = array.block_offsets().unwrap().clone();
59+
60+
bencher.counter(ItemsCount::new(array.len())).bench(|| {
61+
unpack_array_blocked(
62+
array.as_view(),
63+
&offsets,
64+
&mut SESSION.create_execution_ctx(),
65+
)
66+
.unwrap()
67+
});
68+
}

0 commit comments

Comments
 (0)