sunchao commented on code in PR #12058:
URL: https://github.com/apache/arrow-rs/pull/12058#discussion_r4565570158
##########
arrow-arith/src/numeric.rs:
##########
@@ -327,6 +327,139 @@ macro_rules! try_op_ref {
}};
}
+/// Wrapping `+`, `-` and `*` that also report whether they overflowed, written
+/// so that LLVM vectorizes a loop over them.
+///
+/// The signed `overflowing_add` and `overflowing_sub` lower to
+/// `llvm.sadd.with.overflow` and `llvm.ssub.with.overflow`, which LLVM doesn't
+/// vectorize, so the signed impls test the sign bits instead.
+trait OverflowingOp: Sized {
+ fn add_overflowing(self, rhs: Self) -> (Self, bool);
+ fn sub_overflowing(self, rhs: Self) -> (Self, bool);
+ fn mul_overflowing(self, rhs: Self) -> (Self, bool);
+}
+
+macro_rules! signed_overflowing_op {
+ ($($t:ty => $wide:ty),*) => {$(
+ impl OverflowingOp for $t {
+ #[inline]
+ fn add_overflowing(self, rhs: Self) -> (Self, bool) {
+ let sum = self.wrapping_add(rhs);
+ // Overflow iff both operands have the same sign and `sum` has
the other.
+ (sum, (self ^ sum) & (rhs ^ sum) < 0)
+ }
+
+ #[inline]
+ fn sub_overflowing(self, rhs: Self) -> (Self, bool) {
+ let difference = self.wrapping_sub(rhs);
+ // Overflow iff the operands have different signs and
`difference`
+ // doesn't have the sign of `self`.
+ (difference, (self ^ rhs) & (self ^ difference) < 0)
+ }
+
+ #[inline]
+ fn mul_overflowing(self, rhs: Self) -> (Self, bool) {
+ let product = <$wide>::from(self) * <$wide>::from(rhs);
+ // The truncating cast is the wrapping product. It overflowed
iff
+ // widening it back doesn't give the full product.
+ (product as $t, <$wide>::from(product as $t) != product)
+ }
+ }
+ )*};
+}
+
+signed_overflowing_op!(i8 => i16, i16 => i32, i32 => i64, i64 => i128);
+
+macro_rules! unsigned_overflowing_op {
+ ($($t:ty),*) => {$(
+ // LLVM vectorizes the unsigned `overflowing_add` and
`overflowing_sub`.
+ // It folds a widening unsigned multiply back into
`llvm.umul.with.overflow`,
+ // which it doesn't vectorize, so `mul` stays scalar either way.
+ impl OverflowingOp for $t {
+ #[inline]
+ fn add_overflowing(self, rhs: Self) -> (Self, bool) {
+ self.overflowing_add(rhs)
+ }
+
+ #[inline]
+ fn sub_overflowing(self, rhs: Self) -> (Self, bool) {
+ self.overflowing_sub(rhs)
+ }
+
+ #[inline]
+ fn mul_overflowing(self, rhs: Self) -> (Self, bool) {
+ self.overflowing_mul(rhs)
+ }
+ }
+ )*};
+}
+
+unsigned_overflowing_op!(u8, u16, u32, u64);
+
+/// Applies `op` to every slot of `l` and `r`, including null slots, without
+/// branching on overflow.
+///
+/// Returns `None` if any slot overflowed or the array lengths differ, so the
+/// caller can fall back to the checked kernel to report the error. A null slot
+/// can hold any value, so `None` doesn't mean a valid row overflowed.
+fn overflowing_op<T, F>(
+ l: &PrimitiveArray<T>,
+ l_s: bool,
+ r: &PrimitiveArray<T>,
+ r_s: bool,
+ op: F,
+) -> Option<PrimitiveArray<T>>
+where
+ T: ArrowPrimitiveType,
+ F: Fn(T::Native, T::Native) -> (T::Native, bool),
+{
+ match (l_s, r_s) {
+ (true, true) | (false, false) => {
+ if l.len() != r.len() {
+ return None;
+ }
+ let pairs = l.values().iter().zip(r.values());
+ let values = collect_overflowing(pairs.map(|(&l, &r)| op(l, r)))?;
+ Some(PrimitiveArray::new(
+ values.into(),
+ NullBuffer::union(l.nulls(), r.nulls()),
+ ))
+ }
+ (true, false) => match (l.null_count() == 0).then(|| l.value(0)) {
+ None => Some(PrimitiveArray::new_null(r.len())),
+ Some(l) => {
+ let values = collect_overflowing(r.values().iter().map(|&r|
op(l, r)))?;
+ Some(PrimitiveArray::new(values.into(), r.nulls().cloned()))
+ }
+ },
+ (false, true) => match (r.null_count() == 0).then(|| r.value(0)) {
+ None => Some(PrimitiveArray::new_null(l.len())),
+ Some(r) => {
+ let values = collect_overflowing(l.values().iter().map(|&l|
op(l, r)))?;
+ Some(PrimitiveArray::new(values.into(), l.nulls().cloned()))
+ }
+ },
+ }
+}
+
+/// Collects the values of `iter`, returning `None` if any was flagged as
overflowed.
+///
+/// This intentional `inline(never)` keeps `overflow` in a register. Inlined
+/// into `integer_op` under thin LTO, LLVM keeps the flag in memory and loads
+/// and stores it on every row, which serializes the loop and keeps it from
+/// vectorizing.
+#[inline(never)]
+fn collect_overflowing<N>(iter: impl Iterator<Item = (N, bool)>) ->
Option<Vec<N>> {
+ let mut overflow = false;
+ let values = iter
+ .map(|(value, overflowed)| {
+ overflow |= overflowed;
+ value
+ })
+ .collect();
Review Comment:
Could this reserve the output buffer fallibly? For two nonempty arrays with
no nulls, the [current checked
kernel](https://github.com/apache/arrow-rs/blob/4e04fea272107a6716d5634c591d0d994ba1eed2/arrow-arith/src/arity.rs#L370-L390)
maps allocation failure to `ArrowError::MemoryError` as part of
[#11912](https://github.com/apache/arrow-rs/pull/11912). If the allocator
rejects the output allocation here, the infallible `Vec` collection can abort
the process before the checked fallback runs. A fallible reservation in the
fast path would preserve the caller's ability to handle that error.
##########
arrow-arith/src/numeric.rs:
##########
@@ -1693,6 +1839,165 @@ mod tests {
assert_eq!(err, "Divide by zero error");
}
+ type Kernel = fn(&dyn Datum, &dyn Datum) -> Result<ArrayRef, ArrowError>;
+ type Checked<N> = fn(N, N) -> Result<N, ArrowError>;
+
+ /// Checks `add`, `sub` and `mul` against the scalar checked operations for
+ /// every pair of `edges`, with arrays on both sides and with a scalar on
+ /// either side. Every third row of the left array is null, so null slots
+ /// also hold values that overflow.
+ fn test_checked_integer_ops<T: ArrowPrimitiveType>(edges: &[T::Native]) {
+ test_checked_integer_op::<T>(edges, add, |l, r| l.add_checked(r));
+ test_checked_integer_op::<T>(edges, sub, |l, r| l.sub_checked(r));
+ test_checked_integer_op::<T>(edges, mul, |l, r| l.mul_checked(r));
+ }
+
+ fn test_checked_integer_op<T: ArrowPrimitiveType>(
+ edges: &[T::Native],
+ kernel: Kernel,
+ checked: Checked<T::Native>,
+ ) {
+ let (l, r): (Vec<_>, Vec<_>) = edges
+ .iter()
+ .flat_map(|&x| edges.iter().map(move |&y| (x, y)))
+ .unzip();
+ let nulls = NullBuffer::from_iter((0..l.len()).map(|i| i % 3 != 2));
+ let l_array = PrimitiveArray::<T>::new(l.clone().into(),
Some(nulls.clone()));
+ let r_array = PrimitiveArray::<T>::from_iter_values(r.iter().copied());
+
+ // The kernels report the first valid row that overflows.
+ let expected = (0..l.len())
+ .map(|i| nulls.is_valid(i).then(|| checked(l[i],
r[i])).transpose())
+ .collect();
+ assert_kernel_result::<T>(kernel(&l_array, &r_array), expected,
"array, array");
+
+ // An overflow in one row sends the whole array to the checked kernel,
+ // which would hide a missed overflow in another row, so also check
each
+ // row alone.
+ for i in 0..l.len() {
+ let expected = match nulls.is_valid(i) {
+ true => checked(l[i], r[i]).map(|v| vec![Some(v)]),
+ false => Ok(vec![None]),
+ };
+ let actual = kernel(&l_array.slice(i, 1), &r_array.slice(i, 1));
+ assert_kernel_result::<T>(actual, expected, &format!("row {i}"));
+ }
+
+ for &x in edges {
+ let scalar = PrimitiveArray::<T>::new_scalar(x);
+ let expected = r.iter().map(|&y| checked(x,
y).map(Some)).collect();
+ assert_kernel_result::<T>(
+ kernel(&scalar, &r_array),
+ expected,
+ &format!("scalar {x:?}, array"),
+ );
+ let expected = (0..l.len())
+ .map(|i| nulls.is_valid(i).then(|| checked(l[i],
x)).transpose())
+ .collect();
+ assert_kernel_result::<T>(
+ kernel(&l_array, &scalar),
+ expected,
+ &format!("array, scalar {x:?}"),
+ );
+ }
+ }
+
+ #[test]
+ fn test_checked_integer_edges() {
+ macro_rules! signed {
+ ($a:ty, $t:ty) => {
+ test_checked_integer_ops::<$a>(&[
+ <$t>::MIN,
+ <$t>::MIN + 1,
+ <$t>::MIN / 2,
+ -3,
+ -1,
+ 0,
+ 1,
+ 3,
+ <$t>::MAX / 2,
+ <$t>::MAX / 2 + 1,
+ <$t>::MAX - 1,
+ <$t>::MAX,
+ ])
+ };
+ }
+ macro_rules! unsigned {
+ ($a:ty, $t:ty) => {
+ test_checked_integer_ops::<$a>(&[
+ 0,
+ 1,
+ 3,
+ <$t>::MAX / 2,
+ <$t>::MAX / 2 + 1,
+ <$t>::MAX - 1,
+ <$t>::MAX,
+ ])
+ };
+ }
+ signed!(Int8Type, i8);
+ signed!(Int16Type, i16);
+ signed!(Int32Type, i32);
+ signed!(Int64Type, i64);
+ unsigned!(UInt8Type, u8);
+ unsigned!(UInt16Type, u16);
+ unsigned!(UInt32Type, u32);
+ unsigned!(UInt64Type, u64);
+ }
+
+ #[test]
+ fn test_checked_integer_overflow_position() {
+ let one = Int32Array::new_scalar(1);
+ // Every length up to 130 puts the overflow in each part of the vector
loop
+ // for strides up to 64 rows.
+ for len in 1..=130 {
+ let mut values = vec![1; len];
+ values[len - 1] = i32::MAX;
Review Comment:
Could the overflow position vary independently of the batch length? With a
full-vector loop followed by a scalar tail, `len - 1` lands in the last lane of
a full vector or in the tail. A missing overflow flag in an interior lane can
pass this test. A fixed batch above the vectorization threshold with one
overflowing row moved through the batch would cover that case, including the
separate array–array loop. For the one-row edge checks, the current null mask
also hides every signed RHS `MAX` because the signed edge list has 12 entries
and `MAX` is at index 11. Sweeping the pairs without the mask would cover those
cases.
##########
arrow-arith/src/numeric.rs:
##########
@@ -427,22 +560,35 @@ divisor_op!(
);
/// Perform an arithmetic operation on integers
-fn integer_op<T: ArrowPrimitiveType>(
+fn integer_op<T>(
op: Op,
l: &dyn Array,
l_s: bool,
r: &dyn Array,
r_s: bool,
-) -> Result<ArrayRef, ArrowError> {
+) -> Result<ArrayRef, ArrowError>
+where
+ T: ArrowPrimitiveType,
+ T::Native: OverflowingOp,
+{
let l = l.as_primitive::<T>();
let r = r.as_primitive::<T>();
let array: PrimitiveArray<T> = match op {
Op::AddWrapping => op!(l, l_s, r, r_s, l.add_wrapping(r)),
- Op::Add => try_op!(l, l_s, r, r_s, l.add_checked(r)),
+ Op::Add => match overflowing_op(l, l_s, r, r_s,
T::Native::add_overflowing) {
+ Some(array) => array,
+ None => try_op!(l, l_s, r, r_s, l.add_checked(r)),
+ },
Op::SubWrapping => op!(l, l_s, r, r_s, l.sub_wrapping(r)),
- Op::Sub => try_op!(l, l_s, r, r_s, l.sub_checked(r)),
+ Op::Sub => match overflowing_op(l, l_s, r, r_s,
T::Native::sub_overflowing) {
Review Comment:
This forces a second pass for ordinary nullable unsigned subtraction. For
example, `UInt64 [10, null, 20] - 1` has a zero payload at the null row when
built through `PrimitiveBuilder`. The first pass sees `0u64 - 1`, fills and
discards its output, and the checked kernel allocates again to return `[9,
null, 19]`. This repeats on every batch with a null even when all valid rows
succeed. Could you add a nullable `UInt32` or `UInt64` array-minus-scalar
benchmark and avoid replay on this case? The current benchmark only exercises
signed types.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]