Skip to content

Commit 7dd6ba4

Browse files
authored
fix(array): derive the Widen sum bound from the width of the values
Sum adds every integer type into a 64-bit sum, so values of b bits cannot overflow it within 2^(64 - b) rows, whatever the logical width. One rule replaces the fixed 2^32 bound and the special case for 64-bit logical types. Signed-off-by: Connor Tsui <[email protected]>
1 parent d4f4300 commit 7dd6ba4

1 file changed

Lines changed: 14 additions & 18 deletions

File tree

‎vortex-array/src/arrays/widen/compute/aggregate.rs‎

Lines changed: 14 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -15,15 +15,6 @@ use crate::dtype::DType;
1515
use crate::expr::stats::Stat;
1616
use crate::scalar::Scalar;
1717

18-
/// The longest batch with a 64-bit logical dtype for which [`WidenArrayAggregate`] serves [`Sum`].
19-
///
20-
/// `Sum` adds integers narrower than 64 bits in blocks and checks for overflow once per block, but
21-
/// checks 64-bit integers after every value. So only a 64-bit logical dtype is checked at other
22-
/// points than its values. Its values have at most 32 bits, and no sum of at most 2^32 of them
23-
/// leaves the 64-bit range, so neither check fires. In a longer batch, a sum can overflow and come
24-
/// back inside one block, which only the check after every value sees.
25-
const MAX_EXACT_SUM_LEN: u64 = 1 << 32;
26-
2718
/// Runs an aggregate of a [`Widen`] on its values and widens the partial to the logical dtype.
2819
///
2920
/// The values run the same accumulator code as the canonical array, so edge cases such as an empty
@@ -49,11 +40,11 @@ impl DynAggregateKernel for WidenArrayAggregate {
4940
return Ok(None);
5041
}
5142

52-
if aggregate_fn.is::<Sum>() && !is_exact_sum(aggregate_fn, batch) {
43+
let values = widen.values();
44+
if aggregate_fn.is::<Sum>() && !is_exact_sum(aggregate_fn, batch, values) {
5345
return Ok(None);
5446
}
5547

56-
let values = widen.values();
5748
let mut accumulator = aggregate_fn.accumulator(values.dtype())?;
5849
accumulator.accumulate(values, ctx)?;
5950

@@ -72,15 +63,20 @@ impl DynAggregateKernel for WidenArrayAggregate {
7263
/// It does so for an aggregate with the legacy [`Stat::Sum`] slot. Otherwise it adds each value
7364
/// to the running sum, which a batch total cannot match near the 64-bit bounds: from a running
7465
/// sum of `i64::MAX - 5`, the values `[10, -10]` overflow, but their total of zero does not.
75-
/// - The overflow checks **must** agree. A logical dtype narrower than 64 bits is summed in the
76-
/// same blocks as its values, so they always agree. A 64-bit logical dtype needs a batch of at
77-
/// most [`MAX_EXACT_SUM_LEN`] rows.
66+
/// - The sum of the batch **must not** be able to overflow. `Sum` adds every integer type into a
67+
/// 64-bit sum, but checks for overflow at different points for different widths: once per block
68+
/// for types narrower than 64 bits, and after every value for 64-bit types. A signed value of
69+
/// `b` bits lies in `[-2^(b-1), 2^(b-1))` and an unsigned one in `[0, 2^b)`, so no sum of at
70+
/// most `2^(64 - b)` of them leaves the range of `i64` or `u64`, and no check fires on either
71+
/// path.
7872
///
7973
/// Only `Sum` with `skip_nans` has the slot. Integers have no NaNs, so `skip_nans` matters here
8074
/// only because it selects the slot.
81-
fn is_exact_sum(aggregate_fn: &AggregateFnRef, batch: &ArrayRef) -> bool {
82-
let is_64_bit = matches!(batch.dtype(), DType::Primitive(ptype, _) if ptype.byte_width() == 8);
75+
fn is_exact_sum(aggregate_fn: &AggregateFnRef, batch: &ArrayRef, values: &ArrayRef) -> bool {
76+
let DType::Primitive(values_ptype, _) = values.dtype() else {
77+
return false;
78+
};
79+
let max_len = 1u64 << (64 - values_ptype.bit_width());
8380

84-
Stat::from_aggregate_fn(aggregate_fn) == Some(Stat::Sum)
85-
&& (!is_64_bit || batch.len() as u64 <= MAX_EXACT_SUM_LEN)
81+
Stat::from_aggregate_fn(aggregate_fn) == Some(Stat::Sum) && batch.len() as u64 <= max_len
8682
}

0 commit comments

Comments
 (0)