Skip to content

Commit 7286721

Browse files
authored
perf: specialize whole-array sums for run-end arrays (#9823)
## Summary Computes whole-array `Sum` and `SumV2` directly from primitive run values and lengths, avoiding full decoding. Grouped sums and decimals use the existing fallback. ## Changes Reuses cached validity indices or scans the bitmap within the array's slice. Adds coverage for slice boundaries, nulls, overflow, and NaNs, plus one whole-array benchmark. Weighted floating-point sums can round differently from repeated addition, and the shared signed-overflow limitations remain unchanged. Tests and benchmarks have not been rerun for this revision. --------- Signed-off-by: "Connor Tsui" <[email protected]>
1 parent 0a2d04c commit 7286721

9 files changed

Lines changed: 725 additions & 1 deletion

File tree

‎encodings/runend/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -58,3 +58,7 @@ harness = false
5858
[[bench]]
5959
name = "run_end_filter"
6060
harness = false
61+
62+
[[bench]]
63+
name = "run_end_sum"
64+
harness = false
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
#![expect(clippy::unwrap_used)]
5+
6+
use std::sync::LazyLock;
7+
8+
use divan::Bencher;
9+
use vortex_array::ArrayRef;
10+
use vortex_array::IntoArray;
11+
use vortex_array::VortexSessionExecute;
12+
use vortex_array::aggregate_fn::fns::sum_v2::sum_v2;
13+
use vortex_array::arrays::PrimitiveArray;
14+
use vortex_runend::RunEnd;
15+
use vortex_session::VortexSession;
16+
17+
const LEN: usize = 2_048;
18+
const RUN_LENGTH: usize = 64;
19+
20+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
21+
let session = vortex_array::array_session();
22+
vortex_runend::initialize(&session);
23+
session
24+
});
25+
26+
fn main() {
27+
LazyLock::force(&SESSION);
28+
divan::main();
29+
}
30+
31+
fn runend_with_null_runs() -> ArrayRef {
32+
let ends =
33+
PrimitiveArray::from_iter((RUN_LENGTH..=LEN).step_by(RUN_LENGTH).map(|end| end as u64));
34+
let values = PrimitiveArray::from_option_iter(
35+
(0..ends.len()).map(|index| (index % 5 != 0).then_some(i32::try_from(index).unwrap())),
36+
);
37+
38+
RunEnd::try_new(
39+
ends.into_array(),
40+
values.into_array(),
41+
&mut SESSION.create_execution_ctx(),
42+
)
43+
.unwrap()
44+
.into_array()
45+
}
46+
47+
#[divan::bench]
48+
fn whole_array_sum_partially_valid(bencher: Bencher) {
49+
let array = runend_with_null_runs();
50+
bencher
51+
.with_inputs(|| SESSION.create_execution_ctx())
52+
.bench_refs(|ctx| sum_v2(&array, ctx).unwrap());
53+
}

