This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new 36122935e4 bench(arrow-arith): add integer and decimal division by
scalar benchmarks (#11427)
36122935e4 is described below
commit 36122935e488001fae53344ed17ee39f0a5970c9
Author: Matt Butrovich <[email protected]>
AuthorDate: Sun Oct 11 16:15:40 2026 +0000
bench(arrow-arith): add integer and decimal division by scalar benchmarks
(#11427)
# Which issue does this PR close?
- Part of #11421.
# Rationale for this change
#11421 proposes replacing the per-row division in `div` and `rem` by a
scalar with a precomputed reciprocal. The kernel PRs need benchmarks on
`main` to report before and after numbers. Today
[`arithmetic_kernels`](https://github.com/apache/arrow-rs/blob/c7f60c612bd16ca5485cc9acddfd216c10ea9765/arrow/benches/arithmetic_kernels.rs#L26-L74)
covers only `Float32`, and
[`decimal_arithmetic`](https://github.com/apache/arrow-rs/blob/c7f60c612bd16ca5485cc9acddfd216c10ea9765/arrow-arith/benches/decimal_arithmetic.rs#L39-L56)
covers only `add` and `sub`.
# What changes are included in this PR?
This PR adds two benchmarks, `integer_division` and `decimal_division`.
All values come from a fixed seed, and each array is divided by a
`Scalar`, so the divisor is the same for every row.
- `integer_division` runs `div` and `rem` on 8192 random `Int32`,
`UInt32`, `Int64` and `UInt64` values, divided by 13 and by 16. A
precomputed divisor can replace division by a power of two with a shift
or mask, so 16 is a separate case.
- `decimal_division` runs `div` and `rem` by a scalar on 1024
`Decimal32`, `Decimal64`, `Decimal128` and `Decimal256` values. The
`Decimal32` and `Decimal64` values have scale 2, and the `Decimal128`
and `Decimal256` values have scale 10. For `div` the divisors have scale
2, so `div` scales the values by 10^6. Each type has a `div` case whose
values fit after scaling and one whose values overflow the type when
scaled. `Decimal64`, `Decimal128` and `Decimal256` add a case with wider
values, and `Decimal128` and `Decimal256` add a divisor wider than half
the type's width. The overflow cases take the
[`scaled_div`](https://github.com/apache/arrow-rs/blob/c7f60c612bd16ca5485cc9acddfd216c10ea9765/arrow-arith/src/numeric.rs#L970-L1012)
fallback, which computes the quotient one digit at a time. For each
overflowing value, `div` also builds an `ArrowError` and discards it
before falling back. The setup asserts that the overflow case overflows
on every value and the other `div` cases on none, so a case can't change
paths without notice. For `rem` the divisors have the same scale as the
values, because `rem` scales the divisor to the larger scale. `rem`
doesn't scale the values, so it has no overflow case.
- `decimal_division` also runs `multiply_fixed_point`, which computes
each product in `i256` and divides it by the same power of ten for every
row. The operands match the `Decimal256` multiply results that the
`Decimal256` to `Decimal128` casts in #11426 start from: products that
fit in `i128`, wider products, and a divisor wider than 64 bits.
The division cases are in their own targets so that
`decimal_arithmetic`, which covers `add` and `sub`, keeps its 16 cases
and its run time.
Both benchmarks run one case per type and operation on an array where a
fifth of the values are null at random positions, because
[`try_unary`](https://github.com/apache/arrow-rs/blob/c7f60c612bd16ca5485cc9acddfd216c10ea9765/arrow-array/src/array/primitive_array.rs#L1017-L1020)
visits only the valid values when there are nulls. Both also run `div`
on the first 128 values, where building a divisor is a larger share of
the work. Building a `Decimal128` or `Decimal256` divisor costs more, so
those types also run on 1 and 16 values. In the #11421 prototype,
building a 64-bit divisor took 1.4 to 2.5 ns, which is small next to the
fixed cost of a call: on an Apple M5 Max, `div` on 1 or 16 integer
values takes 36 to 41 ns.
`arrow-arith` gains `rand` as a dev-dependency, with the same features
as `arrow-ord`.
# Are these changes tested?
This PR only adds benchmarks.
# Are there any significant user-facing changes?
No.
## AI Disclosure
I wrote this PR with help from Claude but understand and support the
core approach, implementation, and test coverage.
---
Cargo.lock | 1 +
arrow-arith/Cargo.toml | 9 ++
arrow-arith/benches/decimal_division.rs | 196 ++++++++++++++++++++++++++++++++
arrow-arith/benches/integer_division.rs | 78 +++++++++++++
4 files changed, 284 insertions(+)
diff --git a/Cargo.lock b/Cargo.lock
index c6a9c4c271..4e89351a8d 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -212,6 +212,7 @@ dependencies = [
"chrono",
"criterion",
"num-traits",
+ "rand 0.10.3",
]
[[package]]
diff --git a/arrow-arith/Cargo.toml b/arrow-arith/Cargo.toml
index 8bb02b1d8c..116738c967 100644
--- a/arrow-arith/Cargo.toml
+++ b/arrow-arith/Cargo.toml
@@ -44,6 +44,7 @@ num-traits = { version = "0.2.19", default-features = false,
features = ["std"]
[dev-dependencies]
criterion = { workspace = true }
+rand = { version = "0.10", default-features = false, features = ["std",
"std_rng"] }
[[bench]]
name = "decimal_arithmetic"
@@ -53,5 +54,13 @@ harness = false
name = "temporal"
harness = false
+[[bench]]
+name = "integer_division"
+harness = false
+
+[[bench]]
+name = "decimal_division"
+harness = false
+
[lints]
workspace = true
diff --git a/arrow-arith/benches/decimal_division.rs
b/arrow-arith/benches/decimal_division.rs
new file mode 100644
index 0000000000..f22793cb9b
--- /dev/null
+++ b/arrow-arith/benches/decimal_division.rs
@@ -0,0 +1,196 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hint;
+
+use arrow_arith::arithmetic::multiply_fixed_point;
+use arrow_arith::numeric::{div, rem};
+use arrow_array::types::{
+ Decimal32Type, Decimal64Type, Decimal128Type, Decimal256Type, DecimalType,
+};
+use arrow_array::{Array, ArrayRef, ArrowNativeTypeOp, Datum, PrimitiveArray,
Scalar};
+use arrow_buffer::{ArrowNativeType, NullBuffer};
+use arrow_schema::ArrowError;
+use criterion::{Criterion, Throughput, criterion_group, criterion_main};
+use rand::rngs::StdRng;
+use rand::{RngExt, SeedableRng};
+
+const SIZE: usize = 1024;
+
+type Kernel = fn(&dyn Datum, &dyn Datum) -> Result<ArrayRef, ArrowError>;
+
+/// Creates an array of `len` random values with `digits` significant digits
+/// (no leading zero, half of them negative) for the given `scale`
+fn random_decimal<T: DecimalType>(
+ len: usize,
+ digits: u32,
+ scale: i8,
+ seed: u64,
+) -> PrimitiveArray<T> {
+ let mut rng = StdRng::seed_from_u64(seed);
+ let ten = T::Native::usize_as(10);
+ let values = (0..len).map(|_| {
+ let mut value = T::Native::usize_as(rng.random_range(1..10));
+ for _ in 1..digits {
+ value = value
+ .mul_wrapping(ten)
+ .add_wrapping(T::Native::usize_as(rng.random_range(0..10)));
+ }
+ if rng.random::<bool>() {
+ value.neg_wrapping()
+ } else {
+ value
+ }
+ });
+ PrimitiveArray::<T>::from_iter_values(values)
+ .with_precision_and_scale(T::MAX_PRECISION, scale)
+ .unwrap()
+}
+
+/// Returns `array` with a fifth of its values null, at random positions
+fn with_random_nulls<T: DecimalType>(array: &PrimitiveArray<T>) ->
PrimitiveArray<T> {
+ let mut rng = StdRng::seed_from_u64(7);
+ let nulls = NullBuffer::from_iter((0..array.len()).map(|_|
rng.random_ratio(4, 5)));
+ PrimitiveArray::<T>::new(array.values().clone(), Some(nulls))
+ .with_data_type(array.data_type().clone())
+}
+
+/// Benchmarks `div` and `rem` of values with scale `scale` by a scalar, for
each pair of value
+/// and divisor digit counts in `div_cases` and `rem_cases`, and `div` of the
first `div` case
+/// on arrays of each length in `small_lens`
+///
+/// For `div` the divisor has scale 2, so `div` scales the values by 10^6. The
last `div` case
+/// overflows when scaled, which `div` handles one digit at a time. For `rem`
the divisor has
+/// scale `scale`, because `rem` scales the divisor to the larger scale, which
would change its
+/// digit count.
+fn benchmark_scalar<T: DecimalType>(
+ c: &mut Criterion,
+ name: &str,
+ scale: i8,
+ div_cases: &[(u32, u32)],
+ rem_cases: &[(u32, u32)],
+ small_lens: &[usize],
+) {
+ let mut group = c.benchmark_group(format!("{name}_scalar"));
+ group.throughput(Throughput::Elements(SIZE as u64));
+ let scale_factor = T::Native::usize_as(1_000_000);
+ let ops = [
+ ("div", div as Kernel, 2, div_cases),
+ ("rem", rem as Kernel, scale, rem_cases),
+ ];
+ let mut small = None;
+ for (op, kernel, divisor_scale, cases) in ops {
+ for (i, &(digits, divisor_digits)) in cases.iter().enumerate() {
+ let array = random_decimal::<T>(SIZE, digits, scale, 42);
+ let divisor = Scalar::new(random_decimal::<T>(1, divisor_digits,
divisor_scale, 42));
+ let id =
format!("{op}_{digits}_digits_by_{divisor_digits}_digits");
+ if op == "div" {
+ // Fail if a case no longer takes the path it's meant to
+ let overflowing = array
+ .values()
+ .iter()
+ .filter(|v| v.mul_checked(scale_factor).is_err())
+ .count();
+ let expected = if i + 1 == cases.len() { SIZE } else { 0 };
+ assert_eq!(overflowing, expected, "{name} {id}");
+ }
+ group.bench_function(format!("{id}/no_nulls"), |b| {
+ b.iter(|| hint::black_box(kernel(&array, &divisor).unwrap()))
+ });
+
+ if i == 0 {
+ // `try_unary` visits only the valid values when the array has
nulls
+ let with_nulls = with_random_nulls(&array);
+ group.bench_function(format!("{id}/mixed_nulls"), |b| {
+ b.iter(|| hint::black_box(kernel(&with_nulls,
&divisor).unwrap()))
+ });
+ if op == "div" {
+ small = Some((id, array, divisor));
+ }
+ }
+ }
+ }
+
+ // Small arrays, where the cost of building a divisor can outweigh the
per-value savings
+ let (id, array, divisor) = small.unwrap();
+ for &len in small_lens {
+ let array = array.slice(0, len);
+ group.throughput(Throughput::Elements(len as u64));
+ group.bench_function(format!("{id}/{len}_values"), |b| {
+ b.iter(|| hint::black_box(div(&array, &divisor).unwrap()))
+ });
+ }
+ group.finish();
+}
+
+fn decimal_scalar_division(c: &mut Criterion) {
+ // Values that fit after scaling and values that overflow. For each
overflowing value, `div`
+ // also builds an `ArrowError` and discards it before falling back.
+ benchmark_scalar::<Decimal32Type>(c, "decimal32", 2, &[(3, 4), (6, 4)],
&[(9, 4)], &[128]);
+ // A value that fits in 32 bits after scaling, a wider one, and one that
overflows
+ benchmark_scalar::<Decimal64Type>(
+ c,
+ "decimal64",
+ 2,
+ &[(3, 4), (12, 4), (15, 4)],
+ &[(18, 4)],
+ &[128],
+ );
+ // A value that fits in 64 bits after scaling, a wider one, a divisor
wider than 64 bits, and a
+ // value that overflows. `rem` doesn't scale the values, so it has no
overflow case. Building
+ // a divisor for these types costs more, so they also run on 1 and 16
values.
+ benchmark_scalar::<Decimal128Type>(
+ c,
+ "decimal128",
+ 10,
+ &[(10, 4), (30, 4), (30, 21), (34, 4)],
+ &[(10, 4), (30, 4), (30, 21)],
+ &[1, 16, 128],
+ );
+ // The same cases for 128 bits
+ benchmark_scalar::<Decimal256Type>(
+ c,
+ "decimal256",
+ 10,
+ &[(30, 4), (60, 4), (60, 40), (72, 4)],
+ &[(30, 4), (60, 4), (60, 40)],
+ &[1, 16, 128],
+ );
+}
+
+/// Benchmarks `multiply_fixed_point`, which computes each product in `i256`
and divides it by
+/// 10^(product scale - required scale)
+fn decimal_multiply_fixed_point(c: &mut Criterion) {
+ let mut group = c.benchmark_group("decimal128_multiply_fixed_point");
+ group.throughput(Throughput::Elements(SIZE as u64));
+ // Products that fit in 128 bits, wider products, and a divisor wider than
64 bits
+ for (digits, scale) in [(15, 10), (24, 10), (21, 20)] {
+ let left = random_decimal::<Decimal128Type>(SIZE, digits, scale, 1);
+ let right = random_decimal::<Decimal128Type>(SIZE, digits, scale, 2);
+
group.bench_function(format!("{digits}_digits_scale_{scale}_to_scale_6"), |b| {
+ b.iter(|| hint::black_box(multiply_fixed_point(&left, &right,
6).unwrap()))
+ });
+ }
+ group.finish();
+}
+
+criterion_group!(
+ benches,
+ decimal_scalar_division,
+ decimal_multiply_fixed_point
+);
+criterion_main!(benches);
diff --git a/arrow-arith/benches/integer_division.rs
b/arrow-arith/benches/integer_division.rs
new file mode 100644
index 0000000000..b76b9f05a1
--- /dev/null
+++ b/arrow-arith/benches/integer_division.rs
@@ -0,0 +1,78 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+use std::hint::black_box;
+
+use arrow_arith::numeric::{div, rem};
+use arrow_array::types::{Int32Type, Int64Type, UInt32Type, UInt64Type};
+use arrow_array::{ArrayRef, ArrowPrimitiveType, Datum, PrimitiveArray};
+use arrow_buffer::{ArrowNativeType, NullBuffer};
+use arrow_schema::ArrowError;
+use criterion::{Criterion, Throughput, criterion_group, criterion_main};
+use rand::distr::{Distribution, StandardUniform};
+use rand::rngs::StdRng;
+use rand::{RngExt, SeedableRng};
+
+const SIZE: usize = 8192;
+
+type Kernel = fn(&dyn Datum, &dyn Datum) -> Result<ArrayRef, ArrowError>;
+
+fn benchmark<T: ArrowPrimitiveType>(c: &mut Criterion, name: &str)
+where
+ StandardUniform: Distribution<T::Native>,
+{
+ let mut rng = StdRng::seed_from_u64(42);
+ let array = PrimitiveArray::<T>::from_iter_values((0..SIZE).map(|_|
rng.random()));
+ // A fifth of the values null, at random positions
+ let nulls = NullBuffer::from_iter((0..SIZE).map(|_| rng.random_ratio(4,
5)));
+ let with_nulls = PrimitiveArray::<T>::new(array.values().clone(),
Some(nulls));
+ let mut group = c.benchmark_group(format!("integer_division_{name}"));
+ group.throughput(Throughput::Elements(SIZE as u64));
+ for (op, kernel) in [("div", div as Kernel), ("rem", rem)] {
+ // 16 is a power of two, which a precomputed divisor can replace with
a shift or mask
+ for d in [13, 16] {
+ let divisor =
PrimitiveArray::<T>::new_scalar(T::Native::usize_as(d));
+ group.bench_function(format!("{op}_{d}/no_nulls"), |b| {
+ b.iter(|| black_box(kernel(black_box(&array),
black_box(&divisor)).unwrap()))
+ });
+ }
+ // `try_unary` visits only the valid values when the array has nulls
+ let divisor = PrimitiveArray::<T>::new_scalar(T::Native::usize_as(13));
+ group.bench_function(format!("{op}_13/mixed_nulls"), |b| {
+ b.iter(|| black_box(kernel(black_box(&with_nulls),
black_box(&divisor)).unwrap()))
+ });
+ }
+ // A small array, where building a divisor is a larger share of the work.
On fewer values,
+ // the fixed cost of each call is far larger than building a divisor for
these types.
+ let small = array.slice(0, 128);
+ let divisor = PrimitiveArray::<T>::new_scalar(T::Native::usize_as(13));
+ group.throughput(Throughput::Elements(small.len() as u64));
+ group.bench_function("div_13/128_values", |b| {
+ b.iter(|| black_box(div(black_box(&small),
black_box(&divisor)).unwrap()))
+ });
+ group.finish();
+}
+
+fn integer_division(c: &mut Criterion) {
+ benchmark::<Int32Type>(c, "int32");
+ benchmark::<UInt32Type>(c, "uint32");
+ benchmark::<Int64Type>(c, "int64");
+ benchmark::<UInt64Type>(c, "uint64");
+}
+
+criterion_group!(benches, integer_division);
+criterion_main!(benches);
