mbutrovich commented on code in PR #12062:
URL: https://github.com/apache/arrow-rs/pull/12062#discussion_r4568410887
##########
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.
Review Comment:
> When the overflow flag is set and the input has nulls, could we check the
overflowing positions against the validity bitmap before falling back?
Done in this PR. After a pass that flagged an overflow, `overflowing_op`
recomputes the overflow of every row into a bitmap with
`BooleanBuffer::collect_bool`, masks it with the validity bits, and falls back
to the checked kernel only if a valid row overflowed. Otherwise it keeps the
values from the first pass. `decimal128_add_null_slot_overflow` measured 0.88x
on
[Neoverse-V2](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863263619),
0.86x on [Xeon
8581C](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863287300),
and 1.45x with
[`x86-64-v3`](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863303751).
`Decimal128` doesn't vectorize, so on Neoverse-V2 and Xeon 8581C a scalar pass
plus the check still costs more than one checked pass over the valid rows. The
description lists it as an input that gets slower.
##########
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());
+ let mut overflow = false;
+ let mut written = 0;
+ for (slot, (value, overflowed)) in
values.spare_capacity_mut().iter_mut().zip(iter) {
+ slot.write(value);
+ overflow |= overflowed;
+ written += 1;
+ }
+ debug_assert!(written <= values.capacity());
+ // SAFETY: the loop initialized the first `written` slots of the spare
+ // capacity, and `written` counts those writes, so it doesn't rely on
+ // `iter.len()`.
+ unsafe { values.set_len(written) };
+ (!overflow).then_some(values)
+}
+
+// No vector lanes are 128 or 256 bits wide, so loops over these types stay
+// scalar. Their `overflowing_*` methods don't branch on overflow, which still
+// removes the early return of the checked kernel.
+impl OverflowingOp for i128 {
+ #[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) {
+ // Decimal values usually fit in 64 bits, and the product of two `i64`
+ // can't overflow `i128`, so this skips the full 128-bit multiply.
+ match (i64::try_from(self), i64::try_from(rhs)) {
Review Comment:
> Could you add a case where operands randomly do or don't fit in `i64`, so
the mispredicted branch is measured?
Added `decimal128_multiply_wide`. Each left value fits in `i64` or not at
random: half are in +-999,999, and half have a magnitude in [2^63, 2^80).
Without and with 10% nulls, it measured 1.18x and 0.89x on
[Neoverse-V2](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863263619),
1.14x and 1.44x on [Xeon
8581C](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863287300),
and 1.11x and 1.42x with
[`x86-64-v3`](https://github.com/apache/arrow-rs/pull/12062#issuecomment-6863303751).
The description lists the 0.89x case as an input that gets slower.
--
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]