‎encodings/runend/src/compute/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ pub(crate) mod filter;
88
pub(crate) mod is_constant;
99
pub(crate) mod is_sorted;
1010
pub(crate) mod min_max;
11+
pub(crate) mod sum;
1112
pub(crate) mod take;
1213
pub(crate) mod take_from;
1314

Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Whole-array sum dispatch and scalar partial construction.
5+
//!
6+
//! Run traversal and arithmetic are implemented in [`super::runs`].
7+
8+
use std::ops::Range;
9+
10+
use vortex_array::ArrayRef;
11+
use vortex_array::ExecutionCtx;
12+
use vortex_array::aggregate_fn::AggregateFnRef;
13+
use vortex_array::aggregate_fn::NumericalAggregateOpts;
14+
use vortex_array::aggregate_fn::fns::sum::Sum;
15+
use vortex_array::aggregate_fn::fns::sum_v2::SumV2;
16+
use vortex_array::aggregate_fn::kernels::DynAggregateKernel;
17+
use vortex_array::arrays::PrimitiveArray;
18+
use vortex_array::dtype::DType;
19+
use vortex_array::dtype::NativePType;
20+
use vortex_array::dtype::Nullability::Nullable;
21+
use vortex_array::dtype::UnsignedPType;
22+
use vortex_array::match_each_native_ptype;
23+
use vortex_array::match_each_unsigned_integer_ptype;
24+
use vortex_array::scalar::PValue;
25+
use vortex_array::scalar::Scalar;
26+
use vortex_error::VortexExpect;
27+
use vortex_error::VortexResult;
28+
use vortex_mask::Mask;
29+
30+
use super::runs::add_float_run;
31+
use super::runs::add_signed_run;
32+
use super::runs::add_unsigned_run;
33+
use super::runs::sum_range;
34+
use crate::RunEnd;
35+
use crate::RunEndArrayExt;
36+
use crate::RunEndArraySlotsExt;
37+
38+
/// Whole-array primitive sum kernel for [`RunEnd`].
39+
#[derive(Debug)]
40+
pub(crate) struct RunEndSumKernel;
41+
42+
impl DynAggregateKernel for RunEndSumKernel {
43+
fn aggregate(
44+
&self,
45+
aggregate_fn: &AggregateFnRef,
46+
batch: &ArrayRef,
47+
ctx: &mut ExecutionCtx,
48+
) -> VortexResult<Option<Scalar>> {
49+
if !batch.dtype().is_primitive() {
50+
return Ok(None);
51+
}
52+
53+
let Some(options) = aggregate_fn
54+
.as_opt::<Sum>()
55+
.or_else(|| aggregate_fn.as_opt::<SumV2>())
56+
.copied()
57+
else {
58+
return Ok(None);
59+
};
60+
61+
let Some(array) = batch.as_opt::<RunEnd>() else {
62+
return Ok(None);
63+
};
64+
65+
if array.is_empty() {
66+
return Ok(Some(empty_partial(aggregate_fn, batch.dtype())?));
67+
}
68+
69+
let validity = array
70+
.values()
71+
.validity()?
72+
.execute_mask(array.values().len(), ctx)?;
73+
if validity.all_false() {
74+
return Ok(Some(empty_partial(aggregate_fn, batch.dtype())?));
75+
}
76+
77+
let ends = array.ends().clone().execute::<PrimitiveArray>(ctx)?;
78+
let values = array.values().clone().execute::<PrimitiveArray>(ctx)?;
79+
let range = array.offset()..array.offset() + batch.len();
80+
let (sum, is_empty) = sum_primitive_runs(&ends, &values, &validity, range, options);
81+
82+
Ok(Some(partial_scalar(aggregate_fn, sum, is_empty)?))
83+
}
84+
}
85+
86+
/// Select run-end and value types, widening sums to `u64`, `i64`, or `f64`.
87+
///
88+
/// Returns `(sum, is_empty)` with overflow represented by a null scalar. Input requirements and
89+
/// empty-input semantics are defined in [`super::runs`].
90+
fn sum_primitive_runs(
91+
ends: &PrimitiveArray,
92+
values: &PrimitiveArray,
93+
validity: &Mask,
94+
range: Range<usize>,
95+
options: NumericalAggregateOpts,
96+
) -> (Scalar, bool) {
97+
match_each_unsigned_integer_ptype!(ends.ptype(), |E| {
98+
let ends = ends.as_slice::<E>();
99+
100+
match_each_native_ptype!(values.ptype(),
101+
unsigned: |T| {
102+
sum_typed_runs(ends, values.as_slice::<T>(), validity, range, add_unsigned_run::<T>)
103+
},
104+
signed: |T| {
105+
sum_typed_runs(ends, values.as_slice::<T>(), validity, range, add_signed_run::<T>)
106+
},
107+
floating: |T| {
108+
sum_typed_runs(ends, values.as_slice::<T>(), validity, range, |sum, value, len| {
109+
add_float_run(sum, value, len, options.skip_nans)
110+
})
111+
}
112+
)
113+
})
114+
}
115+
116+
/// Convert the reduction's sum to a nullable scalar, preserving its empty-input flag.
117+
fn sum_typed_runs<E: UnsignedPType, T: NativePType, A: NativePType + Into<PValue>>(
118+
ends: &[E],
119+
values: &[T],
120+
validity: &Mask,
121+
range: Range<usize>,
122+
add_run: impl Fn(A, T, usize) -> Option<A>,
123+
) -> (Scalar, bool) {
124+
let (sum, is_empty) = sum_range(ends, values, validity, range, add_run);
125+
let sum = match sum {
126+
Some(sum) => Scalar::primitive(sum, Nullable),
127+
None => Scalar::null(DType::Primitive(A::PTYPE, Nullable)),
128+
};
129+
130+
(sum, is_empty)
131+
}
132+
133+
fn empty_partial(aggregate_fn: &AggregateFnRef, dtype: &DType) -> VortexResult<Scalar> {
134+
let sum_dtype = aggregate_fn
135+
.return_dtype(dtype)
136+
.vortex_expect("The primitive sum kernel accepts only supported dtypes");
137+
138+
partial_scalar(aggregate_fn, Scalar::zero_value(&sum_dtype), true)
139+
}
140+
141+
/// Wrap the sum in the aggregate's partial representation without finalizing empty inputs.
142+
fn partial_scalar(
143+
aggregate_fn: &AggregateFnRef,
144+
sum: Scalar,
145+
is_empty: bool,
146+
) -> VortexResult<Scalar> {
147+
if aggregate_fn.is::<SumV2>() {
148+
SumV2::partial_from_sum(sum, is_empty)
149+
} else {
150+
Ok(sum)
151+
}
152+
}
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Whole-array primitive sums over run-end encoded arrays.
5+
//!
6+
//! Both [`Sum`] and [`SumV2`] reduce valid run values and lengths without expanding the runs. Each
7+
//! aggregate retains its own partial representation and empty-input semantics. Grouped sums and
8+
//! decimal inputs use the fallback.
9+
//!
10+
//! Floating-point multiplication can round differently from repeated addition, as with constant sums.
11+
//!
12+
//! [`Sum`]: vortex_array::aggregate_fn::fns::sum::Sum
13+
//! [`SumV2`]: vortex_array::aggregate_fn::fns::sum_v2::SumV2
14+
15+
mod kernel;
16+
pub(crate) use kernel::RunEndSumKernel;
17+
18+
mod runs;
19+
20+
#[cfg(test)]
21+
mod tests;

0 commit comments

Comments
 (0)