mbutrovich opened a new pull request, #11467: URL: https://github.com/apache/arrow-rs/pull/11467
# Which issue does this PR close? - Part of #11421. # Rationale for this change See #11421. This is the first divisor PR in that epic, so it settles the API that the `i128` and `i256` divisors, the sealed trait and the kernel changes build on. # What changes are included in this PR? This PR adds `DivisorU32`, `DivisorI32`, `DivisorU64` and `DivisorI64` to `arrow-buffer`, exported at the crate root next to `i256`. No kernel uses them yet. - `new(divisor)` returns `None` for a zero divisor. - `div_rem(n)` returns `(n / divisor, n % divisor)`. For the signed types that is `(n.wrapping_div(divisor), n.wrapping_rem(divisor))`, so `MIN / -1` returns `(MIN, 0)`. - `checked_div_rem(n)` on the signed types returns `None` only for `MIN / -1`, the same as `checked_div` and `checked_rem`. The unsigned types don't have it, because it could never return `None` there. `new` computes the multiplier from figure 4.1 of [Granlund and Montgomery (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf). A divisor that is a power of two uses a shift and a mask instead. That choice is a field of the divisor, so `div_rem` branches on it, but the branch doesn't depend on the dividend, and LLVM tests it once before the loop and emits a separate loop for each case. The signed types divide the magnitudes with the unsigned type and apply the signs with `(x ^ s) - s`. Writing the sign handling as `if` expressions made LLVM compute the division for both `n` and `-n` in each iteration and select one, which made `DivisorI32` slower than `/`. A macro generates the two unsigned types and another generates the two signed types, so each method is written once. # Are these changes tested? The unit tests compare `div_rem` with `/` and `%` for the unsigned types, and `div_rem` and `checked_div_rem` with `wrapping_div`, `wrapping_rem`, `checked_div` and `checked_rem` for the signed types. For the unsigned types the divisors are 1 to 2000, every power of two and its neighbors, `10^k - 1`, `10^k` and `10^k + 1`, `MAX`, `MAX - 1` and random values, and the dividends are 0, 1, 2, `MAX`, `MAX - 1`, `2^(N-1)` and its neighbors, and random values. For the signed types the divisors are magnitudes 1 to 1000, powers of two and powers of ten with their neighbors, and random values, each with both signs, plus `MIN`, `MAX`, -1 and 1. Their dividends are 0, 1, -1, `MIN`, `MIN + 1`, `MAX`, and random values with both signs. Each divisor is also tested with the dividends next to it and with seven times it. Each public method has a doctest. The new `divisor` benchmark divides 8192 random values by 13 and by 16 with `/` and `%` and with `div_rem`. On an Apple M5 Max, in one run: <img width="1600" height="1380" alt="divisor-types" src="https://github.com/user-attachments/assets/9ca324ac-5ed5-46f2-941f-d9a07fa7f718"; /> <details><summary>Numbers behind the chart</summary> | Case | `/` or `%` | `div_rem` | Speedup | |---|---|---|---| | `u32` div 13 | 3.68 us | 0.71 us | 5.1x | | `u32` div 16 | 3.65 us | 0.29 us | 12.7x | | `u32` rem 13 | 3.67 us | 0.84 us | 4.4x | | `u32` rem 16 | 3.68 us | 0.28 us | 13.3x | | `i32` div 13 | 3.76 us | 1.31 us | 2.9x | | `i32` div 16 | 3.83 us | 0.72 us | 5.3x | | `i32` rem 13 | 3.81 us | 1.33 us | 2.9x | | `i32` rem 16 | 3.87 us | 0.61 us | 6.4x | | `u64` div 13 | 3.69 us | 1.83 us | 2.0x | | `u64` div 16 | 3.69 us | 0.64 us | 5.7x | | `u64` rem 13 | 3.74 us | 2.84 us | 1.3x | | `u64` rem 16 | 3.77 us | 0.64 us | 5.9x | | `i64` div 13 | 4.08 us | 2.75 us | 1.5x | | `i64` div 16 | 4.06 us | 1.53 us | 2.7x | | `i64` rem 13 | 3.98 us | 4.80 us | 0.8x | | `i64` rem 16 | 4.02 us | 3.02 us | 1.3x | </details> The 32-bit loops compile to NEON code, because their 32x32 to 64-bit multiply has vector forms. The 64-bit multiply-high has no NEON form, so the 64-bit loops are scalar or use two lanes. `i64` remainder by 13 is slower than `%` on this machine, where `%` takes 0.49 ns per value. The integer kernel PR will decide per type which kernels use the divisor, with numbers from the benchmark bot on both arm64 and x86_64. # Are there any significant user-facing changes? Four new public types in `arrow-buffer`. Nothing existing changes. ## AI 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]
