mbutrovich commented on issue #11451: URL: https://github.com/apache/arrow-rs/issues/11451#issuecomment-6064895595
The `#[inline]` change is in #11457. On an Apple M5 Max it made `i256_div_rem small divisor` 3.6% faster, but the benchmark bot measured no change on either architecture ([arm64](https://github.com/apache/arrow-rs/pull/11457#issuecomment-6064702970), [x86_64](https://github.com/apache/arrow-rs/pull/11457#issuecomment-6064692912)): | Runner | Bench | `main` | #11457 | |---|---|---|---| | arm64 (`c4a-highmem-16`) | small divisor | 42.9 us | 42.9 us | | arm64 (`c4a-highmem-16`) | small quotient | 25.6 us | 25.6 us | | x86_64 (`c4-highmem-16`) | small divisor | 10.1 us | 10.2 us | | x86_64 (`c4-highmem-16`) | small quotient | 21.3 us | 22.1 us | The out-of-line calls aren't where the time goes. The same runs show a different gap. Each iteration does 1024 divisions, so the small-divisor case costs about 42 ns per division on arm64 and 10 ns on x86_64, while the small-quotient case, which runs Algorithm D, costs 25 ns and 21 ns. The small-divisor case calls [`div_rem_word`](https://github.com/apache/arrow-rs/blob/9c07b17255ee65a70c1885368c1d91ca737521de/arrow-buffer/src/bigint/div.rs#L182-L211) once per word. On x86_64 that's a `div` instruction through inline assembly. On other targets it computes `u128 / u128`, and LLVM can't prove the quotient fits in 64 bits, so `div_rem::<4>` makes four calls to `__udivti3`. I haven't profiled it. The M5 Max doesn't show the same gap (15.9 us for small divisor and 16.4 us for small quotient), so the cost of `__udivti3` may depend on the core. Should the next step for non-x86 targets be a 128-by-64 division built from 64-bit operations? The divisor is the same for every word in one `div_rem_small` call, so the 2-by-1 division with a precomputed reciprocal from [Moller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf) could fit. -- 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]
