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-11530-6eff9554a1d07022e0cad72d123699eb64b3355b in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
commit 603929546f8231ecbe0573093f17048c064ff5f2 Author: Matt Butrovich <[email protected]> AuthorDate: Wed Oct 14 19:53:55 2026 +0000 perf(arrow-buffer): divide `i256` magnitudes below 2^128 with one `u128` division (#11530) # Which issue does this PR close? - Part of #11451. - Part of #11421. # Rationale for this change See #11451. This is its second item, the fast path for operands that fit in `i128`. The path applies where `i256` holds the product of two `Decimal128` values before a rescale, as in `multiply_fixed_point` and Comet's [`div_round_half_up`](https://github.com/apache/datafusion-comet/blob/8d0bb01a5a99924024e07c1722e6eddd9260e167/native/spark-expr/src/math_funcs/wide_decimal_binary_expr.rs#L123-L146), and to `Decimal256` columns whose values have at most 38 digits. # What changes are included in this PR? `i256::div_rem` divides the magnitudes with one `u128` division when both are below 2^128, and with the long division otherwise. The checks before it and the sign handling after it don't change. This covers every pair of operands that fits in `i128`, and `i128::MIN / -1` needs no special case because the magnitudes are taken first. # Are these changes tested? `test_div_rem_powers_of_ten` and `test_i256_fuzz` in `arrow-buffer/src/bigint/mod.rs` cover both sides of the new boundary, with dividends such as `i256::from_parts(u128::MAX, 0)` and `i256::from_parts(0, 1)`, both signs, and every power of ten up to 10^76 as the divisor. The benchmark bot ran the `Decimal256` cases of `decimal_downscale` in `cast_decimal` on [x86_64](https://github.com/apache/arrow-rs/pull/11530#issuecomment-6133792043) and [arm64](https://github.com/apache/arrow-rs/pull/11530#issuecomment-6133602543), and `decimal256_scalar` in `decimal_division` on [x86_64](https://github.com/apache/arrow-rs/pull/11530#issuecomment-6133766286) and [arm64](https://github.com/apache/arrow-rs/pull/11530#issuecomment-6133579958). The runners are a Xeon Platinum 8581C and a Neoverse-V2. <img width="1600" height="1636" alt="i256-fast-path-bot" src="https://github.com/user-attachments/assets/5a5c6cf6-9553-4282-af3e-cd1f06358c30"; /> <details><summary>Numbers behind the chart</summary> In us with no nulls, per 8192 values for the casts and per 1024 values for the division: | Case | Magnitudes | x86_64: `main` | This PR | arm64: `main` | This PR | |---|---|---|---|---|---| | `Decimal256` (76, 10) to (76, 2), 38 digits | below 2^128 | 272.2 | 209.7 | 469.1 | 304.4 | | `Decimal256` (41, 20) to `Decimal128` (38, 6), 30 digits | below 2^128 | 298.3 | 184.0 | 499.7 | 375.6 | | `div_30_digits_by_4_digits` | below 2^128 | 38.2 | 32.3 | 51.3 | 42.6 | | `rem_30_digits_by_4_digits` | below 2^128 | 37.3 | 31.9 | 48.6 | 40.3 | | `Decimal256` (76, 10) to (76, 2), 60 digits | wide | 277.0 | 302.4 | 750.9 | 748.2 | | `Decimal256` (76, 20) to `Decimal128` (38, 6), 48 digits, fallible | wide | 296.6 | 305.3 | 782.4 | 788.1 | | `Decimal256` (76, 40) to `Decimal128` (38, 6), 42 digits, fallible | wide | 616.2 | 603.3 | 701.9 | 698.4 | | `div_60_digits_by_4_digits` | wide | 37.4 | 38.8 | 77.7 | 78.1 | | `div_60_digits_by_40_digits` | wide | 56.6 | 56.7 | 88.8 | 88.6 | | `div_72_digits_by_4_digits`, through `scaled_div` | wide | 429.6 | 384.4 | 553.8 | 555.1 | </details> The first four cases take the new path. The cases with nulls gain by about the same amount, and `div_30_digits_by_4_digits` on 128, 16 and 1 values gains 1.07x to 1.20x. The rest have a magnitude of at least 2^128 and pay for the check before the long division. The cost shows when the divisor fits in 64 bits and the long division is short: the 60-digit cast on x86_64 is 6% to 9% slower, and `div_60_digits_by_4_digits` 4% slower. With a 40-digit divisor there is no measurable cost. The bot runs don't include #11528, so the casts call `div_rem` twice per value. The x86_64 gains for the 72-digit division and the 42-digit casts don't come from this change, because those values take the long division. With #11528 applied on both sides, on an Apple M5 Max, the cost on wide values depends on the build setting. With LTO and one codegen unit, as DataFusion and Comet build their releases, it is about 2 ns per division, which makes `div` and `rem` of 60 digits by 4 digits 7% slower. Forcing loop alignment with `-C llvm-args=-align-loops=64` didn't change it. The precomputed divisors in #11421 would take `Decimal256` `/` and `%` by a scalar off this path. <details><summary>Apple M5 Max by build setting</summary> With rustc 1.99.0, criterion with a 1 s warm-up and 2 s of measurement, and #11528 applied on both sides, as the speedup over `main` with no nulls: | Case | Default profile | Thin LTO, 1 codegen unit | Fat LTO, 1 codegen unit | |---|---|---|---| | `cast_decimal`: `Decimal256` (76, 10) to (76, 2), 38 digits | 1.64x | 1.33x | 1.33x | | `cast_decimal`: `Decimal256` (41, 20) to `Decimal128` (38, 6), 30 digits | 1.62x | 1.48x | 1.44x | | `decimal_division`: `decimal256_scalar/div_30_digits_by_4_digits` | 1.17x | 1.18x | 1.17x | | `decimal_division`: `decimal256_scalar/rem_30_digits_by_4_digits` | 1.18x | 1.17x | 1.17x | | `cast_decimal`: `Decimal256` (76, 10) to (76, 2), 60 digits | 0.97x | 1.02x | 1.00x | | `cast_decimal`: 48-digit fallible casts | 0.97x to 0.98x | 1.00x to 1.01x | 1.00x to 1.01x | | `cast_decimal`: 42-digit fallible casts | 0.96x to 0.97x | 0.99x to 1.11x | 0.94x to 0.96x | | `decimal_division`: `div` and `rem` of 60 digits by 4 digits | 0.98x, 0.99x | 0.93x, 0.93x | 0.93x, 0.92x | | `decimal_division`: `div` and `rem` of 60 digits by 40 digits | 1.00x, 1.00x | 0.99x, 1.00x | 0.97x, 0.97x | | `i256`: `i256_div_rem` | 0.98x | 1.00x | 0.99x | The thin LTO baseline of the 38-digit cast without nulls was disturbed, so that cell uses the case with nulls, which costs the same. </details> `multiply_fixed_point` also takes the new path, but #11526 changes its per-row divisions, so its numbers are left out until that merges. # 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. --- arrow-buffer/src/bigint/mod.rs | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/arrow-buffer/src/bigint/mod.rs b/arrow-buffer/src/bigint/mod.rs index 823ec7d28d..95cd7ff12d 100644 --- a/arrow-buffer/src/bigint/mod.rs +++ b/arrow-buffer/src/bigint/mod.rs @@ -496,9 +496,16 @@ impl i256 { let a = self.wrapping_abs(); let b = other.wrapping_abs(); - let (div, rem) = div_rem(&a.as_digits(), &b.as_digits()); - let div = Self::from_digits(div); - let rem = Self::from_digits(rem); + let (div, rem) = if a.high == 0 && b.high == 0 { + // Magnitudes below 2^128 don't need the long division + ( + Self::from_parts(a.low / b.low, 0), + Self::from_parts(a.low % b.low, 0), + ) + } else { + let (div, rem) = div_rem(&a.as_digits(), &b.as_digits()); + (Self::from_digits(div), Self::from_digits(rem)) + }; Ok(( if self.is_negative() == other.is_negative() {
