mbutrovich commented on code in PR #12062:
URL: https://github.com/apache/arrow-rs/pull/12062#discussion_r4568400009


##########
arrow-arith/src/numeric.rs:
##########
@@ -327,6 +327,217 @@ 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 its caller 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. The loop writes into the `Vec`'s spare capacity itself,
+/// because whether LLVM inlines the loop inside `collect` depends on the
+/// closure and the target, and when it doesn't, that loop reaches the flag
+/// through a pointer.
+#[inline(never)]
+fn collect_overflowing<N>(iter: impl ExactSizeIterator<Item = (N, bool)>) -> 
Option<Vec<N>> {
+    let mut values = Vec::with_capacity(iter.len());

Review Comment:
   > Could this use a fallible reservation?
   
   Yes. `collect_overflowing` now reserves with `Vec::try_reserve_exact` and 
returns `ArrowError::MemoryError` on failure, as 
[`try_binary_no_nulls`](https://github.com/apache/arrow-rs/blob/9c9486188744e80ec86c3b2bcdd649b89945ffe5/arrow-arith/src/arity.rs#L380-L384)
 does, for the checked and wrapping entry points alike. The null-slot check 
that runs after a flagged pass allocates two bitmaps through 
`BooleanBuffer::collect_bool`, which aborts on failure. It runs only when the 
result has nulls, where `try_binary` allocates infallibly too.



##########
arrow-arith/src/numeric.rs:
##########
@@ -1195,28 +1406,61 @@ where
             match op {
                 // Equal scales make both decimal multipliers one.
                 Op::Add | Op::AddWrapping if s1 == s2 => {
-                    try_op!(l, l_s, r, r_s, l.add_checked(r))
+                    match overflowing_op(l, l_s, r, r_s, 
T::Native::add_overflowing) {

Review Comment:
   > Can we keep the checked path for equal-scale `Decimal256` add until this 
case improves on `x86-64-v3`?
   
   Done. `Decimal256` now keeps the checked kernel for `add`, `sub`, and `mul`, 
through an `OverflowingOp::ONE_PASS` const that the `i256` impl sets to false. 
The rerun with independent operands still measured `decimal256_add` at 0.75x 
without nulls and 0.90x with nulls with 
[`x86-64-v3`](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6862160802),
 against 1.33x to 2.40x on Neoverse-V2 and Xeon 8581C. With the checked kernel, 
`decimal256_add` now measures 0.99x to 1.06x in every configuration 
([Neoverse-V2](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863263619),
 [Xeon 
8581C](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863287300), 
[`x86-64-v3`](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863303751)).
   
   I looked at the codegen. With `-C target-cpu=x86-64-v3`, LLVM vectorizes the 
`i256` add loop in `collect_overflowing` at two rows per iteration. The 256-bit 
adds stay scalar (`add` and `adc`). The carries and overflow flags move through 
`vinserti128`, `vpermd`, `vmovmskps`, and `vpblendvb`, and the loop spills and 
reloads about 20 stack slots per iteration. That is about 120 instructions per 
two rows, against about 25 per row in the scalar loop that the `x86-64` build 
runs. Computing the flag with the sign-bit test instead of the comparisons in 
[`i256::overflowing_add`](https://github.com/apache/arrow-rs/blob/9c9486188744e80ec86c3b2bcdd649b89945ffe5/arrow-buffer/src/bigint/mod.rs#L849-L866)
 gives the same loop, so the vectorizer is packing the carry, not the flag. 
Returning at the first overflow kept the loop scalar on `x86-64-v3`, but it 
would have added a second loop mode to the shared helper for one type.



-- 
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]

Reply via email to