mbutrovich opened a new pull request, #12232: URL: https://github.com/apache/arrow-rs/pull/12232
# Which issue does this PR close? - Closes #12167. - Part of #11421. # Rationale for this change See #12167. # What changes are included in this PR? - `DivisorI128` and `DivisorI256` in `arrow-buffer`, with the `PowerOfTwo` and `AddIndicator` variants that `DivisorI64` has. No kernel uses them yet. - There is no `DivisorU128` or `u256` form. Every kernel in #11421 divides signed values, and a `u256` isn't needed for `Display for i256` because a signed divisor of 10^38 divides `i256::MIN`. Either type can be added later without a breaking change. - The API has no separate narrow variant. A kernel that finds every value of a batch fits in `i64` divides with `DivisorI64`, and one whose `i256` values fit in `i128` divides with `DivisorI128`. The rustdoc of each type says when the results match, which excludes a divisor of -1. - `new` isn't a `const fn` for these types, because it divides with `i256`. Making it `const` later is additive. - `AddIndicator` uses figure 5.1 of Granlund and Montgomery, as `DivisorI64` does. The prototype in #11421 used figure 4.1 on `|n|` with a sign fix. In a comparison where every form used the same high multiply, figure 5.1 had the fewest instructions per value on aarch64, x86_64 and `x86-64-v3`, and it was the fastest form on an Apple M5 Max (table below). - The code comments say where the code departs from the paper and why. The `i256` variants are the only divisor methods that branch on the divisor, on the shift, because a branch-free shift was slower. <details><summary>Forms of <code>AddIndicator</code>, in us per 8192 full-width random values on an Apple M5 Max</summary> The forms are figure 5.1, figure 4.1 on `|n|` with a sign fix (the #11421 prototype), and an exact N-bit multiplier on `|n|` at N - 1 bits of precision with no add. Speedups are over the operator (`/` and `%` for `i128`, `i256::wrapping_div_rem` for `i256`). The `i256` rows compare figure 5.1 as in this PR, at `#[inline(always)]`, with the other two forms out of line, so only the `i128` rows compare the forms on equal terms. | Case | Operator | Figure 5.1 | Figure 4.1 on `\|n\|` | No add on `\|n\|` | |---|---|---|---|---| | `i128` `/` 7 | 18.44 | 11.08 (1.67x) | 14.53 (1.27x) | 11.79 (1.56x) | | `i128` `/` 10^18 | 65.12 | 11.04 (5.90x) | 14.52 (4.49x) | 11.77 (5.53x) | | `i128` `%` 7 | 18.43 | 12.22 (1.51x) | 17.70 (1.04x) | 14.64 (1.26x) | | `i128` `%` 10^18 | 65.41 | 12.22 (5.35x) | 17.77 (3.68x) | 14.64 (4.47x) | Instructions per value in the `i128` loop, `/` and `%`: | Form | aarch64 | x86_64 | `x86-64-v3` | |---|---|---|---| | Figure 5.1 | 40 / 42 | 47 / 53 | 41.5 / 51 | | Figure 4.1 on `\|n\|` | 45 / 49 | 52 / 59 | 47 / 54 | | No add on `\|n\|` | 39 / 43 | 46 / 51 | 43 / 49 | </details> # Are these changes tested? `test_divisor_i128`, `test_divisor_i256` and `test_variant_signed` in `arrow-buffer/src/divisor.rs` compare the divisors with the operators. The values include each side of every power of two and power of ten, which covers the 64-bit limbs of the multiply and the edges of the narrower types. Each public method has a doctest. The `divisor` benchmark adds `i128` and `i256` cases with divisors 7, 16 and 10^18 or 10^38, on full-width values and on values that fit in the next narrower type, where the operators take a faster path. Bot runs: TODO(Matt) link the Neoverse-V2, Xeon 8581C and `x86-64-v3` runs. On values that fit in the next narrower type, the divisor gains least, and `i256` `%` was about as fast as `i256::wrapping_div_rem`, which divides such values with one `u128` division. Kernels should divide those batches with the narrower divisor. # Are there any significant user-facing changes? No existing API changes. The PR adds `DivisorI128`, `PowerOfTwoDivisorI128`, `AddIndicatorDivisorI128`, `DivisorI256`, `PowerOfTwoDivisorI256` and `AddIndicatorDivisorI256` to `arrow-buffer`. # AI usage disclosure I wrote this PR with help from Claude but understand and support the core approach, implementation, and test coverage. -- 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]
