Skip to content

Commit 812de38

Browse files
authored
Encode/Decode Kernels for BlockedFoR (#10118)
Stacked on #10105. ## Summary Adds an encoder that picks one reference per 1024-element chunk, and a fused decode for chunked FoR over BitPacked. No wire format changes: arrays with varying references still can't be serialized until the next PR. ## Encoder `FoR::encode_chunked(array, ctx)` uses the same rule as `FoR::encode`, applied per chunk: - Each chunk's reference is the minimum of its valid values, so every encoded value is small and non-negative. Null slots don't count towards the minimum. - Null rows encode as 0, as in `FoR::encode`. - The minimum and the subtraction run per chunk while it is in cache, without branches. Each value is masked with all ones or all zeros from its validity bit, over fixed 64-value blocks, so both loops vectorize at every integer width. I checked the aarch64 assembly: `umin`/`smin` and `sub` at `.8b`/`.8h`/`.4s`/`.2d`, with no per-value branches. - A chunk with no valid values reuses the previous chunk's reference (or the first valid reference at the start), so the references compress into runs. - The references are a plain primitive child and the offset is 0. Compressing the references is left to the compressor scheme. ```text chunk 0 values: 1_000_000 .. 1_000_900 → reference 1_000_000, encoded 0..900 chunk 1 values: all null → reference 1_000_000, encoded 0 chunk 2 values: 9_000_000 .. 9_000_950 → reference 9_000_000, encoded 0..950 ``` Encoding, `cargo bench -p vortex-fastlanes --bench for_encode`, median per iteration on an M5 Max with 512 KiB of input (128Ki `u32` or 64Ki `i64` values): | | `FoR::encode` | `FoR::encode_chunked` | |---|---|---| | u32, non-null | 13.4 µs | 10.3 µs | | i64, non-null | 18.0 µs | 12.5 µs | | u32, 10% null | 112 µs | 27.6 µs | | i64, 10% null | 61.5 µs | 25.0 µs | ## Decode `decompress_many_refs` now dispatches like `decompress_one_ref`: - **Fused**: unsigned arrays whose `encoded` child is `BitPacked` with the same offset as the FoR. For each packed chunk it calls `unchecked_unfor_pack` with that chunk's reference, writing full chunks straight into the output and partial first/last chunks through a scratch buffer. Patch values are added to the reference of the chunk they fall in. - **Unfused** (`add_references`): everything else. It decodes `encoded`, then adds each chunk's reference. A uniquely owned buffer is updated in place. A shared one, as when `encoded` is a plain primitive child, gets the references added while it is copied, in one pass. Copying first and then adding made this path 2.2× slower than single-reference decode. A BitPacked child with patches slices lazily into `Slice(BitPacked)`, so sliced arrays with patches take the unfused path. Single-reference FoR behaves the same way today. Decoding, `--bench for_decode`, same machine and input size. Every chunk spans the same range, so both encodings pack at 7 bits and the difference is the cost of the per-chunk references: | | one reference | per-chunk references | |---|---|---| | u32, primitive child | 8.46 µs | 8.71 µs | | i64, primitive child | 8.46 µs | 8.50 µs | | u32, BitPacked child (fused) | 9.58 µs | 9.67 µs | | i64, BitPacked child (unfused) | 19.1 µs | 19.2 µs | Single-reference decode is as fast as it was before #10105. On aarch64, the per-chunk reference adds compile to four 128-bit `add.4s`/`add.2d` per iteration, and fused decode calls the same `unchecked_unfor_pack` kernel as single-reference decode. ## Benchmarks `for_encode` and `for_decode` cover `u32` and `i64` inputs of 256 KiB and 512 KiB. They carry `#[cpu_features]`, so CodSpeed measures them on the walltime legs instead of in simulation. Locally, every case takes 4–112 µs per iteration. ## CUDA CUDA FoR decoding now returns an error for per-chunk references instead of falling back to the CPU. --------- Signed-off-by: Matt Katz <[email protected]>
1 parent e868676 commit 812de38

9 files changed

Lines changed: 828 additions & 139 deletions

File tree

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎encodings/fastlanes/Cargo.toml‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@ rand = { workspace = true }
4040
rstest = { workspace = true }
4141
vortex-alp = { path = "../alp" }
4242
vortex-array = { workspace = true, features = ["_test-harness"] }
43+
vortex-bench-support = { workspace = true }
4344
vortex-fastlanes = { path = ".", features = ["_test-harness"] }
4445

4546
[features]
@@ -71,3 +72,11 @@ harness = false
7172
name = "cast_bitpacked"
7273
harness = false
7374
required-features = ["_test-harness"]
75+
76+
[[bench]]
77+
name = "for_encode"
78+
harness = false
79+
80+
[[bench]]
81+
name = "for_decode"
82+
harness = false
Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Benchmarks decoding a FoR array with a reference per 1024-element chunk, over a primitive child
5+
//! 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.
7+
//!
8+
//! Every benchmark carries `#[cpu_features]`, so it is measured on each walltime CPU-feature leg
9+
//! rather than in simulation: the loops under test are auto-vectorized, so the build decides
10+
//! their speed.
11+
//!
12+
//! Run with `cargo bench -p vortex-fastlanes --bench for_decode`.
13+
14+
#![expect(clippy::unwrap_used)]
15+
16+
use std::sync::LazyLock;
17+
18+
use divan::Bencher;
19+
use divan::counter::ItemsCount;
20+
use mimalloc::MiMalloc;
21+
use vortex_array::ArrayRef;
22+
use vortex_array::IntoArray;
23+
use vortex_array::VortexSessionExecute;
24+
use vortex_array::arrays::PrimitiveArray;
25+
use vortex_array::dtype::NativePType;
26+
use vortex_array::validity::Validity;
27+
use vortex_buffer::Buffer;
28+
use vortex_fastlanes::BitPacked;
29+
use vortex_fastlanes::FoR;
30+
use vortex_fastlanes::FoRArraySlotsExt;
31+
use vortex_session::VortexSession;
32+
33+
#[global_allocator]
34+
static GLOBAL: MiMalloc = MiMalloc;
35+
36+
fn main() {
37+
divan::main();
38+
}
39+
40+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
41+
let session = vortex_array::array_session();
42+
vortex_fastlanes::initialize(&session);
43+
session
44+
});
45+
46+
/// Bytes of values per input array.
47+
const INPUT_BYTES: &[usize] = &[512 * 1024];
48+
49+
/// Enough bits for the values' spread above their minimum.
50+
const BIT_WIDTH: u8 = 7;
51+
52+
fn values<T: NativePType + TryFrom<usize>>(len: usize) -> Buffer<T> {
53+
(0..len)
54+
.map(|i| T::try_from(1000 + (i * 7919) % 100).ok().unwrap())
55+
.collect()
56+
}
57+
58+
fn for_array<T: NativePType + TryFrom<usize>>(len: usize, bitpacked: bool) -> ArrayRef {
59+
let mut ctx = SESSION.create_execution_ctx();
60+
let array = PrimitiveArray::new(values::<T>(len), Validity::NonNullable);
61+
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();
66+
FoR::try_new_chunked(packed.into_array(), for_array.references().clone(), 0)
67+
.unwrap()
68+
.into_array()
69+
}
70+
71+
fn run<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize, bitpacked: bool) {
72+
let len = bytes / size_of::<T>();
73+
let array = for_array::<T>(len, bitpacked);
74+
bencher
75+
.counter(ItemsCount::new(len))
76+
.with_inputs(|| (&array, SESSION.create_execution_ctx()))
77+
.bench_refs(|(array, ctx)| (*array).clone().execute::<PrimitiveArray>(ctx).unwrap());
78+
}
79+
80+
#[vortex_bench_support::cpu_features]
81+
#[divan::bench(types = [i64], args = INPUT_BYTES)]
82+
fn decode_chunked<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize) {
83+
run::<T>(bencher, bytes, false);
84+
}
85+
86+
#[vortex_bench_support::cpu_features]
87+
#[divan::bench(types = [u32, i64], args = INPUT_BYTES)]
88+
fn decode_bitpacked_chunked<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize) {
89+
run::<T>(bencher, bytes, true);
90+
}
Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Benchmarks `FoR::encode_chunked`, which subtracts a reference per 1024-element chunk, with and
5+
//! without nulls.
6+
//!
7+
//! Every benchmark carries `#[cpu_features]`, so it is measured on each walltime CPU-feature leg
8+
//! rather than in simulation: the loops under test are auto-vectorized, so the build decides
9+
//! their speed.
10+
//!
11+
//! Run with `cargo bench -p vortex-fastlanes --bench for_encode`.
12+
13+
#![expect(clippy::unwrap_used)]
14+
15+
use std::sync::LazyLock;
16+
17+
use divan::Bencher;
18+
use divan::counter::ItemsCount;
19+
use mimalloc::MiMalloc;
20+
use vortex_array::VortexSessionExecute;
21+
use vortex_array::arrays::PrimitiveArray;
22+
use vortex_array::dtype::NativePType;
23+
use vortex_array::validity::Validity;
24+
use vortex_buffer::Buffer;
25+
use vortex_fastlanes::FoR;
26+
use vortex_session::VortexSession;
27+
28+
#[global_allocator]
29+
static GLOBAL: MiMalloc = MiMalloc;
30+
31+
fn main() {
32+
divan::main();
33+
}
34+
35+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
36+
let session = vortex_array::array_session();
37+
vortex_fastlanes::initialize(&session);
38+
session
39+
});
40+
41+
/// Bytes of values per input array.
42+
const INPUT_BYTES: &[usize] = &[512 * 1024];
43+
44+
/// Values that step up by 1000 every chunk, with a small spread within each chunk.
45+
fn values<T: NativePType + TryFrom<usize>>(len: usize) -> Buffer<T> {
46+
(0..len)
47+
.map(|i| {
48+
T::try_from((i / 1024) * 1000 + (i * 7919) % 100)
49+
.ok()
50+
.unwrap()
51+
})
52+
.collect()
53+
}
54+
55+
fn validity(len: usize, nullable: bool) -> Validity {
56+
if nullable {
57+
Validity::from_iter((0..len).map(|i| i % 10 != 0))
58+
} else {
59+
Validity::NonNullable
60+
}
61+
}
62+
63+
fn run<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize, nullable: bool) {
64+
let len = bytes / size_of::<T>();
65+
let buffer = values::<T>(len);
66+
let validity = validity(len, nullable);
67+
bencher
68+
.counter(ItemsCount::new(len))
69+
// `encode_chunked` takes the array by value, so each iteration encodes a fresh one.
70+
.with_inputs(|| PrimitiveArray::new(buffer.clone(), validity.clone()))
71+
.bench_local_values(|array| {
72+
FoR::encode_chunked(array, &mut SESSION.create_execution_ctx()).unwrap()
73+
});
74+
}
75+
76+
#[vortex_bench_support::cpu_features]
77+
#[divan::bench(types = [i64], args = INPUT_BYTES)]
78+
fn encode_chunked<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize) {
79+
run::<T>(bencher, bytes, false);
80+
}
81+
82+
#[vortex_bench_support::cpu_features]
83+
#[divan::bench(types = [i64], args = INPUT_BYTES)]
84+
fn encode_chunked_nullable<T: NativePType + TryFrom<usize>>(bencher: Bencher, bytes: usize) {
85+
run::<T>(bencher, bytes, true);
86+
}

0 commit comments

Comments
 (0)