andygrove commented on code in PR #12062:
URL: https://github.com/apache/arrow-rs/pull/12062#discussion_r4566189775
##########
arrow/benches/arithmetic_kernels.rs:
##########
@@ -60,5 +61,96 @@ fn add_benchmark(c: &mut Criterion) {
}
}
-criterion_group!(benches, add_benchmark);
+/// Decimal arithmetic at DataFusion's default batch size.
+///
+/// Values stay within six digits, so the cases never overflow unless the case
+/// name says so. `add` and `add_wrapping` run the same checked kernel for
+/// decimals, so only `add` is measured.
+fn decimal_benchmark(c: &mut Criterion) {
+ const BATCH_SIZE: usize = 8192;
+ let decimal128 = |null_density, scale| {
+ create_primitive_array_range::<Decimal128Type>(
+ BATCH_SIZE,
+ null_density,
+ -999_999..1_000_000,
+ )
+ .with_precision_and_scale(18, scale)
+ .unwrap()
+ };
+ for null_density in [0., 0.1] {
+ let a = decimal128(null_density, 2);
+ let b = decimal128(null_density, 2);
+ let b_scale4 = decimal128(null_density, 4);
+ let a64 = create_primitive_array_range::<Decimal64Type>(
+ BATCH_SIZE,
+ null_density,
+ -999_999..1_000_000,
+ )
+ .with_precision_and_scale(18, 2)
+ .unwrap();
+ let b64 = a64.clone();
Review Comment:
These add each array to a copy of itself. Could `b64`/`b256` be generated
independently like `a`/`b` for Decimal128? Then the Decimal256 numbers would be
measured on two different operands.
##########
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:
As the PR description notes, overflow in a null slot reruns the whole batch
on every batch. Since this PR now writes wrapped values into null slots,
chaining decimal ops makes that more likely. When the overflow flag is set and
the input has nulls, could we check the overflowing positions against the
validity bitmap before falling back? It could also be a follow-up, but it seems
worth tracking.
##########
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) {
+ Some(array) => array,
+ None => try_op!(l, l_s, r, r_s, l.add_checked(r)),
+ }
}
Op::Sub | Op::SubWrapping if s1 == s2 => {
- try_op!(l, l_s, r, r_s, l.sub_checked(r))
+ match overflowing_op(l, l_s, r, r_s,
T::Native::sub_overflowing) {
+ Some(array) => array,
+ None => try_op!(l, l_s, r, r_s, l.sub_checked(r)),
+ }
}
+ // `move` copies the multipliers into the closures. Borrowed,
they
+ // keep the loop from vectorizing under thin LTO, like the
borrowed
+ // captures #11525 fixed in `unary`.
Op::Add | Op::AddWrapping => {
- try_op!(
- l,
- l_s,
- r,
- r_s,
-
l.mul_checked(l_mul)?.add_checked(r.mul_checked(r_mul)?)
- )
+ let add = T::Native::add_overflowing;
+ let array = match s1 < s2 {
+ true => overflowing_op(l, l_s, r, r_s, move |l, r| {
+ rescale_left(l, l_mul, r, add)
Review Comment:
When the scalar has the smaller scale (e.g. `col + 1.5` against a scale-4
column, which is common in DataFusion), the closure rescales the same scalar by
`l_mul`/`r_mul` on every row. Could we rescale the scalar once before the loop
and pass plain `add_overflowing` to `overflowing_op`? That saves a 128- or
256-bit multiply per row. It also means a scalar whose rescale overflows
doesn't flag every row and force the checked rerun. The same applies to the
`Sub` arm.
##########
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:
The benchmarks only use values in ±999,999, so this always takes the `i64`
path. Could you add a case where operands randomly do or don't fit in `i64`, so
the mispredicted branch is measured? I'd like to make sure Decimal128 mul with
wider values doesn't regress.
##########
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)) {
+ (Ok(l), Ok(r)) => (i128::from(l) * i128::from(r), false),
+ _ => self.overflowing_mul(rhs),
+ }
+ }
+}
+
+impl OverflowingOp for i256 {
+ #[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) {
+ // `i256` has no `overflowing_mul`.
+ match self.checked_mul(rhs) {
Review Comment:
nit: On overflow this does the 256-bit multiply twice (`checked_mul`, then
`wrapping_mul`), and `i256` can't vectorize anyway. Is there a measured gain
for Decimal256 `mul`? If not, keeping `try_op!` there would be simpler.
##########
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>> {
Review Comment:
The description says this is the same as in #12058, but the versions differ.
#12058 takes `Iterator` and uses `collect`, while this one takes
`ExactSizeIterator` and writes into spare capacity with `unsafe set_len`.
Whichever lands second will need to pick one deliberately rather than just
dropping its copy. If the spare-capacity version is the faster one, the integer
kernels in #12058 probably want it too, measured with their own benchmarks.
Also, `debug_assert!(written <= values.capacity())` always holds because of the
`zip` with `spare_capacity_mut`, so it can go.
--
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]