You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "mbutrovich (via GitHub)" <gi...@apache.org> on 2026/10/15 14:13:58 UTC
[PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
mbutrovich opened a new pull request, #11580:
URL: https://github.com/apache/arrow-rs/pull/11580
# Which issue does this PR close?
- Part of #11451.
- Part of #11421.
# Rationale for this change
Outside x86_64, [`div_rem_word`](https://github.com/apache/arrow-rs/blob/418340d5188f6e2949c4a0545b3e437dfdc848f8/arrow-buffer/src/bigint/div.rs#L186-L211) divides a two-word number by one word with a `u128` division, which is a call to `__udivti3`. [`div_rem_small`](https://github.com/apache/arrow-rs/blob/418340d5188f6e2949c4a0545b3e437dfdc848f8/arrow-buffer/src/bigint/div.rs#L61-L73) calls it once per word, so dividing an `i256` by a divisor below 2^64 makes four calls ([comment](https://github.com/apache/arrow-rs/issues/11451#issuecomment-6064895595)).
# What changes are included in this PR?
Outside x86_64 and under Miri, `div_rem_small` shifts both operands so that the divisor's top bit is set. It computes a reciprocal of the divisor once with algorithm 2 of [Moller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf), which uses a 256-entry table and multiplies. It then divides each word with their algorithm 4, which uses one full multiply, one low multiply and two corrections, and no divide. x86_64 keeps the `div` instruction.
Computing the reciprocal with a `u128` division instead made the `i256` bench slower than `main`, because that one `__udivti3` call cost more than the four it replaced.
Dividends and divisors whose magnitudes are both below 2^128 still take the `u128` division from #11530. This change applies to wider dividends with a divisor below 2^64, such as `Decimal256` division of two arrays with more than 38 digits in the scaled dividend.
# Are these changes tested?
The new tests in `arrow-buffer/src/bigint/div.rs` compile on every target:
- `test_reciprocal_word` checks the reciprocal against a `u128` division for the divisors 2^63 and `u64::MAX` and their neighbors, the divisors at and next to each boundary between table entries, and random divisors.
- `test_div_rem_word_reciprocal` checks each word's division against `u128` division, including an input that reaches the second correction.
- `test_div_rem_small_reciprocal` compares the new path with the per-word `div_rem_word` path for every normalization shift, powers of ten up to 10^19 and their neighbors, one, two and four words, and random inputs.
The existing `test_i256_fuzz` and `test_div_rem_powers_of_ten` reach the new path on targets other than x86_64 and under Miri.
The benchmark bot ran `i256_div_rem` in the `i256` benchmark, whose rows each have their own divisor, on [x86_64](TODO) and [arm64](TODO). The runners are a Xeon Platinum 8581C and a Neoverse-V2.
TODO: chart
<details><summary>Numbers behind the chart</summary>
In us per 1024 divisions:
| Case | x86_64: `main` | This PR | arm64: `main` | This PR |
|---|---|---|---|---|
| `small divisor` | TODO | TODO | TODO | TODO |
| `small quotient` | TODO | TODO | TODO | TODO |
</details>
`small quotient` divides by divisors wider than 64 bits, which this change doesn't reach.
<details><summary>Apple M5 Max</summary>
With rustc 1.99.0, in us per 1024 divisions:
| Case | `main` | This PR |
|---|---|---|
| `small divisor` | 17.5 | 13.5 |
| `small quotient` | 16.9 | 16.6 |
</details>
# Are there any significant user-facing changes?
No.
## AI Disclosure
I wrote this PR with help from Claude but understand and support the core approach, implementation, and test coverage.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6249560211
@Rich-T-kid @neilconway @rluvaton I’m struggling to find reviewers on low-level performance PRs. Do you mind taking a look if you have time and interest, please?
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4314717593
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +95,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf),
Review Comment:
> Maybe add the paper name in the comment in case the link ever die
Added "Improved division by invariant integers" to both links.
https://github.com/apache/arrow-rs/pull/11580#discussion_r4306946278
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4328291502
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +93,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund, "Improved division by invariant integers" (2011)](https://gmplib.org/~tege/division-paper.pdf),
+/// which avoids a `u128` division
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn reciprocal_word(divisor: u64) -> u64 {
+ debug_assert_eq!(divisor >> 63, 1);
+
+ // `floor((2^19 - 3 * 2^8) / d9)` for each value of the top 9 bits `d9`
+ const TABLE: [u16; 256] = {
+ let mut table = [0; 256];
+ let mut i = 0;
+ while i < 256 {
+ table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
+ i += 1;
+ }
+ table
+ };
+
+ let d0 = divisor & 1;
+ let d9 = divisor >> 55;
+ let d40 = (divisor >> 24) + 1;
+ let d63 = (divisor >> 1) + d0;
+
+ // `d9` is in 256..512, so masking gives `d9 - 256` without a bounds check
+ let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
+ // Two Newton iterations, each about doubling the bits of precision
+ let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
+ let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
+ // `2^96 - v2 * d63 + floor(v2 / 2) * d0`, which the paper shows fits in 64 bits
+ let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
+ let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
+ // `floor((v3 + 2^64 + 1) * divisor / 2^64)`, without overflowing a `u128`
+ let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
+ v3.wrapping_sub(p.wrapping_add(divisor))
+}
Review Comment:
I added a bit more documentation.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "Rich-T-kid (via GitHub)" <gi...@apache.org>.
Rich-T-kid commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296822196
run benchmark decimal_division
env:
BENCH_FILTER: decimal256_scalar
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4314728091
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
+ divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
+ let expected = (n / u128::from(divisor)) as u64;
+ assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
+ }
+ }
+
+ #[test]
+ fn test_div_rem_word_reciprocal() {
+ // The second correction, which random inputs rarely reach, runs for this input
+ let (hi, lo, divisor) = (
+ 3787258589690185862,
+ 17800796494353475223,
+ 9357586864501027680,
Review Comment:
> What is special for those numbers?
Nothing, beyond the fact that they reach the second correction. I found them by searching random inputs, and the comment didn't say so. I replaced them with an input whose arithmetic can be checked by hand. The reciprocal of `2^63 + 2` is `2^64 - 8`, so the estimate for `(2^127 + 2^64 - 1) / (2^63 + 2)` is `2^64 - 3`. The quotient is `2^64 - 2`, so the estimate is one too small and the second correction adds it back. The test also asserts the reciprocal value.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6269072215
Thanks for the feedback @rluvaton! I think I addressed all of it.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296968132
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296822196)
**Target:** decimal_division
Comparing i256-div-rem-small-reciprocal (0a6a25caf23cb1ee5cbd419ef4a7c3dcef01e311) to d58a0fc (merge-base) [diff](https://github.com/apache/arrow-rs/compare/d58a0fce35b67836ac9b2e20a7efe47a584e0a86..0a6a25caf23cb1ee5cbd419ef4a7c3dcef01e311)
<details><summary>Run configuration</summary>
```yaml
run benchmark decimal_division
env:
BENCH_FILTER: decimal256_scalar
shards: 1
```
</details>
<details><summary>Details</summary>
```
group base changed
----- ---- -------
decimal256_scalar/div_30_digits_by_4_digits/128_values 1.00 5.2±0.01µs 23.7 MElem/sec 1.00 5.2±0.01µs 23.7 MElem/sec
decimal256_scalar/div_30_digits_by_4_digits/16_values 1.00 802.1±4.36ns 19.0 MElem/sec 1.00 800.3±2.47ns 19.1 MElem/sec
decimal256_scalar/div_30_digits_by_4_digits/1_values 1.00 206.5±1.30ns 4.6 MElem/sec 1.00 206.5±1.73ns 4.6 MElem/sec
decimal256_scalar/div_30_digits_by_4_digits/mixed_nulls 1.00 32.5±0.04µs 30.1 MElem/sec 1.00 32.4±0.03µs 30.1 MElem/sec
decimal256_scalar/div_30_digits_by_4_digits/no_nulls 1.00 40.5±0.10µs 24.1 MElem/sec 1.00 40.4±0.14µs 24.2 MElem/sec
decimal256_scalar/div_60_digits_by_40_digits/no_nulls 1.00 86.9±0.45µs 11.2 MElem/sec 1.00 87.1±0.45µs 11.2 MElem/sec
decimal256_scalar/div_60_digits_by_4_digits/no_nulls 1.36 75.1±0.03µs 13.0 MElem/sec 1.00 55.2±0.04µs 17.7 MElem/sec
decimal256_scalar/div_72_digits_by_4_digits/no_nulls 1.12 228.0±0.41µs 4.3 MElem/sec 1.00 204.4±0.37µs 4.8 MElem/sec
decimal256_scalar/rem_30_digits_by_4_digits/mixed_nulls 1.00 32.3±0.04µs 30.2 MElem/sec 1.00 32.4±0.04µs 30.2 MElem/sec
decimal256_scalar/rem_30_digits_by_4_digits/no_nulls 1.00 40.3±0.06µs 24.2 MElem/sec 1.00 40.4±0.07µs 24.2 MElem/sec
decimal256_scalar/rem_60_digits_by_40_digits/no_nulls 1.00 85.8±0.29µs 11.4 MElem/sec 1.00 85.7±0.30µs 11.4 MElem/sec
decimal256_scalar/rem_60_digits_by_4_digits/no_nulls 1.33 76.1±0.29µs 12.8 MElem/sec 1.00 57.1±0.16µs 17.1 MElem/sec
```
</details>
<details><summary>Per-runner information</summary>
<details><summary>decimal_division — shard 1/1</summary>
**Node:** gk3-benchmark-cluster-nap-15ehpxtl-07f2d97c-4ccj
**Instance:** c4a-highmem-16 (12 vCPU / 65 GiB)
**uname:**
```text
Linux bench-c6296822196-3664-jxgdr 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux
```
**BENCH_COMMAND:**
```sh
cargo bench --features=arrow,async,test_common,experimental,object_store --bench decimal_division
```
<details><summary>CPU Details (lscpu)</summary>
```text
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 125.0s |
| Peak memory | 12.4 MiB |
| Avg memory | 11.2 MiB |
| CPU user | 120.5s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 120.0s |
| Peak memory | 12.8 MiB |
| Avg memory | 11.6 MiB |
| CPU user | 116.1s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
</details>
</details>
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6296822196:finish:c67aababa0078de559f596fdbe5eb58f -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "Rich-T-kid (via GitHub)" <gi...@apache.org>.
Rich-T-kid commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4328101185
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +93,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund, "Improved division by invariant integers" (2011)](https://gmplib.org/~tege/division-paper.pdf),
+/// which avoids a `u128` division
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn reciprocal_word(divisor: u64) -> u64 {
+ debug_assert_eq!(divisor >> 63, 1);
+
+ // `floor((2^19 - 3 * 2^8) / d9)` for each value of the top 9 bits `d9`
+ const TABLE: [u16; 256] = {
+ let mut table = [0; 256];
+ let mut i = 0;
+ while i < 256 {
+ table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
+ i += 1;
+ }
+ table
+ };
+
+ let d0 = divisor & 1;
+ let d9 = divisor >> 55;
+ let d40 = (divisor >> 24) + 1;
+ let d63 = (divisor >> 1) + d0;
+
+ // `d9` is in 256..512, so masking gives `d9 - 256` without a bounds check
+ let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
+ // Two Newton iterations, each about doubling the bits of precision
+ let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
+ let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
+ // `2^96 - v2 * d63 + floor(v2 / 2) * d0`, which the paper shows fits in 64 bits
+ let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
+ let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
+ // `floor((v3 + 2^64 + 1) * divisor / 2^64)`, without overflowing a `u128`
+ let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
+ v3.wrapping_sub(p.wrapping_add(divisor))
+}
Review Comment:
@mbutrovich, this is a lot to take in. Could you add some explanation, particularly for the magic numbers? Apart from the factors of 8, I’m not sure what some of the bit shifts are doing. Clearer variable names would help too.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4306960527
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
+ divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
+ let expected = (n / u128::from(divisor)) as u64;
+ assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
+ }
+ }
+
+ #[test]
+ fn test_div_rem_word_reciprocal() {
+ // The second correction, which random inputs rarely reach, runs for this input
+ let (hi, lo, divisor) = (
+ 3787258589690185862,
+ 17800796494353475223,
+ 9357586864501027680,
+ );
+ let n = (u128::from(hi) << 64) | u128::from(lo);
+ let d = u128::from(divisor);
+ assert_eq!(
+ div_rem_word_reciprocal(hi, lo, divisor, reciprocal_word(divisor)),
+ ((n / d) as u64, (n % d) as u64)
+ );
+
+ let mut rng = rng();
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ divisors.extend((0..100).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let reciprocal = reciprocal_word(divisor);
+ let mut his = vec![0, 1, divisor / 2, divisor - 1];
+ his.extend((0..20).map(|_| rng.random_range(0..divisor)));
+ for hi in his {
+ let mut los = vec![0, 1, divisor - 1, divisor, u64::MAX];
+ los.extend((0..20).map(|_| rng.random::<u64>()));
+ for lo in los {
+ let n = (u128::from(hi) << 64) | u128::from(lo);
+ let d = u128::from(divisor);
+ let expected = ((n / d) as u64, (n % d) as u64);
+ assert_eq!(
+ div_rem_word_reciprocal(hi, lo, divisor, reciprocal),
+ expected,
+ "{n} / {divisor}"
+ );
+ }
+ }
+ }
+ }
+
+ #[test]
+ fn test_div_rem_small_reciprocal() {
+ let mut rng = rng();
+ let numerators = [
+ [0; 4],
+ [1, 0, 0, 0],
+ [0, 0, 0, 1],
+ [u64::MAX; 4],
+ [0, 0, 0, u64::MAX],
+ [u64::MAX, 0, 0, 0],
+ rng.random(),
+ ];
+ // Every normalization shift, with divisors at and next to each power of two
+ for shift in 0..64 {
+ let p = 1u64 << shift;
+ let mut divisors = vec![p, p.wrapping_mul(2).wrapping_sub(1)];
+ divisors.extend(p.checked_add(1));
+ divisors.extend(p.checked_sub(1).filter(|d| *d != 0));
+ for divisor in divisors {
+ for numerator in numerators {
+ check_div_rem_small(numerator, divisor);
+ check_div_rem_small([numerator[0], numerator[1]], divisor);
+ check_div_rem_small([numerator[0]], divisor);
+ }
+ }
+ }
+ // Powers of ten, as used when rescaling decimals
+ for k in 0..=19 {
+ let p = 10u64.pow(k);
+ for divisor in [p - 1, p, p + 1].into_iter().filter(|d| *d != 0) {
+ for numerator in numerators {
+ check_div_rem_small(numerator, divisor);
+ }
+ }
+ }
+ for _ in 0..1000 {
+ let divisor = rng.random::<u64>() >> rng.random_range(0..64);
Review Comment:
can you make it seeded rng to be deterministic
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6195149265
🤖 Benchmark starting (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6195147060)
**Target:** cast_decimal
**Sharding factor: 1** (1 workers).
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark cast_decimal
env:
BENCH_FILTER: decimal_downscale/decimal256
RUSTFLAGS: -C llvm-args=-align-all-functions=6 -C llvm-args=-align-all-nofallthru-blocks=6
shards: 1
```
</details>
Results will be posted when all workers finish.
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6195147060:start:96bcb6c90d6ab3fca2bbf8191913f67b -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194210246
run benchmark i256
```
env:
BENCH_FILTER: i256_div_rem
resources:
arch: amd64
```
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194334512
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194210246)
**Target:** i256
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark i256
env:
BENCH_FILTER: i256_div_rem
resources:
arch: amd64
shards: 1
```
</details>
<details><summary>Details</summary>
```
group base changed
----- ---- -------
i256_div_rem small divisor 1.00 14.5±0.27µs ? ?/sec 1.00 14.5±0.49µs ? ?/sec
i256_div_rem small quotient 1.00 30.8±0.77µs ? ?/sec 1.00 30.7±0.57µs ? ?/sec
```
</details>
<details><summary>Per-runner information</summary>
<details><summary>i256 — shard 1/1</summary>
**Node:** gk3-benchmark-cluster-nap-ndbz1fge-ea6947bc-fkpq
**Instance:** c4-highmem-16 (12 vCPU / 65 GiB)
**uname:**
```text
Linux bench-c6194210246-3454-r2gs4 6.12.94+ #1 SMP Fri Aug 21 07:56:42 UTC 2026 x86_64 GNU/Linux
```
**BENCH_COMMAND:**
```sh
cargo bench --features=arrow,async,test_common,experimental,object_store --bench i256
```
<details><summary>CPU Details (lscpu)</summary>
```text
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 52 bits physical, 57 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: INTEL(R) XEON(R) PLATINUM 8581C CPU @ 2.30GHz
CPU family: 6
Model: 207
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 2
BogoMIPS: 4600.00
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc cpuid tsc_known_freq pni pclmulqdq monitor ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm 3dnowprefetch ssbd ibrs ibpb stibp ibrs_enhanced fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm avx512f avx512dq rdseed adx smap avx512ifma clflushopt clwb avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves avx_vnni avx512_bf16 wbnoinvd arat avx512vbmi umip avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq rdpid cldemote movdiri movdir64b fsrm md_clear serialize tsxldtrk amx_bf16 avx512_fp16 amx_tile amx_int8 arch_capabilities
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 384 KiB (8 instances)
L1i cache: 256 KiB (8 instances)
L2 cache: 16 MiB (8 instances)
L3 cache: 260 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2: Mitigation; Enhanced / Automatic IBRS; IBPB conditional; PBRSB-eIBRS SW sequence; BHI BHI_DIS_S
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 20.0s |
| Peak memory | 11.1 MiB |
| Avg memory | 7.0 MiB |
| CPU user | 17.7s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 20.0s |
| Peak memory | 11.1 MiB |
| Avg memory | 6.9 MiB |
| CPU user | 17.0s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
</details>
</details>
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6194210246:finish:f249211272f5f4094c5027be8b450a42 -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4314721331
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +95,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf),
+/// which avoids a `u128` division
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn reciprocal_word(divisor: u64) -> u64 {
+ debug_assert_eq!(divisor >> 63, 1);
+
+ // `floor((2^19 - 3 * 2^8) / d9)` for each value of the top 9 bits `d9`
+ const TABLE: [u16; 256] = {
+ let mut table = [0; 256];
+ let mut i = 0;
+ while i < 256 {
+ table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
+ i += 1;
+ }
+ table
+ };
+
+ let d0 = divisor & 1;
+ let d9 = divisor >> 55;
+ let d40 = (divisor >> 24) + 1;
+ let d63 = (divisor >> 1) + d0;
+
+ // `d9` is in 256..512, so masking gives `d9 - 256` without a bounds check
+ let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
+ // Two Newton iterations, each about doubling the bits of precision
+ let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
+ let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
+ // `2^96 - v2 * d63 + floor(v2 / 2) * d0`, which the paper shows fits in 64 bits
+ let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
+ let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
+ // `floor((v3 + 2^64 + 1) * divisor / 2^64)`, without overflowing a `u128`
+ let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
+ v3.wrapping_sub(p.wrapping_add(divisor))
+}
+
+/// Divides `hi:lo` by a divisor with its top bit set, given its [`reciprocal_word`]
+///
+/// This is algorithm 4 of [Möller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf)
Review Comment:
> Maybe add the paper name in the comment in case the link ever die
Done here too.
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
+ divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
+ let expected = (n / u128::from(divisor)) as u64;
+ assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
+ }
+ }
+
+ #[test]
+ fn test_div_rem_word_reciprocal() {
+ // The second correction, which random inputs rarely reach, runs for this input
+ let (hi, lo, divisor) = (
+ 3787258589690185862,
+ 17800796494353475223,
+ 9357586864501027680,
+ );
+ let n = (u128::from(hi) << 64) | u128::from(lo);
+ let d = u128::from(divisor);
+ assert_eq!(
+ div_rem_word_reciprocal(hi, lo, divisor, reciprocal_word(divisor)),
+ ((n / d) as u64, (n % d) as u64)
+ );
+
+ let mut rng = rng();
Review Comment:
> can you make it seeded rng to be deterministic
All three tests now use `StdRng::seed_from_u64(42)`, like the other seeded tests in `arrow-buffer`.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4328191695
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +93,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund, "Improved division by invariant integers" (2011)](https://gmplib.org/~tege/division-paper.pdf),
+/// which avoids a `u128` division
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn reciprocal_word(divisor: u64) -> u64 {
+ debug_assert_eq!(divisor >> 63, 1);
+
+ // `floor((2^19 - 3 * 2^8) / d9)` for each value of the top 9 bits `d9`
+ const TABLE: [u16; 256] = {
+ let mut table = [0; 256];
+ let mut i = 0;
+ while i < 256 {
+ table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
+ i += 1;
+ }
+ table
+ };
+
+ let d0 = divisor & 1;
+ let d9 = divisor >> 55;
+ let d40 = (divisor >> 24) + 1;
+ let d63 = (divisor >> 1) + d0;
+
+ // `d9` is in 256..512, so masking gives `d9 - 256` without a bounds check
+ let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
+ // Two Newton iterations, each about doubling the bits of precision
+ let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
+ let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
+ // `2^96 - v2 * d63 + floor(v2 / 2) * d0`, which the paper shows fits in 64 bits
+ let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
+ let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
+ // `floor((v3 + 2^64 + 1) * divisor / 2^64)`, without overflowing a `u128`
+ let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
+ v3.wrapping_sub(p.wrapping_add(divisor))
+}
Review Comment:
> @mbutrovich, this is a lot to take in. Could you add some explanation, particularly for the magic numbers? Apart from the factors of 8, I’m not sure what some of the bit shifts are doing. Clearer variable names would help too.
I think changing the variable names would hurt readability. `reciprocal_word` exactly matches Algorithm 2 from the paper, and I think trying to ascribe our own meaning here would make it more difficult to map to the source. I can try to bring some of the comments from the Algorithm 2 listing, but at some point we have to rely on the reference and not reproduce the paper in comment form.
<img width="405" height="313" alt="Screenshot 2026-10-20 at 1 37 55 PM" src="https://github.com/user-attachments/assets/3e0bc6ac-0033-439c-9230-65e6422efd25" />
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4306917208
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -59,6 +59,29 @@ fn bits(arr: &[u64]) -> usize {
/// Division of numerator by a u64 divisor
fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N], [u64; N]) {
+ // x86_64 divides by one word with `div`. On 32-bit targets, including wasm32, each
+ // 64x64-to-128-bit product in the reciprocal path would call `__multi3`
+ #[cfg(any(
+ all(target_arch = "x86_64", not(miri)),
+ not(target_pointer_width = "64")
+ ))]
+ {
+ div_rem_small_word(numerator, divisor)
+ }
+
+ // Here `div_rem_word` would call `__udivti3` for every digit
Review Comment:
```suggestion
// Fallback implementation
// Here `div_rem_word` would call `__udivti3` for every digit
```
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4306941582
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -59,6 +59,29 @@ fn bits(arr: &[u64]) -> usize {
/// Division of numerator by a u64 divisor
fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N], [u64; N]) {
+ // x86_64 divides by one word with `div`. On 32-bit targets, including wasm32, each
+ // 64x64-to-128-bit product in the reciprocal path would call `__multi3`
+ #[cfg(any(
+ all(target_arch = "x86_64", not(miri)),
+ not(target_pointer_width = "64")
+ ))]
+ {
+ div_rem_small_word(numerator, divisor)
+ }
+
+ // Here `div_rem_word` would call `__udivti3` for every digit
+ #[cfg(all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri)))]
+ {
+ div_rem_small_reciprocal(numerator, divisor)
+ }
Review Comment:
The cfg attributes makes it harder to understand the fallback here, maybe add a a comment which is the fallback and move it to be the last like most people assume
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194268453
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194207134)
**Target:** i256
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark i256
env:
BENCH_FILTER: i256_div_rem
shards: 1
```
</details>
<details><summary>Details</summary>
```
group base changed
----- ---- -------
i256_div_rem small divisor 1.78 43.1±0.02µs ? ?/sec 1.00 24.2±0.02µs ? ?/sec
i256_div_rem small quotient 1.02 25.8±0.04µs ? ?/sec 1.00 25.4±0.06µs ? ?/sec
```
</details>
<details><summary>Per-runner information</summary>
<details><summary>i256 — shard 1/1</summary>
**Node:** gk3-benchmark-cluster-nap-wkl49k2l-484c2473-4pfv
**Instance:** c4a-highmem-16 (12 vCPU / 65 GiB)
**uname:**
```text
Linux bench-c6194207134-3453-2vp85 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux
```
**BENCH_COMMAND:**
```sh
cargo bench --features=arrow,async,test_common,experimental,object_store --bench i256
```
<details><summary>CPU Details (lscpu)</summary>
```text
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 25.0s |
| Peak memory | 9.3 MiB |
| Avg memory | 5.4 MiB |
| CPU user | 19.2s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 20.0s |
| Peak memory | 9.3 MiB |
| Avg memory | 5.5 MiB |
| CPU user | 16.0s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
</details>
</details>
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6194207134:finish:74f8cae3feef87e9466fffca7752033d -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194207134
run benchmark i256
```
env:
BENCH_FILTER: i256_div_rem
```
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6195355966
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6195147060)
**Target:** cast_decimal
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark cast_decimal
env:
BENCH_FILTER: decimal_downscale/decimal256
RUSTFLAGS: -C llvm-args=-align-all-functions=6 -C llvm-args=-align-all-nofallthru-blocks=6
shards: 1
```
</details>
<details><summary>Details</summary>
```
group base changed
----- ---- -------
decimal_downscale/decimal256 (41, 20) -> decimal128(38, 6) 30 digits/mixed_nulls/safe 1.02 219.0±0.27µs 35.7 MElem/sec 1.00 214.7±0.53µs 36.4 MElem/sec
decimal_downscale/decimal256 (41, 20) -> decimal128(38, 6) 30 digits/no_nulls/safe 1.02 219.6±0.38µs 35.6 MElem/sec 1.00 214.6±0.31µs 36.4 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 38 digits/mixed_nulls/safe 1.08 173.7±0.38µs 45.0 MElem/sec 1.00 161.3±0.40µs 48.4 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 38 digits/no_nulls/safe 1.08 174.4±1.67µs 44.8 MElem/sec 1.00 161.3±0.33µs 48.4 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 60 digits/mixed_nulls/safe 1.47 431.1±0.93µs 18.1 MElem/sec 1.00 293.3±0.51µs 26.6 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 60 digits/no_nulls/safe 1.46 431.1±2.16µs 18.1 MElem/sec 1.00 294.8±2.74µs 26.5 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/mixed_nulls/safe 1.31 400.4±0.65µs 19.5 MElem/sec 1.00 304.9±1.18µs 25.6 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/mixed_nulls/strict 1.28 428.0±0.95µs 18.3 MElem/sec 1.00 334.2±1.03µs 23.4 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/no_nulls/safe 1.33 450.1±0.51µs 17.4 MElem/sec 1.00 338.2±0.42µs 23.1 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/no_nulls/strict 1.28 477.6±1.70µs 16.4 MElem/sec 1.00 372.8±1.12µs 21.0 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/mixed_nulls/safe 1.01 363.9±21.00µs 21.5 MElem/sec 1.00 359.0±0.72µs 21.8 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/mixed_nulls/strict 1.01 382.4±20.51µs 20.4 MElem/sec 1.00 377.8±2.33µs 20.7 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/no_nulls/safe 1.01 406.5±23.78µs 19.2 MElem/sec 1.00 400.6±0.75µs 19.5 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/no_nulls/strict 1.02 426.3±22.77µs 18.3 MElem/sec 1.00 417.9±2.20µs 18.7 MElem/sec
```
</details>
<details><summary>Per-runner information</summary>
<details><summary>cast_decimal — shard 1/1</summary>
**Node:** gk3-benchmark-cluster-nap-1ufwnz1d-9bc6d61c-sw22
**Instance:** c4a-highmem-16 (12 vCPU / 65 GiB)
**uname:**
```text
Linux bench-c6195147060-3458-xw8d9 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux
```
**BENCH_COMMAND:**
```sh
cargo bench --features=arrow,async,test_common,experimental,object_store --bench cast_decimal
```
<details><summary>CPU Details (lscpu)</summary>
```text
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 150.0s |
| Peak memory | 15.8 MiB |
| Avg memory | 14.3 MiB |
| CPU user | 143.9s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 150.0s |
| Peak memory | 16.6 MiB |
| Avg memory | 14.8 MiB |
| CPU user | 144.2s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
</details>
</details>
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6195147060:finish:a5efca94be4676614976cc14f02fa9cb -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194355455
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194213985)
**Target:** decimal_division
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark decimal_division
env:
BENCH_FILTER: decimal256_scalar
shards: 1
```
</details>
<details><summary>Details</summary>
```
group base changed
----- ---- -------
decimal256_scalar/div_30_digits_by_4_digits/128_values 1.00 5.2±0.01µs 23.7 MElem/sec 1.00 5.2±0.01µs 23.7 MElem/sec
decimal256_scalar/div_30_digits_by_4_digits/16_values 1.00 796.2±3.02ns 19.2 MElem/sec 1.00 793.4±2.86ns 19.2 MElem/sec
decimal256_scalar/div_30_digits_by_4_digits/1_values 1.01 206.9±1.39ns 4.6 MElem/sec 1.00 204.9±1.75ns 4.7 MElem/sec
decimal256_scalar/div_30_digits_by_4_digits/mixed_nulls 1.00 32.5±0.03µs 30.1 MElem/sec 1.00 32.5±0.03µs 30.1 MElem/sec
decimal256_scalar/div_30_digits_by_4_digits/no_nulls 1.00 40.4±0.11µs 24.1 MElem/sec 1.00 40.5±0.15µs 24.1 MElem/sec
decimal256_scalar/div_60_digits_by_40_digits/no_nulls 1.00 86.1±0.46µs 11.3 MElem/sec 1.01 86.9±0.47µs 11.2 MElem/sec
decimal256_scalar/div_60_digits_by_4_digits/no_nulls 1.35 75.0±0.06µs 13.0 MElem/sec 1.00 55.5±0.05µs 17.6 MElem/sec
decimal256_scalar/div_72_digits_by_4_digits/no_nulls 1.11 227.3±0.24µs 4.3 MElem/sec 1.00 204.3±0.31µs 4.8 MElem/sec
decimal256_scalar/rem_30_digits_by_4_digits/mixed_nulls 1.00 32.3±0.04µs 30.2 MElem/sec 1.00 32.3±0.04µs 30.2 MElem/sec
decimal256_scalar/rem_30_digits_by_4_digits/no_nulls 1.00 40.3±0.06µs 24.3 MElem/sec 1.00 40.4±0.07µs 24.2 MElem/sec
decimal256_scalar/rem_60_digits_by_40_digits/no_nulls 1.00 85.2±0.28µs 11.5 MElem/sec 1.00 85.4±0.31µs 11.4 MElem/sec
decimal256_scalar/rem_60_digits_by_4_digits/no_nulls 1.33 76.1±0.27µs 12.8 MElem/sec 1.00 57.4±0.15µs 17.0 MElem/sec
```
</details>
<details><summary>Per-runner information</summary>
<details><summary>decimal_division — shard 1/1</summary>
**Node:** gk3-benchmark-cluster-nap-wkl49k2l-484c2473-8jnl
**Instance:** c4a-highmem-16 (12 vCPU / 65 GiB)
**uname:**
```text
Linux bench-c6194213985-3455-xv22r 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux
```
**BENCH_COMMAND:**
```sh
cargo bench --features=arrow,async,test_common,experimental,object_store --bench decimal_division
```
<details><summary>CPU Details (lscpu)</summary>
```text
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 125.0s |
| Peak memory | 12.4 MiB |
| Avg memory | 11.2 MiB |
| CPU user | 120.8s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 120.0s |
| Peak memory | 12.8 MiB |
| Avg memory | 11.6 MiB |
| CPU user | 116.1s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
</details>
</details>
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6194213985:finish:13fb493babfa9f2c6e88ea8f0721ab64 -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4314714663
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -59,6 +59,29 @@ fn bits(arr: &[u64]) -> usize {
/// Division of numerator by a u64 divisor
fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N], [u64; N]) {
+ // x86_64 divides by one word with `div`. On 32-bit targets, including wasm32, each
+ // 64x64-to-128-bit product in the reciprocal path would call `__multi3`
+ #[cfg(any(
+ all(target_arch = "x86_64", not(miri)),
+ not(target_pointer_width = "64")
+ ))]
+ {
+ div_rem_small_word(numerator, divisor)
+ }
+
+ // Here `div_rem_word` would call `__udivti3` for every digit
+ #[cfg(all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri)))]
+ {
+ div_rem_small_reciprocal(numerator, divisor)
+ }
Review Comment:
> The cfg attributes makes it harder to understand the fallback here, maybe add a a comment which is the fallback and move it to be the last like most people assume
Good idea. The reciprocal path is now first, with a comment that says what its `cfg` selects: the 64-bit targets where `div_rem_word` is a `u128` division rather than the `div` instruction. That condition is the same as the one in `div_rem_word`. The `div_rem_word` path is last, and its `cfg` is `not(...)` of the first one's, so it reads as the fallback.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194213985
run benchmark decimal_division
```
env:
BENCH_FILTER: decimal256_scalar
```
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194215541
🤖 Benchmark starting (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194213985)
**Target:** decimal_division
**Sharding factor: 1** (1 workers).
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark decimal_division
env:
BENCH_FILTER: decimal256_scalar
shards: 1
```
</details>
Results will be posted when all workers finish.
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6194213985:start:c95152acd358244cb3dde549881cbc6c -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194209205
🤖 Benchmark starting (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194207134)
**Target:** i256
**Sharding factor: 1** (1 workers).
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark i256
env:
BENCH_FILTER: i256_div_rem
shards: 1
```
</details>
Results will be posted when all workers finish.
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6194207134:start:3f7ae3549d896a453e639434e92de8ce -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194283037
🤖 Benchmark starting (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194280451)
**Target:** cast_decimal
**Sharding factor: 1** (1 workers).
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark cast_decimal
env:
BENCH_FILTER: decimal_downscale/decimal256
shards: 1
```
</details>
Results will be posted when all workers finish.
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6194280451:start:437fc006247d61c4336d7afe774cf367 -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4306945844
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +95,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf),
Review Comment:
Maybe add the paper name in the comment in case the link ever die
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +95,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf),
+/// which avoids a `u128` division
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn reciprocal_word(divisor: u64) -> u64 {
+ debug_assert_eq!(divisor >> 63, 1);
+
+ // `floor((2^19 - 3 * 2^8) / d9)` for each value of the top 9 bits `d9`
+ const TABLE: [u16; 256] = {
+ let mut table = [0; 256];
+ let mut i = 0;
+ while i < 256 {
+ table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
+ i += 1;
+ }
+ table
+ };
+
+ let d0 = divisor & 1;
+ let d9 = divisor >> 55;
+ let d40 = (divisor >> 24) + 1;
+ let d63 = (divisor >> 1) + d0;
+
+ // `d9` is in 256..512, so masking gives `d9 - 256` without a bounds check
+ let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
+ // Two Newton iterations, each about doubling the bits of precision
+ let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
+ let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
+ // `2^96 - v2 * d63 + floor(v2 / 2) * d0`, which the paper shows fits in 64 bits
+ let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
+ let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
+ // `floor((v3 + 2^64 + 1) * divisor / 2^64)`, without overflowing a `u128`
+ let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
+ v3.wrapping_sub(p.wrapping_add(divisor))
+}
+
+/// Divides `hi:lo` by a divisor with its top bit set, given its [`reciprocal_word`]
+///
+/// This is algorithm 4 of [Möller and Granlund (2011)](https://gmplib.org/~tege/division-paper.pdf)
Review Comment:
Maybe add the paper name in the comment in case the link ever die
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4306959691
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
+ divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
+ let expected = (n / u128::from(divisor)) as u64;
+ assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
+ }
+ }
+
+ #[test]
+ fn test_div_rem_word_reciprocal() {
+ // The second correction, which random inputs rarely reach, runs for this input
+ let (hi, lo, divisor) = (
+ 3787258589690185862,
+ 17800796494353475223,
+ 9357586864501027680,
+ );
+ let n = (u128::from(hi) << 64) | u128::from(lo);
+ let d = u128::from(divisor);
+ assert_eq!(
+ div_rem_word_reciprocal(hi, lo, divisor, reciprocal_word(divisor)),
+ ((n / d) as u64, (n % d) as u64)
+ );
+
+ let mut rng = rng();
Review Comment:
can you make it seeded rng to be deterministic
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
Review Comment:
can you make it seeded rng to be deterministic
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "Rich-T-kid (via GitHub)" <gi...@apache.org>.
Rich-T-kid merged PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296823709
🤖 Benchmark starting (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296822196)
**Target:** decimal_division
**Sharding factor: 1** (1 workers).
Comparing i256-div-rem-small-reciprocal (0a6a25caf23cb1ee5cbd419ef4a7c3dcef01e311) to d58a0fc (merge-base) [diff](https://github.com/apache/arrow-rs/compare/d58a0fce35b67836ac9b2e20a7efe47a584e0a86..0a6a25caf23cb1ee5cbd419ef4a7c3dcef01e311)
<details><summary>Run configuration</summary>
```yaml
run benchmark decimal_division
env:
BENCH_FILTER: decimal256_scalar
shards: 1
```
</details>
Results will be posted when all workers finish.
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6296822196:start:bbbde67f354cb8f87632e1bf37de60b9 -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "Rich-T-kid (via GitHub)" <gi...@apache.org>.
Rich-T-kid commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4328727875
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +93,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund, "Improved division by invariant integers" (2011)](https://gmplib.org/~tege/division-paper.pdf),
+/// which avoids a `u128` division
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn reciprocal_word(divisor: u64) -> u64 {
+ debug_assert_eq!(divisor >> 63, 1);
+
+ // `floor((2^19 - 3 * 2^8) / d9)` for each value of the top 9 bits `d9`
+ const TABLE: [u16; 256] = {
+ let mut table = [0; 256];
+ let mut i = 0;
+ while i < 256 {
+ table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
+ i += 1;
+ }
+ table
+ };
+
+ let d0 = divisor & 1;
+ let d9 = divisor >> 55;
+ let d40 = (divisor >> 24) + 1;
+ let d63 = (divisor >> 1) + d0;
+
+ // `d9` is in 256..512, so masking gives `d9 - 256` without a bounds check
+ let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
+ // Two Newton iterations, each about doubling the bits of precision
+ let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
+ let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
+ // `2^96 - v2 * d63 + floor(v2 / 2) * d0`, which the paper shows fits in 64 bits
+ let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
+ let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
+ // `floor((v3 + 2^64 + 1) * divisor / 2^64)`, without overflowing a `u128`
+ let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
+ v3.wrapping_sub(p.wrapping_add(divisor))
+}
Review Comment:
thank you this makes more sense to me,
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -72,6 +93,104 @@ fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N
(numerator, rem_padded)
}
+/// Like [`div_rem_small_word`], but divides each digit by multiplying with a
+/// reciprocal of the divisor, computed once
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn div_rem_small_reciprocal<const N: usize>(
+ numerator: &[u64; N],
+ divisor: u64,
+) -> ([u64; N], [u64; N]) {
+ // Shifting both operands so the divisor's top bit is set leaves the quotient unchanged
+ let shift = divisor.leading_zeros();
+ let divisor = divisor << shift;
+ let reciprocal = reciprocal_word(divisor);
+ let numerator = full_shl(numerator, shift);
+
+ // The top digit is below 2^shift, and so below the divisor
+ let mut rem = numerator[N];
+ let mut quotient = [0; N];
+ for i in (0..N).rev() {
+ let (q, r) = div_rem_word_reciprocal(rem, numerator[i], divisor, reciprocal);
+ quotient[i] = q;
+ rem = r;
+ }
+
+ let mut rem_padded = [0; N];
+ rem_padded[0] = rem >> shift;
+ (quotient, rem_padded)
+}
+
+/// Returns `floor((2^128 - 1) / divisor) - 2^64` for a divisor with its top bit set
+///
+/// This is algorithm 2 of [Möller and Granlund, "Improved division by invariant integers" (2011)](https://gmplib.org/~tege/division-paper.pdf),
+/// which avoids a `u128` division
+#[cfg(any(
+ test,
+ all(target_pointer_width = "64", any(not(target_arch = "x86_64"), miri))
+))]
+fn reciprocal_word(divisor: u64) -> u64 {
+ debug_assert_eq!(divisor >> 63, 1);
+
+ // `floor((2^19 - 3 * 2^8) / d9)` for each value of the top 9 bits `d9`
+ const TABLE: [u16; 256] = {
+ let mut table = [0; 256];
+ let mut i = 0;
+ while i < 256 {
+ table[i] = (((1 << 19) - 3 * (1 << 8)) / (i as u32 + 256)) as u16;
+ i += 1;
+ }
+ table
+ };
+
+ let d0 = divisor & 1;
+ let d9 = divisor >> 55;
+ let d40 = (divisor >> 24) + 1;
+ let d63 = (divisor >> 1) + d0;
+
+ // `d9` is in 256..512, so masking gives `d9 - 256` without a bounds check
+ let v0 = u64::from(TABLE[(d9 & 0xff) as usize]);
+ // Two Newton iterations, each about doubling the bits of precision
+ let v1 = (v0 << 11) - ((v0 * v0 * d40) >> 40) - 1;
+ let v2 = (v1 << 13) + ((v1 * ((1 << 60) - v1 * d40)) >> 47);
+ // `2^96 - v2 * d63 + floor(v2 / 2) * d0`, which the paper shows fits in 64 bits
+ let e = ((v2 >> 1) & d0.wrapping_neg()).wrapping_sub(v2.wrapping_mul(d63));
+ let v3 = (v2 << 31).wrapping_add(((u128::from(v2) * u128::from(e)) >> 65) as u64);
+ // `floor((v3 + 2^64 + 1) * divisor / 2^64)`, without overflowing a `u128`
+ let p = (((u128::from(v3) + 1) * u128::from(divisor)) >> 64) as u64;
+ v3.wrapping_sub(p.wrapping_add(divisor))
+}
Review Comment:
thank you this makes more sense to me
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296832120
🤖 Benchmark starting (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296829905)
**Target:** cast_decimal
**Sharding factor: 1** (1 workers).
Comparing i256-div-rem-small-reciprocal (0a6a25caf23cb1ee5cbd419ef4a7c3dcef01e311) to d58a0fc (merge-base) [diff](https://github.com/apache/arrow-rs/compare/d58a0fce35b67836ac9b2e20a7efe47a584e0a86..0a6a25caf23cb1ee5cbd419ef4a7c3dcef01e311)
<details><summary>Run configuration</summary>
```yaml
run benchmark cast_decimal
env:
BENCH_FILTER: decimal_downscale/decimal256
RUSTFLAGS: -C llvm-args=-align-all-functions=6 -C llvm-args=-align-all-nofallthru-blocks=6
shards: 1
```
</details>
Results will be posted when all workers finish.
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6296829905:start:a121b8c53562d2d16c826f67acdd0fb1 -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "Rich-T-kid (via GitHub)" <gi...@apache.org>.
Rich-T-kid commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296829905
run benchmark cast_decimal
env:
BENCH_FILTER: decimal_downscale/decimal256
RUSTFLAGS: "-C llvm-args=-align-all-functions=6 -C llvm-args=-align-all-nofallthru-blocks=6"
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194434803
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194280451)
**Target:** cast_decimal
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark cast_decimal
env:
BENCH_FILTER: decimal_downscale/decimal256
shards: 1
```
</details>
<details><summary>Details</summary>
```
group base changed
----- ---- -------
decimal_downscale/decimal256 (41, 20) -> decimal128(38, 6) 30 digits/mixed_nulls/safe 1.00 217.1±0.28µs 36.0 MElem/sec 1.02 221.1±0.28µs 35.3 MElem/sec
decimal_downscale/decimal256 (41, 20) -> decimal128(38, 6) 30 digits/no_nulls/safe 1.00 217.1±0.26µs 36.0 MElem/sec 1.02 221.6±1.19µs 35.3 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 38 digits/mixed_nulls/safe 1.00 154.5±0.26µs 50.6 MElem/sec 1.19 183.1±0.42µs 42.7 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 38 digits/no_nulls/safe 1.00 154.7±0.34µs 50.5 MElem/sec 1.18 183.0±0.44µs 42.7 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 60 digits/mixed_nulls/safe 1.50 429.6±1.02µs 18.2 MElem/sec 1.00 286.8±0.34µs 27.2 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 60 digits/no_nulls/safe 1.49 429.8±1.29µs 18.2 MElem/sec 1.00 288.7±0.41µs 27.1 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/mixed_nulls/safe 1.31 399.2±0.65µs 19.6 MElem/sec 1.00 305.1±0.85µs 25.6 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/mixed_nulls/strict 1.27 421.3±1.09µs 18.5 MElem/sec 1.00 330.8±0.78µs 23.6 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/no_nulls/safe 1.31 444.4±0.85µs 17.6 MElem/sec 1.00 339.3±0.72µs 23.0 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/no_nulls/strict 1.26 470.4±1.29µs 16.6 MElem/sec 1.00 373.9±1.16µs 20.9 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/mixed_nulls/safe 1.00 350.5±0.72µs 22.3 MElem/sec 1.03 359.9±0.67µs 21.7 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/mixed_nulls/strict 1.00 374.2±1.95µs 20.9 MElem/sec 1.01 377.1±1.94µs 20.7 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/no_nulls/safe 1.00 391.3±0.96µs 20.0 MElem/sec 1.02 399.6±0.82µs 19.6 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/no_nulls/strict 1.00 413.7±2.58µs 18.9 MElem/sec 1.01 418.3±2.08µs 18.7 MElem/sec
```
</details>
<details><summary>Per-runner information</summary>
<details><summary>cast_decimal — shard 1/1</summary>
**Node:** gk3-benchmark-cluster-nap-wkl49k2l-484c2473-4pfv
**Instance:** c4a-highmem-16 (12 vCPU / 65 GiB)
**uname:**
```text
Linux bench-c6194280451-3456-bcprx 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux
```
**BENCH_COMMAND:**
```sh
cargo bench --features=arrow,async,test_common,experimental,object_store --bench cast_decimal
```
<details><summary>CPU Details (lscpu)</summary>
```text
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 145.0s |
| Peak memory | 14.9 MiB |
| Avg memory | 13.6 MiB |
| CPU user | 140.9s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 145.0s |
| Peak memory | 15.6 MiB |
| Avg memory | 14.0 MiB |
| CPU user | 139.2s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
</details>
</details>
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6194280451:finish:908e00f6fc9a267f63d777ac2531d07f -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4306917208
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -59,6 +59,29 @@ fn bits(arr: &[u64]) -> usize {
/// Division of numerator by a u64 divisor
fn div_rem_small<const N: usize>(numerator: &[u64; N], divisor: u64) -> ([u64; N], [u64; N]) {
+ // x86_64 divides by one word with `div`. On 32-bit targets, including wasm32, each
+ // 64x64-to-128-bit product in the reciprocal path would call `__multi3`
+ #[cfg(any(
+ all(target_arch = "x86_64", not(miri)),
+ not(target_pointer_width = "64")
+ ))]
+ {
+ div_rem_small_word(numerator, divisor)
+ }
+
+ // Here `div_rem_word` would call `__udivti3` for every digit
Review Comment:
```suggestion
// Fallback implementation
// Here `div_rem_word` would call `__udivti3` for every digit
```
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194211866
🤖 Benchmark starting (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194210246)
**Target:** i256
**Sharding factor: 1** (1 workers).
Comparing i256-div-rem-small-reciprocal (08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee) to 418340d (merge-base) [diff](https://github.com/apache/arrow-rs/compare/418340d5188f6e2949c4a0545b3e437dfdc848f8..08d2e4e8ae5db12d9fa4e13e7b9710dedd262dee)
<details><summary>Run configuration</summary>
```yaml
run benchmark i256
env:
BENCH_FILTER: i256_div_rem
resources:
arch: amd64
shards: 1
```
</details>
Results will be posted when all workers finish.
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6194210246:start:4494688e0e1eeae05d839fcb04c13fc3 -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6194280451
run benchmark cast_decimal
```
env:
BENCH_FILTER: decimal_downscale/decimal256
```
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal outside x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6195147060
run benchmark cast_decimal
```
env:
BENCH_FILTER: decimal_downscale/decimal256
RUSTFLAGS: "-C llvm-args=-align-all-functions=6 -C llvm-args=-align-all-nofallthru-blocks=6"
```
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#issuecomment-6297003526
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/11580#issuecomment-6296829905)
**Target:** cast_decimal
Comparing i256-div-rem-small-reciprocal (0a6a25caf23cb1ee5cbd419ef4a7c3dcef01e311) to d58a0fc (merge-base) [diff](https://github.com/apache/arrow-rs/compare/d58a0fce35b67836ac9b2e20a7efe47a584e0a86..0a6a25caf23cb1ee5cbd419ef4a7c3dcef01e311)
<details><summary>Run configuration</summary>
```yaml
run benchmark cast_decimal
env:
BENCH_FILTER: decimal_downscale/decimal256
RUSTFLAGS: -C llvm-args=-align-all-functions=6 -C llvm-args=-align-all-nofallthru-blocks=6
shards: 1
```
</details>
<details><summary>Details</summary>
```
group base changed
----- ---- -------
decimal_downscale/decimal256 (41, 20) -> decimal128(38, 6) 30 digits/mixed_nulls/safe 1.00 214.4±0.37µs 36.4 MElem/sec 1.01 217.2±0.43µs 36.0 MElem/sec
decimal_downscale/decimal256 (41, 20) -> decimal128(38, 6) 30 digits/no_nulls/safe 1.00 214.9±0.25µs 36.3 MElem/sec 1.01 217.2±0.29µs 36.0 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 38 digits/mixed_nulls/safe 1.18 190.6±0.39µs 41.0 MElem/sec 1.00 161.1±0.36µs 48.5 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 38 digits/no_nulls/safe 1.18 190.6±0.41µs 41.0 MElem/sec 1.00 161.2±0.31µs 48.5 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 60 digits/mixed_nulls/safe 1.47 429.8±1.10µs 18.2 MElem/sec 1.00 292.2±0.62µs 26.7 MElem/sec
decimal_downscale/decimal256 (76, 10) -> (76, 2) 60 digits/no_nulls/safe 1.49 429.7±1.10µs 18.2 MElem/sec 1.00 289.1±0.49µs 27.0 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/mixed_nulls/safe 1.30 401.5±0.57µs 19.5 MElem/sec 1.00 307.9±0.84µs 25.4 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/mixed_nulls/strict 1.29 428.8±1.22µs 18.2 MElem/sec 1.00 332.9±0.82µs 23.5 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/no_nulls/safe 1.33 450.1±0.48µs 17.4 MElem/sec 1.00 339.3±0.58µs 23.0 MElem/sec
decimal_downscale/decimal256 (76, 20) -> decimal128(38, 6) 48 digits fallible/no_nulls/strict 1.27 478.9±1.16µs 16.3 MElem/sec 1.00 375.8±1.11µs 20.8 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/mixed_nulls/safe 1.00 354.9±0.79µs 22.0 MElem/sec 1.01 359.9±0.56µs 21.7 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/mixed_nulls/strict 1.00 375.3±1.80µs 20.8 MElem/sec 1.01 378.8±2.15µs 20.6 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/no_nulls/safe 1.00 394.1±0.97µs 19.8 MElem/sec 1.02 400.4±0.79µs 19.5 MElem/sec
decimal_downscale/decimal256 (76, 40) -> decimal128(38, 6) 42 digits fallible/no_nulls/strict 1.00 419.5±2.30µs 18.6 MElem/sec 1.00 420.1±2.07µs 18.6 MElem/sec
```
</details>
<details><summary>Per-runner information</summary>
<details><summary>cast_decimal — shard 1/1</summary>
**Node:** gk3-benchmark-cluster-nap-1s1omc2c-e78be462-96cz
**Instance:** c4a-highmem-16 (12 vCPU / 65 GiB)
**uname:**
```text
Linux bench-c6296829905-3665-6qjhj 6.12.94+ #1 SMP Fri Aug 21 08:00:16 UTC 2026 aarch64 GNU/Linux
```
**BENCH_COMMAND:**
```sh
cargo bench --features=arrow,async,test_common,experimental,object_store --bench cast_decimal
```
<details><summary>CPU Details (lscpu)</summary>
```text
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 145.0s |
| Peak memory | 16.0 MiB |
| Avg memory | 14.5 MiB |
| CPU user | 138.9s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 150.0s |
| Peak memory | 16.6 MiB |
| Avg memory | 14.9 MiB |
| CPU user | 144.2s |
| CPU sys | 0.0s |
| Peak spill | 0 B |
</details>
</details>
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
<!-- benchmark-request:6296829905:finish:165f188413bdcf76df11839459e2b495 -->
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4306963398
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
+ divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
+ let expected = (n / u128::from(divisor)) as u64;
+ assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
+ }
+ }
+
+ #[test]
+ fn test_div_rem_word_reciprocal() {
+ // The second correction, which random inputs rarely reach, runs for this input
+ let (hi, lo, divisor) = (
+ 3787258589690185862,
+ 17800796494353475223,
+ 9357586864501027680,
Review Comment:
What is special for those numbers?
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] perf(arrow-buffer): divide `i256` by a single word with a reciprocal on 64-bit targets other than x86_64 [arrow-rs]
Posted by "mbutrovich (via GitHub)" <gi...@apache.org>.
mbutrovich commented on code in PR #11580:
URL: https://github.com/apache/arrow-rs/pull/11580#discussion_r4314725571
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
Review Comment:
Done.
##########
arrow-buffer/src/bigint/div.rs:
##########
@@ -300,3 +421,116 @@ impl<T, const N: usize> std::ops::DerefMut for ArrayPlusOne<T, N> {
unsafe { std::slice::from_raw_parts_mut(x.cast::<T>(), N + 1) }
}
}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use rand::{RngExt, rng};
+
+ fn check_div_rem_small<const N: usize>(numerator: [u64; N], divisor: u64) {
+ let expected = div_rem_small_word(&numerator, divisor);
+ assert_eq!(
+ div_rem_small_reciprocal(&numerator, divisor),
+ expected,
+ "{numerator:?} / {divisor}"
+ );
+ }
+
+ #[test]
+ fn test_reciprocal_word() {
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ // Each boundary between entries of the lookup table
+ for i in 257..512u64 {
+ divisors.extend([(i << 55) - 1, i << 55, (i << 55) + 1]);
+ }
+ let mut rng = rng();
+ divisors.extend((0..100_000).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let n = (u128::from(!divisor) << 64) | u128::from(u64::MAX);
+ let expected = (n / u128::from(divisor)) as u64;
+ assert_eq!(reciprocal_word(divisor), expected, "{divisor}");
+ }
+ }
+
+ #[test]
+ fn test_div_rem_word_reciprocal() {
+ // The second correction, which random inputs rarely reach, runs for this input
+ let (hi, lo, divisor) = (
+ 3787258589690185862,
+ 17800796494353475223,
+ 9357586864501027680,
+ );
+ let n = (u128::from(hi) << 64) | u128::from(lo);
+ let d = u128::from(divisor);
+ assert_eq!(
+ div_rem_word_reciprocal(hi, lo, divisor, reciprocal_word(divisor)),
+ ((n / d) as u64, (n % d) as u64)
+ );
+
+ let mut rng = rng();
+ let mut divisors = vec![1 << 63, (1 << 63) + 1, u64::MAX - 1, u64::MAX];
+ divisors.extend((0..100).map(|_| rng.random::<u64>() | (1 << 63)));
+ for divisor in divisors {
+ let reciprocal = reciprocal_word(divisor);
+ let mut his = vec![0, 1, divisor / 2, divisor - 1];
+ his.extend((0..20).map(|_| rng.random_range(0..divisor)));
+ for hi in his {
+ let mut los = vec![0, 1, divisor - 1, divisor, u64::MAX];
+ los.extend((0..20).map(|_| rng.random::<u64>()));
+ for lo in los {
+ let n = (u128::from(hi) << 64) | u128::from(lo);
+ let d = u128::from(divisor);
+ let expected = ((n / d) as u64, (n % d) as u64);
+ assert_eq!(
+ div_rem_word_reciprocal(hi, lo, divisor, reciprocal),
+ expected,
+ "{n} / {divisor}"
+ );
+ }
+ }
+ }
+ }
+
+ #[test]
+ fn test_div_rem_small_reciprocal() {
+ let mut rng = rng();
+ let numerators = [
+ [0; 4],
+ [1, 0, 0, 0],
+ [0, 0, 0, 1],
+ [u64::MAX; 4],
+ [0, 0, 0, u64::MAX],
+ [u64::MAX, 0, 0, 0],
+ rng.random(),
+ ];
+ // Every normalization shift, with divisors at and next to each power of two
+ for shift in 0..64 {
+ let p = 1u64 << shift;
+ let mut divisors = vec![p, p.wrapping_mul(2).wrapping_sub(1)];
+ divisors.extend(p.checked_add(1));
+ divisors.extend(p.checked_sub(1).filter(|d| *d != 0));
+ for divisor in divisors {
+ for numerator in numerators {
+ check_div_rem_small(numerator, divisor);
+ check_div_rem_small([numerator[0], numerator[1]], divisor);
+ check_div_rem_small([numerator[0]], divisor);
+ }
+ }
+ }
+ // Powers of ten, as used when rescaling decimals
+ for k in 0..=19 {
+ let p = 10u64.pow(k);
+ for divisor in [p - 1, p, p + 1].into_iter().filter(|d| *d != 0) {
+ for numerator in numerators {
+ check_div_rem_small(numerator, divisor);
+ }
+ }
+ }
+ for _ in 0..1000 {
+ let divisor = rng.random::<u64>() >> rng.random_range(0..64);
Review Comment:
Done.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org