andygrove commented on code in PR #12062:
URL: https://github.com/apache/arrow-rs/pull/12062#discussion_r4569683449
##########
arrow/benches/arithmetic_kernels.rs:
##########
@@ -60,5 +67,141 @@ fn add_benchmark(c: &mut Criterion) {
}
}
-criterion_group!(benches, add_benchmark);
+/// Like `create_primitive_array_range`, but with its own `seed`, so that two
+/// arrays hold different values and nulls.
+fn seeded_array<T>(
+ size: usize,
+ null_density: f32,
+ range: Range<T::Native>,
+ seed: u64,
+) -> PrimitiveArray<T>
+where
+ T: ArrowPrimitiveType,
+ T::Native: SampleUniform,
+{
+ let mut rng = StdRng::seed_from_u64(seed);
+ (0..size)
+ .map(|_| (rng.random::<f32>() >= null_density).then(||
rng.random_range(range.clone())))
+ .collect()
+}
+
+/// 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, seed| {
+ seeded_array::<Decimal128Type>(BATCH_SIZE, null_density,
-999_999..1_000_000, seed)
+ .with_precision_and_scale(18, scale)
+ .unwrap()
+ };
+ let decimal256 = |array: &Decimal128Array| {
+ let array: PrimitiveArray<Decimal256Type> =
+ array.iter().map(|v| v.map(i256::from)).collect();
+ array.with_precision_and_scale(38, 2).unwrap()
+ };
+ for null_density in [0., 0.1] {
+ let a = decimal128(null_density, 2, 1);
+ let b = decimal128(null_density, 2, 2);
+ let b_scale4 = decimal128(null_density, 4, 3);
+ // `1.5`, which has a smaller scale than `b_scale4`.
+ let scalar = Scalar::new(
+ Decimal128Array::from_iter_values([150])
+ .with_precision_and_scale(18, 2)
+ .unwrap(),
+ );
+ let a64 = seeded_array::<Decimal64Type>(BATCH_SIZE, null_density,
-999_999..1_000_000, 1)
+ .with_precision_and_scale(18, 2)
+ .unwrap();
+ let b64 = seeded_array::<Decimal64Type>(BATCH_SIZE, null_density,
-999_999..1_000_000, 2)
+ .with_precision_and_scale(18, 2)
+ .unwrap();
+ let a256 = decimal256(&a);
+ let b256 = decimal256(&b);
+ // Each value fits in `i64` or not at random, which mispredicts the
branch
+ // to the `i64` multiplication in `i128` `mul_overflowing`.
+ let mut rng = StdRng::seed_from_u64(4);
+ let wide: Decimal128Array = (0..BATCH_SIZE)
+ .map(|_| {
+ (rng.random::<f32>() >= null_density).then(|| match
rng.random_bool(0.5) {
+ true => rng.random_range(-999_999..1_000_000),
+ false => {
+ rng.random_range(1 << 63..1 << 80)
+ * if rng.random_bool(0.5) { 1 } else { -1 }
+ }
+ })
+ })
+ .collect();
+ let wide = wide.with_precision_and_scale(38, 2).unwrap();
+
+ c.bench_function(&format!("decimal128_add({null_density})"), |bench| {
+ bench.iter(|| hint::black_box(add(&a, &b).unwrap()))
+ });
+ c.bench_function(
+ &format!("decimal128_add_rescale({null_density})"),
+ |bench| bench.iter(|| hint::black_box(add(&a,
&b_scale4).unwrap())),
+ );
+ c.bench_function(
+ &format!("decimal128_add_rescale_scalar({null_density})"),
+ |bench| bench.iter(|| hint::black_box(add(&b_scale4,
&scalar).unwrap())),
+ );
+ c.bench_function(&format!("decimal128_subtract({null_density})"),
|bench| {
+ bench.iter(|| hint::black_box(sub(&a, &b).unwrap()))
+ });
+ c.bench_function(&format!("decimal128_multiply({null_density})"),
|bench| {
+ bench.iter(|| hint::black_box(mul(&a, &b).unwrap()))
+ });
+ c.bench_function(
+ &format!("decimal128_multiply_wide({null_density})"),
+ |bench| bench.iter(|| hint::black_box(mul(&wide, &b).unwrap())),
+ );
+ c.bench_function(&format!("decimal128_divide({null_density})"),
|bench| {
+ bench.iter(|| hint::black_box(div(&a, &b).unwrap()))
+ });
+ c.bench_function(&format!("decimal64_add({null_density})"), |bench| {
+ bench.iter(|| hint::black_box(add(&a64, &b64).unwrap()))
+ });
+ c.bench_function(&format!("decimal64_multiply({null_density})"),
|bench| {
Review Comment:
nit: The description says Decimal32 and Decimal64 `add`/`sub` now vectorize,
but there's no Decimal32 benchmark and no `decimal64_subtract`. Could you add
them? The Decimal32 path in particular (widening `i32` to `i64` for mul,
sign-bit add/sub) has no coverage, so a slowdown there like the one you saw for
`i256` would go unnoticed.
##########
arrow-arith/src/numeric.rs:
##########
@@ -327,6 +328,299 @@ 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);
+ (n.inner() & &overflowed).count_set_bits() != 0
+ });
+ (!valid_overflow).then(|| PrimitiveArray::new(values.into(), nulls))
+}
+
+/// Converts an allocation failure in [`collect_overflowing`].
+///
+/// One shared, out-of-line copy keeps the formatting code out of every
+/// instance of [`collect_overflowing`], as [`mul_checked_cold`] does for the
+/// decimal `div` and `rem` closures.
+#[cold]
+#[inline(never)]
+fn memory_error(e: TryReserveError) -> ArrowError {
+ ArrowError::MemoryError(e.to_string())
+}
+
+/// Collects the values of `iter`, and whether 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. The checked `add` cases of the `arithmetic_kernels`
+/// benchmark measure this.
+#[inline(never)]
+fn collect_overflowing<N>(
Review Comment:
nit: Could you add numbers to the PR description comparing this to a safe
version (e.g. `Vec::with_capacity` + `push`/`extend` with the same
`#[inline(never)]` boundary)? Since the gain depends on LLVM's inlining choices
for a given target, it would be good to have a record that the `unsafe` is what
produces the gain.
##########
arrow-arith/src/numeric.rs:
##########
@@ -327,6 +328,299 @@ 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);
+ (n.inner() & &overflowed).count_set_bits() != 0
+ });
+ (!valid_overflow).then(|| PrimitiveArray::new(values.into(), nulls))
+}
+
+/// Converts an allocation failure in [`collect_overflowing`].
+///
+/// One shared, out-of-line copy keeps the formatting code out of every
+/// instance of [`collect_overflowing`], as [`mul_checked_cold`] does for the
+/// decimal `div` and `rem` closures.
+#[cold]
+#[inline(never)]
+fn memory_error(e: TryReserveError) -> ArrowError {
+ ArrowError::MemoryError(e.to_string())
+}
+
+/// Collects the values of `iter`, and whether 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. The checked `add` cases of the `arithmetic_kernels`
+/// benchmark measure this.
+#[inline(never)]
+fn collect_overflowing<N>(
+ iter: impl ExactSizeIterator<Item = (N, bool)>,
+) -> Result<(Vec<N>, bool), ArrowError> {
+ let mut values = Vec::new();
+ values.try_reserve_exact(iter.len()).map_err(memory_error)?;
+ 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());
Review Comment:
nit: `written <= values.capacity()` can't fail, because the zip is bounded
by `spare_capacity_mut()`. It doesn't check the `set_len` precondition either.
Maybe drop it, or capture `iter.len()` up front and `debug_assert_eq!(written,
len)`, which at least catches an iterator that reports the wrong length.
--
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]