mbutrovich opened a new issue, #12167: URL: https://github.com/apache/arrow-rs/issues/12167
### Is your feature request related to a problem or challenge? Part of #11421. `i128` and `u128` division calls `__divti3` or `__udivti3` for every value, even with a literal divisor such as 10^18 (rustc 1.98.1, aarch64). On x86_64 these [build on the `div` instruction](https://github.com/rust-lang/rust/blob/b940084d7eb6a299eb4bfeb8e34901bc051e7ac4/library/compiler-builtins/compiler-builtins/src/int/specialized_div_rem/mod.rs#L189-L221), which divides 128 bits by 64. On other targets they use a [sequence of 64-bit hardware divides](https://github.com/rust-lang/rust/blob/b940084d7eb6a299eb4bfeb8e34901bc051e7ac4/library/compiler-builtins/compiler-builtins/src/int/specialized_div_rem/mod.rs#L142-L158). `i256::div_rem` is covered by #11451. #11467 added precomputed divisors for 32-bit and 64-bit integers. The decimal kernels that divide by a scalar need the same for the wider types. ### Describe the solution you'd like Add `DivisorU128`, `DivisorI128` and `DivisorI256` (and a `u256` form if the kernels need one) to `arrow-buffer`, following the API of #11467: each is a `#[non_exhaustive]` enum whose variants are branch-free types, and the variant set differs by type. Which variants the wider types get, such as `Up` for `u128`, is open. Tests are the ones from #11467 plus `10^k - 1`, `10^k`, `10^k + 1`, and values on each side of 2^64 (and 2^128 for `i256`). #### Choosing the variant per batch A kernel would pick the narrowest variant that fits a batch from a scan of the values' magnitude, so the API has to let a kernel build the 64-bit divisor for an `i128` divisor, or the 128-bit one for an `i256` divisor, when every value in the batch fits. One variant per type isn't enough: - The 128-bit variant alone made 18-digit `Decimal128` casts 16% slower than today (24.8 vs 21.3 us per 8192-value batch), while the 64-bit variant made them 1.9x faster (11.5 us). - In Comet, the 128-bit variant made `i256` products that fit in `i128` 4.2x faster than today (63.4 vs 266.5 us). - The scan cost 4% to 8% when it found wide values. The choice can't come from the declared precision, because arrow doesn't check stored values against it ([`with_precision_and_scale`](https://github.com/apache/arrow-rs/blob/6b34163d51aa59f7cac2edcb74e8bd1ddc6b9120/arrow-array/src/array/primitive_array.rs#L1709-L1715)). Whether the scan lives in `arrow-buffer` or in each kernel should be settled in this PR, because the API is permanent once released. #### Construction cost In the prototype, building a divisor costs 22 ns for `i128` and 451 ns for `i256`. The `i256` constructor divides one bit at a time and could use Algorithm D instead. That's at most 0.45 us per 8192-value batch. For scalars and very small batches plain division is cheaper, so kernels need a row-count threshold. ### Describe alternatives you've considered Precomputed tables of the reciprocals of 10^k would remove the construction cost for decimal rescaling. The cost is small enough per batch that I'd start without them. ### Additional context Comet's `wide_decimal` benchmark evaluates the `WideDecimalBinaryExpr` multiply on an 8192-row batch, with each method in the kernel. Today is `div_round_half_up`. Times are in us per batch on an Apple M5 Max, medians of three runs. <img width="1600" height="884" alt="Image" src="https://github.com/user-attachments/assets/3e26139c-8ea7-4b78-9c99-08dcf5315c15"; /> | Case | Today | One Algorithm D call, remainder by multiply | Granlund-Montgomery, 256-bit | Granlund-Montgomery, 128-bit when products fit | |---|---|---|---|---| | The existing [`multiply`](https://github.com/apache/datafusion-comet/blob/8d0bb01a5a99924024e07c1722e6eddd9260e167/native/spark-expr/benches/wide_decimal.rs#L156) case, 30-digit products | 266.5 | 233.8 (1.1x) | 148.4 (1.8x) | **63.4 (4.2x)** | | 48-digit products, 34-digit quotients | 398.1 | 301.9 (1.3x) | **147.1 (2.7x)** | 153.2 (2.6x) | | 42-digit products, 8-digit quotients | 351.5 | 234.5 (1.5x) | **137.1 (2.6x)** | 143.6 (2.4x) | The prototype's divisors are in [`divproto/`](https://github.com/mbutrovich/arrow-rs/tree/ee0358cd48c9bdeb7ca5a4c52d479f949c17f736/divproto). -- 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]
