Skip to content

Commit 61ff28d

Browse files
authored
perf(fastlanes): answer BitPacked compare and between from the bit width, between through the fused kernel (#10559)
## Summary - Tracking Issue: #10396 BitPacked knows its bit width W, so a packed value is in `[0, 2^W - 1]` and anything else is a patch. A predicate that is monotone in the value and agrees at both ends of that range is decided for every packed value without unpacking, which is the fast path from #8013 (ty @joseph-isaacs), here extended to between and to patches. Vortex builds for baseline x86-64 by default, where the between path also paid for two compares per value through `stream_predicate`. ## Changes - New `packed_range.rs`: the range of packed values for a bit width, and a constant result with the patched positions fixed up by a dynamic predicate, so it stays one instance per type. Without patches or nulls the result is a `ConstantArray` and nothing is unpacked. - `compare`: ordering operators are decided when the constant lies outside the packed range; `Eq`/`NotEq` only when it is outside the range or W = 0. - `between`: the same rule on both endpoints, otherwise through the fused `unpack_cmp` kernel with the bounds made inclusive and clamped to the packed range, so one unsigned compare of the offset per value regardless of strictness. - Tests for both against the decoded reference, including patches, nulls, W = 0 and full width. ## Benchmarks Zen 5 laptop, divan medians (minimum over 3 alternating rounds), ratio = develop / branch. Kernel-only counts from `perf stat` as the difference of `--sample-size 400` and `200`. | bench | default | target-cpu=native | |---|---|---| | `fast_{eq,lt}_out_of_range`, 64K | 8.8 to 11.8x | 4.9 to 5.6x | | `fast_{eq,lt}_out_of_range`, 1K | 1.09 to 1.14x | 0.97 to 1.01x | | `new_bp_prim_test_between` i16/i32 | 2.0 to 6.2x | 1.3 to 3.3x | | `new_bp_prim_test_between` i64 | 1.3 to 1.55x | 1.26 to 1.97x | | `new_alp_prim_test_between` | 1.24 to 3.7x | 1.18 to 2.5x | | `baseline_{eq,lt}`, `bitpack_compare_sweep` | 0.97 to 1.03x | 0.99 to 1.03x | | `new_raw_prim_test_between` (unaffected) | 1.01 to 1.03x | 0.99 to 1.01x | The out-of-range compares now cost the same ~500 ns at any length, which is the fixed `execute` overhead. Kernel instructions drop 2.67x for those and 3.84x for bitpacked between; the in-range compare executes the same instruction count as develop. --------- Signed-off-by: mightsleep <[email protected]> Signed-off-by: Robert Kruszewski <[email protected]>
1 parent 3ded4dd commit 61ff28d

5 files changed

Lines changed: 472 additions & 33 deletions

File tree

‎encodings/fastlanes/src/bitpacking/compute/between.rs‎

Lines changed: 181 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -9,11 +9,17 @@
99
//!
1010
//! [`BitPackedArray`]: crate::BitPackedArray
1111
12+
use fastlanes::BitPacking;
13+
use fastlanes::BitPackingCompare;
14+
use fastlanes::FastLanesComparable;
15+
use num_traits::AsPrimitive;
16+
use num_traits::WrappingSub;
1217
use vortex_array::ArrayRef;
1318
use vortex_array::ArrayView;
1419
use vortex_array::ExecutionCtx;
1520
use vortex_array::dtype::NativePType;
1621
use vortex_array::dtype::Nullability;
22+
use vortex_array::dtype::PhysicalPType;
1723
use vortex_array::match_each_integer_ptype;
1824
use vortex_array::scalar_fn::fns::between::BetweenKernel;
1925
use vortex_array::scalar_fn::fns::between::BetweenOptions;
@@ -23,7 +29,12 @@ use vortex_error::VortexResult;
2329

2430
use crate::BitPacked;
2531
use crate::BitPackedArrayExt;
32+
use crate::BitWidthsView;
33+
use crate::bitpacking::compute::compare_fused::stream_compare_fused;
34+
use crate::bitpacking::compute::packed_range::constant_result;
35+
use crate::bitpacking::compute::packed_range::packed_range;
2636
use crate::bitpacking::compute::stream_predicate::stream_predicate;
37+
use crate::unpack_iter::BitPacked as BitPackedIter;
2738

2839
impl BetweenKernel for BitPacked {
2940
fn between(
@@ -78,7 +89,11 @@ fn between_constant_typed<T>(
7889
ctx: &mut ExecutionCtx,
7990
) -> VortexResult<ArrayRef>
8091
where
81-
T: NativePType + Copy + crate::unpack_iter::BitPacked,
92+
T: NativePType
93+
+ BitPackedIter
94+
+ FastLanesComparable<Bitpacked = <T as PhysicalPType>::Physical>
95+
+ AsPrimitive<<T as PhysicalPType>::Physical>,
96+
<T as PhysicalPType>::Physical: BitPacking + NativePType + BitPackingCompare + WrappingSub,
8297
{
8398
// Branch on strictness once at the top so each call into `between_impl` monomorphises
8499
// a single tight predicate — same shape as `Primitive::between` in `vortex-array`.
@@ -132,18 +147,73 @@ fn between_impl<T, Lo, Up>(
132147
ctx: &mut ExecutionCtx,
133148
) -> VortexResult<ArrayRef>
134149
where
135-
T: NativePType + Copy + crate::unpack_iter::BitPacked,
136-
Lo: Fn(T, T) -> bool,
137-
Up: Fn(T, T) -> bool,
150+
T: NativePType
151+
+ BitPackedIter
152+
+ FastLanesComparable<Bitpacked = <T as PhysicalPType>::Physical>
153+
+ AsPrimitive<<T as PhysicalPType>::Physical>,
154+
<T as PhysicalPType>::Physical: BitPacking + NativePType + BitPackingCompare + WrappingSub,
155+
Lo: Fn(T, T) -> bool + Copy,
156+
Up: Fn(T, T) -> bool + Copy,
138157
{
139-
stream_predicate::<T, _>(
158+
let predicate = move |v| lower_fn(lower, v) & upper_fn(v, upper);
159+
let BitWidthsView::Global(bit_width) = array.bit_widths() else {
160+
return stream_predicate::<T, _>(array, nullability, predicate, ctx);
161+
};
162+
let Some((lo, hi)) = packed_range::<T>(bit_width) else {
163+
return stream_predicate::<T, _>(array, nullability, predicate, ctx);
164+
};
165+
166+
// Both tests are monotone, so the ends of the packed range decide them.
167+
if lower_fn(lower, lo) && upper_fn(hi, upper) {
168+
return constant_result(array, true, nullability, &predicate, ctx);
169+
}
170+
if !lower_fn(lower, hi) || !upper_fn(lo, upper) {
171+
return constant_result(array, false, nullability, &predicate, ctx);
172+
}
173+
174+
// Inclusive bounds clamped to the packed range, so one kernel serves every strictness.
175+
// A strict bound at the end of `T` returned above, so the step cannot overflow.
176+
let first = if lower_fn(lower, lower) {
177+
lower
178+
} else {
179+
lower + T::one()
180+
};
181+
let first = if first.is_lt(lo) { lo } else { first };
182+
let last = if upper_fn(upper, upper) {
183+
upper
184+
} else {
185+
upper - T::one()
186+
};
187+
let last = if last.is_gt(hi) { hi } else { last };
188+
if first.is_gt(last) {
189+
return constant_result(array, false, nullability, &predicate, ctx);
190+
}
191+
192+
let kernel = offset_within::<T>(first, last);
193+
stream_compare_fused(
140194
array,
195+
bit_width,
196+
lower,
141197
nullability,
142-
|v| lower_fn(lower, v) & upper_fn(v, upper),
198+
kernel,
199+
&predicate,
143200
ctx,
144201
)
145202
}
146203

204+
/// `first <= v <= last` as one unsigned compare: values below `first` wrap around.
205+
fn offset_within<T>(first: T, last: T) -> impl Fn(T, T) -> bool + Copy
206+
where
207+
T: NativePType + PhysicalPType + AsPrimitive<<T as PhysicalPType>::Physical>,
208+
<T as PhysicalPType>::Physical: NativePType + WrappingSub + PartialOrd,
209+
{
210+
let span: <T as PhysicalPType>::Physical = (last - first).as_();
211+
let first: <T as PhysicalPType>::Physical = first.as_();
212+
move |v: T, _| {
213+
AsPrimitive::<<T as PhysicalPType>::Physical>::as_(v).wrapping_sub(&first) <= span
214+
}
215+
}
216+
147217
#[cfg(test)]
148218
mod tests {
149219
use std::sync::LazyLock;
@@ -155,13 +225,15 @@ mod tests {
155225
use vortex_array::arrays::PrimitiveArray;
156226
use vortex_array::assert_arrays_eq;
157227
use vortex_array::builtins::ArrayBuiltins;
228+
use vortex_array::scalar_fn::fns::between::BetweenKernel;
158229
use vortex_array::scalar_fn::fns::between::BetweenOptions;
159230
use vortex_array::scalar_fn::fns::between::StrictComparison;
160231
use vortex_array::validity::Validity;
161232
use vortex_buffer::BufferMut;
162233
use vortex_error::VortexResult;
163234
use vortex_session::VortexSession;
164235

236+
use crate::BitPacked;
165237
use crate::BitPackedArrayExt;
166238
use crate::BitPackedData;
167239

@@ -246,4 +318,107 @@ mod tests {
246318
assert_arrays_eq!(actual, expected, &mut ctx);
247319
Ok(())
248320
}
321+
322+
/// Bounds covering or missing `[0, 2^W - 1]` give a constant, patches and nulls still exact.
323+
#[rstest]
324+
fn decided_by_bit_width_matches_primitive(
325+
#[values(false, true)] patched: bool,
326+
#[values(false, true)] nullable: bool,
327+
) -> VortexResult<()> {
328+
let mut ctx = SESSION.create_execution_ctx();
329+
let values = (0..3000i32).map(|i| match i % 97 {
330+
0 if patched => 100_000 + i,
331+
_ => i % 128,
332+
});
333+
let prim = if nullable {
334+
PrimitiveArray::from_option_iter(
335+
values.enumerate().map(|(i, v)| (i % 11 != 0).then_some(v)),
336+
)
337+
} else {
338+
PrimitiveArray::from_iter(values)
339+
};
340+
let packed = BitPackedData::encode(&prim.clone().into_array(), 7, &mut ctx)?;
341+
assert_eq!(packed.patches().is_some(), patched);
342+
let bounds = [i32::MIN, -5, 0, 50, 127, 128, 1000];
343+
let strictness = [StrictComparison::Strict, StrictComparison::NonStrict];
344+
for (&lo, &up) in bounds
345+
.iter()
346+
.flat_map(|l| bounds.iter().map(move |u| (l, u)))
347+
{
348+
for (&lower_strict, &upper_strict) in strictness
349+
.iter()
350+
.flat_map(|l| strictness.iter().map(move |u| (l, u)))
351+
{
352+
let options = opts(lower_strict, upper_strict);
353+
let lower = ConstantArray::new(lo, prim.len()).into_array();
354+
let upper = ConstantArray::new(up, prim.len()).into_array();
355+
let got = <BitPacked as BetweenKernel>::between(
356+
packed.as_view(),
357+
&lower,
358+
&upper,
359+
&options,
360+
&mut ctx,
361+
)?
362+
.expect("between kernel must engage");
363+
// Packed values span [0, 127].
364+
let inside = |v: i32| {
365+
let above = match lower_strict {
366+
StrictComparison::Strict => lo < v,
367+
StrictComparison::NonStrict => lo <= v,
368+
};
369+
let below = match upper_strict {
370+
StrictComparison::Strict => v < up,
371+
StrictComparison::NonStrict => v <= up,
372+
};
373+
above && below
374+
};
375+
let decided = (0..=127).all(|v| inside(v) == inside(0));
376+
if !patched && !nullable {
377+
assert_eq!(got.as_constant().is_some(), decided, "{lo} {up}");
378+
}
379+
let want = prim.clone().into_array().between(lower, upper, options)?;
380+
assert_arrays_eq!(got, want, &mut ctx);
381+
}
382+
}
383+
Ok(())
384+
}
385+
386+
/// Patches past the packed width compare at full width.
387+
#[rstest]
388+
#[case(0, 1000)]
389+
#[case(1000, 1 << 26)]
390+
#[case(5, (1 << 27) - 1)]
391+
fn wide_patches_compare_exactly(#[case] lo: u64, #[case] up: u64) -> VortexResult<()> {
392+
let mut ctx = SESSION.create_execution_ctx();
393+
let values = (0..5000u64).map(|i| match i % 89 {
394+
0 => (1 << 40) + i,
395+
1 => u64::MAX - i,
396+
2 => (1 << 32) + lo,
397+
_ => (i * 7919) % (1 << 27),
398+
});
399+
let prim = PrimitiveArray::from_iter(values);
400+
let packed = BitPackedData::encode(&prim.clone().into_array(), 27, &mut ctx)?;
401+
assert!(packed.patches().is_some(), "test setup expects patches");
402+
let lower = ConstantArray::new(lo, prim.len()).into_array();
403+
let upper = ConstantArray::new(up, prim.len()).into_array();
404+
for options in [
405+
opts(StrictComparison::NonStrict, StrictComparison::NonStrict),
406+
opts(StrictComparison::Strict, StrictComparison::Strict),
407+
] {
408+
let got = <BitPacked as BetweenKernel>::between(
409+
packed.as_view(),
410+
&lower,
411+
&upper,
412+
&options,
413+
&mut ctx,
414+
)?
415+
.expect("between kernel must engage");
416+
let want = prim
417+
.clone()
418+
.into_array()
419+
.between(lower.clone(), upper.clone(), options)?;
420+
assert_arrays_eq!(got, want, &mut ctx);
421+
}
422+
Ok(())
423+
}
249424
}

0 commit comments

Comments
 (0)