mbutrovich commented on PR #11467: URL: https://github.com/apache/arrow-rs/pull/11467#issuecomment-6085517937
Thanks @andygrove. I made the API change you suggested and adopted figure 5.2, and I updated the PR description to match the new API and numbers. The numbers below are from an Apple M5 Max with rustc 1.99.0, in us per 8192 values, from the PR's `divisor` benchmark unless I say otherwise. ### Hoisting the power-of-two branch > My main concern is the premise that LLVM moves the `power_of_two` branch out of the loop. You were right, and your thin LTO numbers reproduce here. I found two separate problems. The first is how the loop reaches the divisor. The benchmark's closure captured the divisor by reference, which fits the per-element loads you saw in the disassembly. Moving a copy of the divisor into the closure (`move |x| d.div_rem(*x)`) fixed every case in both the default and the thin LTO build. Through `unary`, a `move` closure at the call site didn't help. [`unary` wraps the closure in `map(|v| op(*v))`](https://github.com/apache/arrow-rs/blob/412dfa590c4659573bf57d77f3f712fb77d9df2e/arrow-array/src/array/primitive_array.rs#L927-L936), which captures `op` by reference, and changing only that line to `map(move |v| op(*v))` fixed it. I'll open a separate PR for that change, since it affects every `unary` caller that captures state. The second is that `move` alone wasn't enough at every optimization level. At `opt-level=2`, the power-of-two path gave no gain even with `move`: `u32 % 16` took 1.11 us, the same as `u32 % 13`. So the API now does what you suggested. `new` returns an enum with a `PowerOfTwo` variant and a `Multiplier` variant, and each variant's methods are branch-free. A kernel matches on the variant once, outside the loop, and moves the variant into its closure. The enum also has `wrapping_div_rem`, which matches on each call, for callers that divide a few values. The comment at [`divisor.rs:80`](https://github.com/apache/arrow-rs/blob/7d3e750bacf5ab46e465b2241597a86de054050f/arrow-buffer/src/divisor.rs#L80) and the sentence in the PR description went away with the branch. With thin LTO, your cases now look like this: | Case | `/` or `%` | Before | After | |---|---|---|---| | `u32 % 13` | 3.73 | 4.05 | 0.86 | | `u32 % 16` | 3.77 | 2.03 | 0.30 | | `i32 / 13` | 3.64 | 5.14 | 0.97 | | `i32 / 16` | 3.66 | 3.27 | 0.73 | | `i64 / 13` | 3.70 | 4.94 | 2.16 | | `i64 % 16` | 3.79 | 3.04 | 1.31 | At `opt-level=2`, the power-of-two cases with the old API and a `move` closure, against the new API: | Case | `/` or `%` | Old API with `move` | New API | |---|---|---|---| | `u32 % 16` | 3.91 | 1.11 | 0.31 | | `i32 / 16` | 4.23 | 1.47 | 0.73 | | `u64 % 16` | 4.06 | 2.04 | 0.65 | | `i64 % 16` | 3.87 | 2.69 | 1.34 | <details><summary>All cases with the new API</summary> | Case | `/` or `%`, default | Divisor, default | `/` or `%`, thin LTO | Divisor, thin LTO | `/` or `%`, `opt-level=2` | Divisor, `opt-level=2` | |---|---|---|---|---|---|---| | `u32 / 13` | 3.63 | 0.73 | 3.65 | 0.73 | 3.62 | 0.74 | | `u32 % 13` | 3.66 | 0.86 | 3.73 | 0.86 | 3.86 | 0.87 | | `u32 / 16` | 3.64 | 0.28 | 3.63 | 0.29 | 3.62 | 0.30 | | `u32 % 16` | 3.69 | 0.28 | 3.77 | 0.30 | 3.91 | 0.31 | | `i32 / 13` | 3.63 | 0.97 | 3.64 | 0.97 | 4.12 | 0.98 | | `i32 % 13` | 3.68 | 1.09 | 3.71 | 1.09 | 3.96 | 1.11 | | `i32 / 16` | 3.63 | 0.73 | 3.66 | 0.73 | 4.23 | 0.73 | | `i32 % 16` | 3.70 | 0.62 | 3.71 | 0.62 | 3.75 | 0.62 | | `u64 / 13` | 3.68 | 1.82 | 3.70 | 1.84 | 3.69 | 1.73 | | `u64 % 13` | 3.75 | 2.83 | 3.81 | 2.94 | 4.09 | 2.87 | | `u64 / 16` | 3.73 | 0.64 | 3.71 | 0.66 | 3.69 | 0.63 | | `u64 % 16` | 3.78 | 0.64 | 3.81 | 0.65 | 4.06 | 0.65 | | `i64 / 13` | 3.69 | 2.13 | 3.70 | 2.16 | 3.90 | 2.16 | | `i64 % 13` | 3.77 | 3.32 | 3.76 | 3.59 | 4.02 | 3.27 | | `i64 / 16` | 3.69 | 1.53 | 3.70 | 1.53 | 3.84 | 1.54 | | `i64 % 16` | 3.80 | 1.31 | 3.79 | 1.31 | 3.87 | 1.34 | </details> > Have the benchmark call the divisor through `unary`, as the kernels will, and check that the inner loop is vectorized in the bot's thin-LTO build before using its numbers. `arrow-buffer` can't depend on `arrow-array`, so the benchmark can't call `unary`. It now does what a kernel will do: it matches on the variant once and maps the values with a `move` closure. The kernel PR will measure the `unary` path with the `integer_division` benchmark from #11427. I agree about the earlier bot runs. They measured the by-reference loop, so I'll rerun the bot on the new commit before anything uses those numbers. ### Figure 5.2 for the signed types > Figure 5.2 divides with a signed multiplier and `smulh`, with no `abs` and one sign fix instead of two. Thanks for prototyping this. The signed `Multiplier` variant now uses figure 5.2 of [Granlund and Montgomery (1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf), and the signed `PowerOfTwo` variant shifts with a bias of `|d| - 1` for negative dividends, so the signed types no longer use the unsigned ones. `i64 % 13` went from 5.11 to 3.32 us in the default build, against 3.77 for `%`, so on this machine the divisor is now faster than `/` and `%` in all 32 cases in the default, thin LTO and `opt-level=2` builds. `i32 / 13` went from 1.32 to 0.97. Besides the unit tests, I compared both signed and unsigned results against `wrapping_div`, `wrapping_rem`, `checked_div` and `checked_rem` for every 32-bit dividend with 70 divisors, and for 200M random 64-bit pairs, with no mismatches. ### Naming > Here the wrapping version on the signed types is `div_rem`. The sealed trait will cover both, so it would help to pick one convention now All four types now use `wrapping_div_rem`, to match `i256`. > A `checked_div_rem` on the unsigned types that always returns `Some` would also give the trait the same set of methods on every type. I'd like to keep `checked_div_rem` off the types where it can't fail, for two reasons. The first is consistency with the rest of arrow-rs. The inherent `checked_*` methods on `i256` and the interval types can all return `None`. Methods that can't fail exist only where a trait needs the same set of methods on every type, such as [`ArrowNativeTypeOp::add_checked` for floats](https://github.com/apache/arrow-rs/blob/412dfa590c4659573bf57d77f3f712fb77d9df2e/arrow-array/src/arithmetic.rs#L308-L320), which returns `Ok(self + rhs)`. The sealed trait in #11421 is where the uniform set belongs, and it can implement `checked_div_rem` for the unsigned types the same way. The second is performance in the kernels. When the divisor can't fail, a kernel can use `unary` instead of `try_unary`, and the difference is large. I timed a `Multiplier` divisor by 13 with `unary` and `wrapping_div_rem`, against `try_unary` and a closure that returns `Some(d.wrapping_div_rem(x).0)`, which is what an always-`Some` `checked_div_rem` inlines to: | Case | `unary`, no nulls | `try_unary`, no nulls | `unary`, every fifth value null | `try_unary`, every fifth value null | |---|---|---|---|---| | `u32 / 13` | 0.72 | 0.88 | 0.72 | 4.35 | | `i32 / 13` | 0.95 | 1.14 | 0.95 | 4.51 | | `u64 / 13` | 1.68 | 2.36 | 1.70 | 4.86 | With nulls, [`try_unary` visits only the valid slots](https://github.com/apache/arrow-rs/blob/412dfa590c4659573bf57d77f3f712fb77d9df2e/arrow-array/src/array/primitive_array.rs#L1001-L1023), one index at a time, while `unary` computes every slot. A divisor type without a `checked_div_rem` that can't fail steers kernels to `unary`. The same reasoning applies to the signed `Multiplier` variant. Its divisor has a magnitude of at least 3, so its quotient can't overflow, and it has only `wrapping_div_rem`. Only the signed `PowerOfTwo` variant, which holds -1, and the signed enum have `checked_div_rem`. A kernel can test for -1 once, outside the loop, and use `unary` for every other divisor. ### Smaller points > `new` could be a `const fn` `new` is a `const fn` now, and so are `wrapping_div_rem` and `checked_div_rem`. A test builds `const` divisors. > `checked_div_rem` recomputes `minus_one` on every call (`divisor.rs:164`). Only the signed `PowerOfTwo` variant checks for -1 now. It compares `n` with `MIN` and two of its fields, and the kernel can skip it for any divisor other than -1. > The benchmark groups are named just `u32`, `i32` and so on. They're `divisor_u32`, `divisor_i32`, `divisor_u64` and `divisor_i64` now. > concatenates a single literal, so it could be a plain `///` line. That line went away when I rewrote the signed docs. -- 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]
