mbutrovich opened a new pull request, #11580: URL: https://github.com/apache/arrow-rs/pull/11580
# Which issue does this PR close? - Part of #11451. - Part of #11421. # Rationale for this change Outside x86_64, [`div_rem_word`](https://github.com/apache/arrow-rs/blob/418340d5188f6e2949c4a0545b3e437dfdc848f8/arrow-buffer/src/bigint/div.rs#L186-L211) divides a two-word number by one word with a `u128` division, which is a call to `__udivti3`. [`div_rem_small`](https://github.com/apache/arrow-rs/blob/418340d5188f6e2949c4a0545b3e437dfdc848f8/arrow-buffer/src/bigint/div.rs#L61-L73) calls it once per word, so dividing an `i256` by a divisor below 2^64 makes four calls ([comment](https://github.com/apache/arrow-rs/issues/11451#issuecomment-6064895595)). # What changes are included in this PR? Outside x86_64 and under Miri, `div_rem_small` shifts both operands so that the divisor's top bit is set. It computes a reciprocal of the divisor once with algorithm 2 of [Moller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf), which uses a 256-entry table and multiplies. It then divides each word with their algorithm 4, which uses one full multiply, one low multiply and two corrections, and no divide. x86_64 keeps the `div` instruction. Computing the reciprocal with a `u128` division instead made the `i256` bench slower than `main`, because that one `__udivti3` call cost more than the four it replaced. Dividends and divisors whose magnitudes are both below 2^128 still take the `u128` division from #11530. This change applies to wider dividends with a divisor below 2^64, such as `Decimal256` division of two arrays with more than 38 digits in the scaled dividend. # Are these changes tested? The new tests in `arrow-buffer/src/bigint/div.rs` compile on every target: - `test_reciprocal_word` checks the reciprocal against a `u128` division for the divisors 2^63 and `u64::MAX` and their neighbors, the divisors at and next to each boundary between table entries, and random divisors. - `test_div_rem_word_reciprocal` checks each word's division against `u128` division, including an input that reaches the second correction. - `test_div_rem_small_reciprocal` compares the new path with the per-word `div_rem_word` path for every normalization shift, powers of ten up to 10^19 and their neighbors, one, two and four words, and random inputs. The existing `test_i256_fuzz` and `test_div_rem_powers_of_ten` reach the new path on targets other than x86_64 and under Miri. The benchmark bot ran `i256_div_rem` in the `i256` benchmark, whose rows each have their own divisor, on [x86_64](TODO) and [arm64](TODO). The runners are a Xeon Platinum 8581C and a Neoverse-V2. TODO: chart <details><summary>Numbers behind the chart</summary> In us per 1024 divisions: | Case | x86_64: `main` | This PR | arm64: `main` | This PR | |---|---|---|---|---| | `small divisor` | TODO | TODO | TODO | TODO | | `small quotient` | TODO | TODO | TODO | TODO | </details> `small quotient` divides by divisors wider than 64 bits, which this change doesn't reach. <details><summary>Apple M5 Max</summary> With rustc 1.99.0, in us per 1024 divisions: | Case | `main` | This PR | |---|---|---| | `small divisor` | 17.5 | 13.5 | | `small quotient` | 16.9 | 16.6 | </details> # 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. -- 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]
