mbutrovich commented on code in PR #12232:
URL: https://github.com/apache/arrow-rs/pull/12232#discussion_r4564710973
##########
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`
+ // in. Section 3 of the paper gives `MULSH(x, y) = MULUH(x, y) - AND(x,
XSIGN(y))
+ // - AND(y, XSIGN(x))`, which is program (1) in section 8-3 of Warren,
"Hacker's Delight", 2nd
+ // edition. `m'` is negative for every divisor but 1 and -1, which are
powers of two, so
+ // `AND(n, XSIGN(m'))` is `n` and cancels the add, leaving `MULUH(m', n) -
AND(m', XSIGN(n))`
+ |m, n| (mulx(m as u128, n as u128).1 as i128).wrapping_sub((n >> 127) & m),
+ [
+ ///
+ /// When every value of a batch fits in `i64`, dividing in `i64` with
[`DivisorI64`] gives
+ /// the same results, except for a divisor of -1, because `i64::MIN /
-1` overflows in
+ /// `i64` but not in `i128`. A divisor that doesn't fit in `i64`
exceeds every such value,
+ /// so the quotient is 0 and the remainder is the value.
+ ///
+ /// ```
+ /// # use arrow_buffer::{DivisorI128, DivisorI64};
+ /// let values: Vec<i128> = vec![-12_345, 678, i64::MIN as i128];
+ /// let divisor: i128 = 100;
+ /// let narrow = values.iter().all(|n| i64::try_from(*n).is_ok());
+ /// let quotients: Vec<i128> = match i64::try_from(divisor) {
+ /// Ok(d) if narrow && d != -1 => {
+ /// let d = DivisorI64::new(d).unwrap();
+ /// values.iter().map(|n| d.wrapping_div_rem(*n as i64).0 as
i128).collect()
+ /// }
+ /// _ => {
+ /// let d = DivisorI128::new(divisor).unwrap();
+ /// values.iter().map(|n| d.wrapping_div_rem(*n).0).collect()
+ /// }
+ /// };
+ /// assert_eq!(quotients, [-123, 6, -92233720368547758]);
+ /// ```
+ ]
+);
+
+// `signed_divisor!` can't build `DivisorI256`, because `i256` has no `BITS`
or `unsigned_abs` and
+// its operators can't be called in a `const fn`. Its variants compute on the
parts of the values
+// with the helpers below `impl DivisorI256` instead
+divisor_enum!(
+ DivisorI256,
+ i256,
+ concat!(
+ "# use arrow_buffer::{i256, DivisorI256};\n",
+ "let values: Vec<i256> = [100, 7,
64].map(i256::from_i128).to_vec();\n",
+ "let quotients: Vec<_> = match
DivisorI256::new(i256::from_i128(7)).unwrap() {\n",
+ " DivisorI256::PowerOfTwo(d) => values.iter().map(move |n|
d.wrapping_div_rem(*n).0).collect(),\n",
+ " DivisorI256::AddIndicator(d) => values.iter().map(move |n|
d.wrapping_div_rem(*n).0).collect(),\n",
+ " d => values.iter().map(move |n|
d.wrapping_div_rem(*n).0).collect(),\n",
+ "};\n",
+ "assert_eq!(quotients, [14, 1, 9].map(i256::from_i128));",
+ ),
+ concat!(
+ "# use arrow_buffer::{i256, DivisorI256};\n",
+ "let divisor = DivisorI256::new(i256::from_i128(7)).unwrap();\n",
+ "let (q, r) = divisor.wrapping_div_rem(i256::from_i128(100));\n",
+ "assert_eq!((q, r), (i256::from_i128(14), i256::from_i128(2)));",
+ ),
+ [
+ ///
+ /// Unlike the other divisor types, the variants' methods branch on
the divisor's shift. The
+ /// shift is the same for every value, so the branch is predicted, and
a form without it
+ /// was slower.
+ ///
+ /// When every value of a batch fits in `i128`, dividing in `i128`
with [`DivisorI128`]
+ /// gives the same results, except for a divisor of -1, because
`i128::MIN / -1` overflows
+ /// in `i128` but not in `i256`. A divisor that doesn't fit in `i128`
exceeds every such
+ /// value, so the quotient is 0 and the remainder is the value.
+ ],
+ /// A divisor whose magnitude is a power of two
+ PowerOfTwo(PowerOfTwoDivisorI256),
+ /// Any other divisor
+ AddIndicator(AddIndicatorDivisorI256),
+);
+
+impl DivisorI256 {
+ /// Returns a divisor for `divisor`, or `None` if `divisor` is zero
+ ///
+ /// # Example
+ /// ```
+ /// # use arrow_buffer::{i256, DivisorI256};
+ /// assert!(DivisorI256::new(i256::ZERO).is_none());
+ /// ```
+ pub fn new(divisor: i256) -> Option<Self> {
+ if divisor == i256::ZERO {
+ return None;
+ }
+ Some(match PowerOfTwoDivisorI256::new(divisor) {
+ Some(d) => Self::PowerOfTwo(d),
+ None => Self::AddIndicator(AddIndicatorDivisorI256::new(divisor)),
+ })
+ }
+
+ /// Returns `(n / divisor, n % divisor)`, or `None` for `i256::MIN / -1`
+ ///
+ /// It matches on the variant on each call. Only [`Self::PowerOfTwo`] can
return `None`.
+ ///
+ /// # Example
+ /// ```
+ /// # use arrow_buffer::{i256, DivisorI256};
+ /// let divisor = DivisorI256::new(i256::from_i128(-7)).unwrap();
+ /// let qr = divisor.checked_div_rem(i256::from_i128(-100));
+ /// assert_eq!(qr, Some((i256::from_i128(14), i256::from_i128(-2))));
+ ///
+ /// let minus_one = DivisorI256::new(i256::MINUS_ONE).unwrap();
+ /// assert_eq!(minus_one.checked_div_rem(i256::MIN), None);
+ /// ```
+ #[inline]
+ pub const fn checked_div_rem(self, n: i256) -> Option<(i256, i256)> {
+ match self {
+ Self::PowerOfTwo(d) => d.checked_div_rem(n),
+ Self::AddIndicator(d) => Some(d.wrapping_div_rem(n)),
+ }
+ }
+}
+
+/// `i256` operations that a `const fn` can call, on the parts of the values.
`shr` is `SRA` from
+/// table 3.1 of Granlund and Montgomery for `0..=255` bits
+///
+/// It branches on the shift, so the `i256` variants branch on the divisor,
unlike the other
Review Comment:
The other divisor types don't branch on the divisor, so their loops don't
rely on LLVM moving a branch out of them, as #11467 settled. `shr` branches on
the shift because a branch-free form was slower. In the bot's thin-LTO build no
target moves the branch out of the loop: each `i256` loop dispatches on the
shift for every value, and the shift stays in a register. The shift is the same
for every value, so the branch is predicted.
The branch-free form shifts both halves and selects with a mask. The bot
compared 2bdc7f3b5e (branch) with abc1056086 (branch-free) in the same run, on
[Neoverse-V2](https://github.com/apache/arrow-rs/pull/12232#issuecomment-6854415649),
the [Xeon
8581C](https://github.com/apache/arrow-rs/pull/12232#issuecomment-6854417983)
and the [Xeon at
`x86-64-v3`](https://github.com/apache/arrow-rs/pull/12232#issuecomment-6854667349).
Ratios are time with the branch over time without, so below 1.00x means the
branch-free form is slower:
| Case | Neoverse-V2 | Xeon 8581C | `x86-64-v3` |
|---|---|---|---|
| `/` 16 (`PowerOfTwo`) | 0.77x | 0.81x to 0.82x | 0.78x to 0.80x |
| `/` 7 and 10^38 (`AddIndicator`) | 0.90x | 0.87x to 0.93x | 0.84x to 0.86x
|
| `%` 7 and 10^38 (`AddIndicator`) | 0.95x to 0.96x | 0.90x to 0.92x | 0.91x
to 0.93x |
| `/` and `%` with the operators, which don't call `shr` | 1.00x to 1.01x |
0.99x to 1.02x | 0.99x to 1.02x |
`%` by 16 doesn't call `shr`, and it measured 0.99x to 1.02x except at
`x86-64-v3`, where it measured 1.04x and 1.15x and the operator cases didn't
move. I read that as code layout. On an Apple M5 Max, the branch-free form was
also slower for `PowerOfTwo`, by 1.30x to 1.35x at `opt-level=2` and with thin
LTO.
--
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]
