mbutrovich commented on code in PR #12058:
URL: https://github.com/apache/arrow-rs/pull/12058#discussion_r4579102223
##########
arrow-arith/src/numeric.rs:
##########
@@ -327,6 +328,205 @@ 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 {
+ /// Whether the checked kernels use the one-pass path for this type. When
+ /// it's false, [`overflowing_op`] returns `None` without doing any work.
+ const ONE_PASS: bool = true;
+
+ 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) {
+ signed_mul_overflowing!(self, rhs, $t $(, $wide)?)
+ }
+ }
+ )*};
+}
+
+/// The wrapping product of two signed integers and whether it overflowed.
+macro_rules! signed_mul_overflowing {
+ // The truncating cast is the wrapping product. It overflowed iff widening
+ // it back doesn't give the full product.
+ ($l:expr, $r:expr, $t:ty, $wide:ty) => {{
+ let product = <$wide>::from($l) * <$wide>::from($r);
+ (product as $t, <$wide>::from(product as $t) != product)
+ }};
+ // Widened to `i128`, an `i64` multiply stays a scalar `imul` on x86-64,
and
+ // LLVM packs each row's overflow flag into vector registers around it,
+ // which made the loop slower than the checked kernel with
+ // `-C target-cpu=x86-64-v3`.
+ ($l:expr, $r:expr, $t:ty) => {
+ $l.overflowing_mul($r)
+ };
+}
+
+signed_overflowing_op!(i8 => i16, i16 => i32, i32 => i64, i64);
+
+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 `Ok(None)` if a valid row overflowed or the array lengths differ,
+/// so the caller can fall back to the checked kernel to report the error.
+fn overflowing_op<T, F>(
+ l: &PrimitiveArray<T>,
+ l_s: bool,
+ r: &PrimitiveArray<T>,
+ r_s: bool,
+ op: F,
+) -> Result<Option<PrimitiveArray<T>>, ArrowError>
+where
+ T: ArrowPrimitiveType,
+ T::Native: OverflowingOp,
+ F: Fn(T::Native, T::Native) -> (T::Native, bool),
+{
+ if !T::Native::ONE_PASS {
+ return Ok(None);
+ }
+ match (l_s, r_s) {
+ (true, true) | (false, false) => {
+ if l.len() != r.len() {
+ return Ok(None);
+ }
+ let pairs = l.values().iter().zip(r.values());
+ let values = collect_overflowing(pairs.map(|(&l, &r)| op(l, r)))?;
+ let nulls = NullBuffer::union(l.nulls(), r.nulls());
+ let (l, r) = (l.values(), r.values());
+ Ok(unless_valid_overflow(values, nulls, |i| op(l[i], r[i]).1))
+ }
+ (true, false) => match (l.null_count() == 0).then(|| l.value(0)) {
+ None => Ok(Some(PrimitiveArray::new_null(r.len()))),
+ Some(l) => {
+ let values = collect_overflowing(r.values().iter().map(|&r|
op(l, r)))?;
+ let (nulls, r) = (r.nulls().cloned(), r.values());
+ Ok(unless_valid_overflow(values, nulls, |i| op(l, r[i]).1))
+ }
+ },
+ (false, true) => match (r.null_count() == 0).then(|| r.value(0)) {
+ None => Ok(Some(PrimitiveArray::new_null(l.len()))),
+ Some(r) => {
+ let values = collect_overflowing(l.values().iter().map(|&l|
op(l, r)))?;
+ let (nulls, l) = (l.nulls().cloned(), l.values());
+ Ok(unless_valid_overflow(values, nulls, |i| op(l[i], r).1))
+ }
+ },
+ }
+}
+
+/// Builds the array from the output of [`collect_overflowing`], or returns
+/// `None` if a valid row overflowed.
+///
+/// A null slot can hold any value, such as the 0 that builders write, which
+/// overflows unsigned `0 - 1`. So when a slot overflowed, this recomputes the
+/// overflow of every row with `overflowed` and masks it with the validity
+/// bits, instead of making the caller rerun the whole batch.
+fn unless_valid_overflow<T: ArrowPrimitiveType>(
+ (values, overflow): (Vec<T::Native>, bool),
+ nulls: Option<NullBuffer>,
+ overflowed: impl Fn(usize) -> bool,
+) -> Option<PrimitiveArray<T>> {
+ let valid_overflow = overflow
+ && nulls.as_ref().is_none_or(|n| {
+ let overflowed = BooleanBuffer::collect_bool(n.len(), overflowed);
Review Comment:
Allocation failure is a failing case, and I'd rather not add code for it
here. The scratch is 2 KiB for 8192 rows, and if it can't be allocated, the
checked kernel this falls back to can't report that on nullable input either
([`try_binary`](https://github.com/apache/arrow-rs/blob/9c9486188744e80ec86c3b2bcdd649b89945ffe5/arrow-arith/src/arity.rs#L272-L273),
[`try_unary`](https://github.com/apache/arrow-rs/blob/9c9486188744e80ec86c3b2bcdd649b89945ffe5/arrow-array/src/array/primitive_array.rs#L990-L998)).
`valid_indices().any(..)` is what this check was before, and it slowed down
the common case it exists for: nullable `UInt32` minus a scalar, where
zero-filled null slots overflow, measured 0.70x on Xeon 8581C
([run](https://github.com/apache/arrow-rs/pull/12058#issuecomment-6861746393)),
against 1.17x with the bitmaps
([run](https://github.com/apache/arrow-rs/pull/12058#issuecomment-6863835999)).
`test_checked_null_slot_overflow_sliced` now covers a sliced validity buffer
across se
veral 64-row chunks.
--
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]