mbutrovich commented on code in PR #12232:
URL: https://github.com/apache/arrow-rs/pull/12232#discussion_r4564695929
##########
arrow-buffer/src/divisor.rs:
##########
@@ -470,20 +510,390 @@ unsigned_divisor!(
u64,
u128
);
-signed_divisor!(
+/// Expands to the arguments of `signed_divisor!` that compute with `$wide`, a
type twice as wide
+/// as `$t`
+macro_rules! signed_divisor_wide {
+ ($name:ident, $power_of_two:ident, $add:ident, $t:ty, $wide:ty) => {
+ signed_divisor!(
+ $name,
+ $power_of_two,
+ $add,
+ $t,
+ [const],
+ // m = 1 + floor(2^(N + l - 1) / |divisor|) is between 2^(N - 1)
and 2^N, so m - 2^N
+ // fits in the narrow type
+ |magnitude, l| {
+ let m = 1 + (1 << (<$t>::BITS + l - 1)) / magnitude as $wide;
+ (m - (1 << <$t>::BITS)) as $t
+ },
+ // `n + MULSH(m', n)` in figure 5.1
+ |m, n| n + ((m as $wide * n as $wide) >> <$t>::BITS) as $t,
+ []
+ );
+ };
+}
+
+signed_divisor_wide!(
DivisorI32,
PowerOfTwoDivisorI32,
AddIndicatorDivisorI32,
i32,
i64
);
-signed_divisor!(
+signed_divisor_wide!(
DivisorI64,
PowerOfTwoDivisorI64,
AddIndicatorDivisorI64,
i64,
i128
);
+signed_divisor!(
+ DivisorI128,
+ PowerOfTwoDivisorI128,
+ AddIndicatorDivisorI128,
+ i128,
+ [],
+ // m = 1 + floor(2^(127 + l) / |divisor|), as for the narrower types.
2^(127 + l) is at most
+ // 2^254, so `i256` holds it, and the quotient is below 2^128
+ |magnitude, l| {
+ let pow = i256::ONE << (127 + l) as u8;
+ let (q, _) = pow.wrapping_div(i256::from_parts(magnitude,
0)).to_parts();
+ q.wrapping_add(1) as i128
+ },
+ // Figure 5.1 computes `n + MULSH(m', n)`, and `i128` has no wider type to
compute `MULSH`
Review Comment:
`AddIndicator` uses figure 5.1 of [Granlund and Montgomery
(1994)](https://gmplib.org/~tege/divcnst-pldi94.pdf), as `DivisorI64` does. The
prototype in #11421 used figure 4.1 on `|n|` with a sign fix, and #11979 tried
an unsigned high multiply on `|n|` for 32 and 64 bits. I compared three forms
at 128 bits, all with the same high multiply: figure 5.1, the prototype's form,
and an exact multiplier on `|n|` with no add, which is the form in #11979.
Figure 5.1 had the fewest instructions per value, or tied, on aarch64,
x86_64 and `x86-64-v3`. The form in #11979 skips the add but spends as much on
the absolute value of `n` and the sign fix of the quotient. Instructions per
value in the `i128` loop, for `/` and `%`:
| Form | aarch64 | x86_64 | `x86-64-v3` |
|---|---|---|---|
| Figure 5.1 | 40 / 42 | 47 / 53 | 41.5 / 51 |
| Figure 4.1 on `\|n\|` | 45 / 49 | 52 / 59 | 47 / 54 |
| No add on `\|n\|` | 39 / 43 | 46 / 51 | 43 / 49 |
On an Apple M5 Max, in us per 8192 full-width random values:
| Case | Operator | Figure 5.1 | Figure 4.1 on `\|n\|` | No add on `\|n\|` |
|---|---|---|---|---|
| `i128` `/` 7 | 18.44 | 11.08 | 14.53 | 11.79 |
| `i128` `/` 10^18 | 65.12 | 11.04 | 14.52 | 11.77 |
| `i128` `%` 7 | 18.43 | 12.22 | 17.70 | 14.64 |
| `i128` `%` 10^18 | 65.41 | 12.22 | 17.77 | 14.64 |
The other forms aren't in this PR, so the benchmark bot can't compare them.
--
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]
