You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by gi...@apache.org on 2026/10/14 23:53:14 UTC
(arrow-rs) 01/01: perf(arrow-buffer): divide `i256` magnitudes below 2^128 with one `u128` division (#11530)
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-73f8d3fccc16b92f4c381f1ae8eecc5ad2631c86
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
commit e04a79c35a151eda5f046ae3ff8b3bd18eb8124e
Author: Matt Butrovich <mb...@users.noreply.github.com>
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() {