This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-11427-4c67abc4505344425fd9d5172037bd0f468f8b42 in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
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);
