mbutrovich commented on code in PR #12058:
URL: https://github.com/apache/arrow-rs/pull/12058#discussion_r4568377160
##########
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?
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. That also makes the nullable and scalar paths fallible. The checked
kernel still aborts there, through
[`BufferBuilder::new`](https://github.com/apache/arrow-rs/blob/9c9486188744e80ec86c3b2bcdd649b89945ffe5/arrow-arith/src/arity.rs#L272-L273)
in `try_binary` and
[`vec!`](https://github.com/apache/arrow-rs/blob/9c9486188744e80ec86c3b2bcdd649b89945ffe5/arrow-array/src/array/primitive_array.rs#L990-L998)
in `PrimitiveArray::try_unary`. 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.
--
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]