mbutrovich commented on PR #11467: URL: https://github.com/apache/arrow-rs/pull/11467#issuecomment-6426381403
Thanks @mightsleep and @devanbenz. I adopted the `u32` split, the signed remainder, and the correctness checks at the ends of the last quotient steps. The enums are now `#[non_exhaustive]`, so a later variant isn't a breaking change. The benchmark bot compared the new forms with the PR's previous ones in the same run, on [x86_64](https://github.com/apache/arrow-rs/pull/11467#issuecomment-6426118997) (Xeon Platinum 8581C, `x86-64-v3`) and [arm64](https://github.com/apache/arrow-rs/pull/11467#issuecomment-6426111643) (Neoverse-V2). The ratios are previous time over new time. <img width="1600" height="932" alt="divisor-variants-bot-x86" src="https://github.com/user-attachments/assets/5a539a7a-d4ca-42a4-a9b5-d76984d853ed"; /> <img width="1600" height="932" alt="divisor-variants-bot-arm" src="https://github.com/user-attachments/assets/47120a34-e3fa-46db-93c8-78032c676636"; /> | Case | Variant | x86_64 `/` | x86_64 `%` | arm64 `/` | arm64 `%` | |---|---|---|---|---|---| | `u32` by 13 | `Up` | 1.24x | 1.27x | 1.60x | 1.27x | | `u32` by 7 | `Down` | 0.97x | 1.13x | 1.27x | 1.21x | | `u64` by 13 | `Up` | 0.94x | 1.13x | 1.58x | 1.17x | | `i32` by 13 | `AddIndicator` | 1.00x | 1.16x | 1.00x | 1.34x | | `i64` by 13 | `AddIndicator` | 1.00x | 1.05x | 1.00x | 1.15x | On an Apple M5 Max the same comparison gave 1.47x and 1.38x for `u32` with `Up`, 1.19x and 1.17x for `u32` with `Down`, 1.78x and 1.41x for `u64` with `Up`, and 1.28x and 1.57x for the `i32` and `i64` remainders. Two cases lose a little on the Xeon. `u64 /` with `Up` is 0.94x. In the thin-LTO build for `x86-64-v3`, that loop computes each high multiply with a scalar `mulx` and moves it into a vector register, and `Up` removes only vector instructions from it. `u32 /` with `Down` is 0.97x. Both gain 1.13x on `%`, and both gain on the two Arm CPUs, so I kept them. A few things I tried and left out: - `Down` for `u64` was 0.71-0.73x on the Xeon and 0.95-0.97x for `%` on the M5, though it gained 1.10-1.13x on Neoverse-V2. - Computing `Down` as `m * n + m` in the double-width product instead of a saturating increment was 0.42-0.78x on every CPU. LLVM rewrites it as `m * (n + 1)` in 64-bit lanes, which needs a full 64-bit multiply. - The direct remainder from figures 1 and 2 of Lemire, Kaser and Kurz was 0.67-0.71x on the M5. It needs a 64-bit low multiply and a 64x64 high multiply per value, so it vectorizes worse than the quotient-based remainder in 32-bit lanes. -- 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]
