mbutrovich commented on code in PR #12232:
URL: https://github.com/apache/arrow-rs/pull/12232#discussion_r4588441849


##########
arrow-buffer/src/divisor.rs:
##########
@@ -470,20 +513,389 @@ 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;

Review Comment:
   > A const 256-by-128 shift-subtract loop in `u128` (or a const `div_rem`) 
would keep `[const]` for `i128` and remove the special case.
   
   I covered this in 
https://github.com/apache/arrow-rs/pull/12232#discussion_r4564693444. A `const` 
division of two 128-bit words by one is about 30 lines. The constant divisor in 
#11421 that would gain most from `const` is 10^38 for `Display for i256` 
(#12174), and that needs a `const` Algorithm D for `i256`. Making `new` a 
`const fn` later doesn't break callers, so I'd add it when a caller needs a 
`const` divisor.
   
   It also wouldn't remove the special case from `signed_divisor!`. `i128` has 
no wider type to compute the multiplier or `MULSH` in, so the macro would still 
take both as expressions. Only the `[const]` token would go.
   
   > construction costs up to ~23 ns
   
   `const` removes that cost only for a divisor built in a `const` context. A 
kernel builds its divisor from a runtime scalar once per batch, where `new` 
costs the same either way.



-- 
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]

Reply via email to