You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "dmatth1 (via GitHub)" <gi...@apache.org> on 2026/05/23 14:16:20 UTC
[PR] parquet: SIMD-accelerate Sbbf probe (AVX2, scalar fallback) [arrow-rs]
dmatth1 opened a new pull request, #10011:
URL: https://github.com/apache/arrow-rs/pull/10011
# Which issue does this PR close?
No tracked issue — opening directly, following the precedent of [apache/arrow-go#336](https://github.com/apache/arrow-go/pull/336) which shipped AVX2/SSE4/NEON SBBF probes in 18.3.0, and paralleling an in-progress
[[DISCUSS]](https://lists.apache.org/thread/omof0fq47tndfd80g5hwp2bvjmzvpb40) thread on `dev@arrow.apache.org` for the C++ port of the same kernel.
# Rationale for this change
`Sbbf::check` / `Sbbf::insert` are on the hot path of Parquet row-group skipping for every reader downstream of `arrow-rs` (DataFusion, Databend, InfluxDB / IOx, RisingWave, GreptimeDB). Each 256-bit Parquet block is exactly one AVX2 vector;
the K=8 lane test collapses to one `vptest` (`_mm256_testc_si256`). This PR vectorises that loop on x86_64 without changing the algorithm, hash, salts, or wire format. NEON / aarch64 SIMD support is slated for a follow-up PR.
# What changes are included in this PR?
- AVX2 kernel in `simd_x86`, dispatched via cached `is_x86_feature_detected!("avx2")` (dead-coded when `-C target-cpu=native`).
- Scalar `Block::{check,insert}` retained as the production fallback for non-AVX2 x86 / aarch64 / wasm32 / RISC-V / 32-bit / big-endian, and as the correctness reference the AVX2 kernel is diff-tested against.
- `Block` changed from `#[repr(transparent)]` to `#[repr(C, align(32))]`. Byte layout unchanged; alignment is asserted at compile time so the AVX2 aligned load/store contract is load-bearing.
- `parquet/benches/bloom_filter.rs` gains `bench_check` (miss/hit × three cache regimes) and `bench_insert` exercising the public API.
# Are these changes tested?
Yes. The 31 pre-existing `bloom_filter` unit tests continue to pass on x86_64 with and without `-C target-cpu=native`. Two new diff tests — `test_simd_{check,insert}_matches_scalar` — assert bit-identical AVX2-vs-scalar output across 10K
random `(block, hash)` pairs each. Benchmark results (Cascade Lake-class Xeon) are in the commit message.
# Are there any user-facing changes?
No. Public API, MSRV, dependencies, and wire format are all unchanged. The only observable effect is faster `Sbbf::check` / `Sbbf::insert` on x86_64 hosts with AVX2.
---
The SIMD kernel was drafted with AI assistance and reviewed line-by-line; correctness is enforced in CI by the diff tests above. `cargo fmt --all -- --check` and `cargo clippy -p parquet --all-targets -- -D warnings` both clean on this branch.
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "etseidl (via GitHub)" <gi...@apache.org>.
etseidl commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585582765
run benchmark bloom_filter
--
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] parquet: SIMD-accelerate Sbbf probe (AVX2, scalar fallback) [arrow-rs]
Posted by "etseidl (via GitHub)" <gi...@apache.org>.
etseidl commented on code in PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#discussion_r3319250440
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -229,52 +238,24 @@ impl Block {
fn insert(&mut self, hash: u32) {
let mask = Self::mask(hash);
for i in 0..8 {
- self[i] |= mask[i];
+ self.0[i] |= mask.0[i];
}
}
- /// Check membership: returns `true` when *every* bit from `mask(hash)` is
- /// already set in this block (`block[i] & mask[i] != 0` for all 8 words).
+ /// Check membership: `true` iff every bit in `mask(hash)` is set in this
+ /// block (i.e. the value was probably inserted). `false` is definitive.
///
- /// A `true` result means "probably present" (other inserts may have set
- /// the same bits). A `false` is definitive — the value was never inserted.
+ /// Branchless `acc |= !block & mask; acc == 0` — the "testc" reduction
+ /// shape LLVM autovectorizes. A short-circuiting `.all()` would win a
+ /// few lanes on miss but defeat vectorization.
+ #[inline]
fn check(&self, hash: u32) -> bool {
let mask = Self::mask(hash);
+ let mut acc = 0u32;
for i in 0..8 {
- if self[i] & mask[i] == 0 {
- return false;
- }
- }
- true
- }
-}
-
-impl std::ops::Index<usize> for Block {
Review Comment:
Why are these `impl`s removed? I think that makes this a breaking API change.
##########
parquet/benches/bloom_filter.rs:
##########
@@ -104,10 +108,123 @@ fn bench_insert_only(c: &mut Criterion) {
group.finish();
}
+/// Benchmark `Sbbf::insert` across the same three cache regimes as
Review Comment:
It would be nice for the bench changes to be a separate PR.
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "dmatth1 (via GitHub)" <gi...@apache.org>.
dmatth1 commented on code in PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#discussion_r3329374263
##########
parquet/benches/bloom_filter.rs:
##########
@@ -104,10 +108,123 @@ fn bench_insert_only(c: &mut Criterion) {
group.finish();
}
+/// Benchmark `Sbbf::insert` across the same three cache regimes as
Review Comment:
Done! See https://github.com/apache/arrow-rs/pull/10041
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585604813
🤖 Arrow criterion benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585582765)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
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>Details</summary>
<p>
```
group main sbbf-simd
----- ---- ---------
check/hit/l_32MiB 1.38 522.5±2.51µs 91.3 MElem/sec 1.00 378.1±6.45µs 126.1 MElem/sec
check/hit/m_2MiB 1.57 475.9±5.96µs 100.2 MElem/sec 1.00 303.1±2.72µs 157.3 MElem/sec
check/hit/s_128KiB 1.63 392.2±0.66µs 121.6 MElem/sec 1.00 240.8±0.88µs 198.1 MElem/sec
check/miss/l_32MiB 1.00 360.1±6.16µs 132.4 MElem/sec 1.04 373.8±1.11µs 127.6 MElem/sec
check/miss/m_2MiB 1.04 322.7±2.72µs 147.8 MElem/sec 1.00 310.9±4.59µs 153.4 MElem/sec
check/miss/s_128KiB 1.00 231.0±1.15µs 206.5 MElem/sec 1.04 241.3±0.66µs 197.6 MElem/sec
fold_to_target_fpp/ndv/1000 1.00 71.1±1.55µs 439.7 MElem/sec 1.00 71.0±1.37µs 440.3 MElem/sec
fold_to_target_fpp/ndv/10000 1.00 65.9±1.82µs 474.2 MElem/sec 1.07 70.2±11.00µs 444.9 MElem/sec
fold_to_target_fpp/ndv/100000 1.10 78.5±15.79µs 398.3 MElem/sec 1.00 71.2±8.88µs 438.7 MElem/sec
insert/ins/l_32MiB 1.08 385.1±2.08µs 123.8 MElem/sec 1.00 358.0±6.11µs 133.2 MElem/sec
insert/ins/m_2MiB 1.04 309.0±2.26µs 154.3 MElem/sec 1.00 295.7±4.41µs 161.2 MElem/sec
insert/ins/s_128KiB 1.01 227.5±0.65µs 209.6 MElem/sec 1.00 226.3±0.46µs 210.7 MElem/sec
insert_and_fold/values/1000 1.00 83.4±1.84µs 11.4 MElem/sec 1.06 88.0±0.18µs 10.8 MElem/sec
insert_and_fold/values/10000 1.04 109.4±0.77µs 87.2 MElem/sec 1.00 104.9±3.73µs 90.9 MElem/sec
insert_and_fold/values/100000 1.00 352.9±2.59µs 270.2 MElem/sec 1.00 351.7±2.22µs 271.1 MElem/sec
insert_only/values/1000 1.00 13.6±0.02µs 70.2 MElem/sec 1.00 13.7±0.01µs 69.8 MElem/sec
insert_only/values/10000 1.07 39.5±0.37µs 241.7 MElem/sec 1.00 37.0±0.12µs 257.5 MElem/sec
insert_only/values/100000 1.00 286.5±1.27µs 332.9 MElem/sec 1.00 285.4±1.97µs 334.1 MElem/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 185.0s |
| Peak memory | 4.6 GiB |
| Avg memory | 4.2 GiB |
| CPU user | 165.6s |
| CPU sys | 16.6s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 185.0s |
| Peak memory | 4.5 GiB |
| Avg memory | 4.2 GiB |
| CPU user | 164.1s |
| CPU sys | 18.8s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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] parquet: SIMD-accelerate Sbbf probe (AVX2, scalar fallback) [arrow-rs]
Posted by "dmatth1 (via GitHub)" <gi...@apache.org>.
dmatth1 commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4526481867
Tested locally on aarch64 too (Apple Silicon M1, baseline NEON autovec):
| Regime | Path | Scalar | Autovec | Speedup |
|-----------|--------|-------:|--------:|--------:|
| S 128 KiB | miss | 4.61 | 3.24 | 1.42x |
| S 128 KiB | hit | 6.84 | 3.17 | 2.16x |
| S 128 KiB | insert | 3.25 | 3.19 | 1.02x |
| M 2 MiB | miss | 5.20 | 3.24 | 1.61x |
| M 2 MiB | hit | 7.16 | 3.26 | 2.20x |
| M 2 MiB | insert | 3.34 | 3.31 | 1.01x |
| L 32 MiB | miss | 6.66 | 5.42 | 1.23x |
| L 32 MiB | hit | 9.72 | 5.25 | 1.85x |
| L 32 MiB | insert | 5.19 | 5.38 | 0.96x |
Big simplifier. I included details about how autovec reduces/lowers instructions in the new commit message. Going to force-push to use this approach.
One thing beyond your suggestion: I prototyped a runtime AVX2-detect shim and dropped it for the simplification (no `unsafe`, no `Sbbf` field, no hot-path branch) since users who care about AVX2 probably already set `-C target-cpu=...`.
--
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] parquet: SIMD-accelerate Sbbf probe (AVX2, scalar fallback) [arrow-rs]
Posted by "dmatth1 (via GitHub)" <gi...@apache.org>.
dmatth1 commented on code in PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#discussion_r3323843361
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -229,52 +238,24 @@ impl Block {
fn insert(&mut self, hash: u32) {
let mask = Self::mask(hash);
for i in 0..8 {
- self[i] |= mask[i];
+ self.0[i] |= mask.0[i];
}
}
- /// Check membership: returns `true` when *every* bit from `mask(hash)` is
- /// already set in this block (`block[i] & mask[i] != 0` for all 8 words).
+ /// Check membership: `true` iff every bit in `mask(hash)` is set in this
+ /// block (i.e. the value was probably inserted). `false` is definitive.
///
- /// A `true` result means "probably present" (other inserts may have set
- /// the same bits). A `false` is definitive — the value was never inserted.
+ /// Branchless `acc |= !block & mask; acc == 0` — the "testc" reduction
+ /// shape LLVM autovectorizes. A short-circuiting `.all()` would win a
+ /// few lanes on miss but defeat vectorization.
+ #[inline]
fn check(&self, hash: u32) -> bool {
let mask = Self::mask(hash);
+ let mut acc = 0u32;
for i in 0..8 {
- if self[i] & mask[i] == 0 {
- return false;
- }
- }
- true
- }
-}
-
-impl std::ops::Index<usize> for Block {
Review Comment:
Block is private type and only used here so I don't think so. I ran `cargo public-api diff` for this branch vs main and didn't see any differences
--
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] parquet: SIMD-accelerate Sbbf probe (AVX2, scalar fallback) [arrow-rs]
Posted by "dmatth1 (via GitHub)" <gi...@apache.org>.
dmatth1 commented on code in PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#discussion_r3323884061
##########
parquet/benches/bloom_filter.rs:
##########
@@ -104,10 +108,123 @@ fn bench_insert_only(c: &mut Criterion) {
group.finish();
}
+/// Benchmark `Sbbf::insert` across the same three cache regimes as
Review Comment:
Mainly for conciseness? Or should we push the bench changes first, then this Sbbf probe change second that way its easy to compare? Otherwise I'd lean towards keeping it in here
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #10011: parquet: SIMD-accelerate Sbbf probe via autovectorization
URL: https://github.com/apache/arrow-rs/pull/10011
--
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] parquet: SIMD-accelerate Sbbf probe (AVX2, scalar fallback) [arrow-rs]
Posted by "jhorstmann (via GitHub)" <gi...@apache.org>.
jhorstmann commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4525814355
It looks to me like with one small change to the `check` function, autovectorization can already generate the same instruction sequences: https://rust.godbolt.org/z/a3zT5Gezr
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585730374
🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585724751)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4585724751-383-nm4ns 6.12.68+ #1 SMP Wed Apr 1 02:23:28 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
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>
Comparing sbbf-simd (5ad8cc05544cb73e44887c87cb6b404849eff52c) to 511ad06 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/511ad068ae2b7f511e16215d9d3c96fb0f334f2c..5ad8cc05544cb73e44887c87cb6b404849eff52c)
BENCH_NAME=bloom_filter
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench bloom_filter
BENCH_FILTER=
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "etseidl (via GitHub)" <gi...@apache.org>.
etseidl commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585724751
run benchmark bloom_filter
```yaml
env:
RUSTFLAGS: -Ctarget-cpu=native
```
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-5154645395
Thank you for your contribution. Unfortunately, this pull request is stale because it has been open 60 days with no activity. Please remove the stale label or comment or this will be closed in 7 days.
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "etseidl (via GitHub)" <gi...@apache.org>.
etseidl commented on code in PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#discussion_r3324992200
##########
parquet/benches/bloom_filter.rs:
##########
@@ -104,10 +108,123 @@ fn bench_insert_only(c: &mut Criterion) {
group.finish();
}
+/// Benchmark `Sbbf::insert` across the same three cache regimes as
Review Comment:
>Or should we push the bench changes first, then this Sbbf probe change second that way its easy to compare?
This (see the [contributing](https://github.com/apache/arrow-rs/blob/main/CONTRIBUTING.md#performance-improvements) guide). Thanks!
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585744334
🤖 Arrow criterion benchmark completed (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585724751)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
<details><summary>CPU Details (lscpu)</summary>
```
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>Details</summary>
<p>
```
group main sbbf-simd
----- ---- ---------
check/hit/l_32MiB 1.34 521.9±2.11µs 91.4 MElem/sec 1.00 388.6±1.17µs 122.7 MElem/sec
check/hit/m_2MiB 1.45 484.4±4.52µs 98.4 MElem/sec 1.00 333.9±2.38µs 142.8 MElem/sec
check/hit/s_128KiB 1.62 393.5±0.59µs 121.2 MElem/sec 1.00 242.8±0.13µs 196.4 MElem/sec
check/miss/l_32MiB 1.00 349.2±1.04µs 136.5 MElem/sec 1.09 381.4±2.76µs 125.0 MElem/sec
check/miss/m_2MiB 1.00 316.3±2.91µs 150.8 MElem/sec 1.10 348.6±5.68µs 136.8 MElem/sec
check/miss/s_128KiB 1.00 229.8±0.51µs 207.5 MElem/sec 1.06 243.9±0.12µs 195.5 MElem/sec
fold_to_target_fpp/ndv/1000 1.00 59.3±1.84µs 527.4 MElem/sec 1.03 60.7±1.70µs 514.5 MElem/sec
fold_to_target_fpp/ndv/10000 1.03 55.5±3.36µs 563.3 MElem/sec 1.00 53.9±1.15µs 580.1 MElem/sec
fold_to_target_fpp/ndv/100000 1.00 53.2±1.41µs 587.1 MElem/sec 1.00 53.1±1.25µs 588.3 MElem/sec
insert/ins/l_32MiB 1.03 377.9±1.35µs 126.2 MElem/sec 1.00 365.1±0.94µs 130.6 MElem/sec
insert/ins/m_2MiB 1.00 311.6±4.80µs 153.1 MElem/sec 1.03 321.5±1.97µs 148.3 MElem/sec
insert/ins/s_128KiB 1.01 225.5±0.14µs 211.4 MElem/sec 1.00 224.1±0.16µs 212.8 MElem/sec
insert_and_fold/values/1000 1.00 69.3±0.14µs 13.8 MElem/sec 1.02 70.8±0.13µs 13.5 MElem/sec
insert_and_fold/values/10000 1.00 87.1±0.15µs 109.5 MElem/sec 1.09 95.0±0.35µs 100.4 MElem/sec
insert_and_fold/values/100000 1.00 316.4±0.56µs 301.4 MElem/sec 1.27 403.0±1.44µs 236.7 MElem/sec
insert_only/values/1000 1.00 13.6±0.01µs 70.3 MElem/sec 1.01 13.7±0.01µs 69.8 MElem/sec
insert_only/values/10000 1.00 36.7±0.03µs 260.1 MElem/sec 1.02 37.3±0.18µs 255.6 MElem/sec
insert_only/values/100000 1.00 268.2±0.38µs 355.6 MElem/sec 1.10 296.3±2.71µs 321.8 MElem/sec
```
</p>
</details>
<details><summary>Resource Usage</summary>
**base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 185.0s |
| Peak memory | 4.6 GiB |
| Avg memory | 4.2 GiB |
| CPU user | 164.3s |
| CPU sys | 16.1s |
| Peak spill | 0 B |
**branch**
| Metric | Value |
|--------|-------|
| Wall time | 180.0s |
| Peak memory | 4.5 GiB |
| Avg memory | 4.1 GiB |
| CPU user | 160.7s |
| CPU sys | 18.4s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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] parquet: SIMD-accelerate Sbbf probe (AVX2, scalar fallback) [arrow-rs]
Posted by "dmatth1 (via GitHub)" <gi...@apache.org>.
dmatth1 commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4526028953
Great callout. Measured bench and the numbers with autovectorization are better:
Same-host, same-session medians (Cascade Lake-class Xeon @ 2.8 GHz), via the public `Sbbf::{check,insert}` API (XXH64 + probe), criterion default profile, ns/op:
| Regime | Path | Scalar | Autovec (this) | Hand-written AVX2 | Autovec vs scalar | Autovec vs hand-written |
|-----------|--------|-------:|---------------:|------------------:|------------------:|------------------------:|
| S 128 KiB | miss | 13.02 | **4.96** | 5.14 | 2.62× | +4% |
| S 128 KiB | hit | 13.47 | **4.95** | 5.20 | 2.72× | +5% |
| S 128 KiB | insert | 11.62 | **5.41** | 5.38 | 2.15× | tied |
| M 2 MiB | miss | 18.88 | **7.47** | 8.18 | 2.53× | +9% |
| M 2 MiB | hit | 18.12 | **7.22** | 8.01 | 2.51× | +11% |
| M 2 MiB | insert | 14.99 | **8.45** | 8.59 | 1.77× | tied |
| L 32 MiB | miss | 27.56 | **11.07** | 13.47 | 2.49× | +18% |
| L 32 MiB | hit | 26.57 | **11.23** | 13.40 | 2.37× | +16% |
| L 32 MiB | insert | 23.53 | **12.77** | 12.60 | 1.84× | tied |
Changes here: https://github.com/apache/arrow-rs/compare/main...dmatth1:arrow-rs:sbbf-autovec-tf
This unlocks Neon/aarch64 so I will bundle those numbers into the next revision.
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "etseidl (via GitHub)" <gi...@apache.org>.
etseidl commented on code in PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#discussion_r3325012810
##########
parquet/src/bloom_filter/mod.rs:
##########
@@ -229,52 +238,24 @@ impl Block {
fn insert(&mut self, hash: u32) {
let mask = Self::mask(hash);
for i in 0..8 {
- self[i] |= mask[i];
+ self.0[i] |= mask.0[i];
}
}
- /// Check membership: returns `true` when *every* bit from `mask(hash)` is
- /// already set in this block (`block[i] & mask[i] != 0` for all 8 words).
+ /// Check membership: `true` iff every bit in `mask(hash)` is set in this
+ /// block (i.e. the value was probably inserted). `false` is definitive.
///
- /// A `true` result means "probably present" (other inserts may have set
- /// the same bits). A `false` is definitive — the value was never inserted.
+ /// Branchless `acc |= !block & mask; acc == 0` — the "testc" reduction
+ /// shape LLVM autovectorizes. A short-circuiting `.all()` would win a
+ /// few lanes on miss but defeat vectorization.
+ #[inline]
fn check(&self, hash: u32) -> bool {
let mask = Self::mask(hash);
+ let mut acc = 0u32;
for i in 0..8 {
- if self[i] & mask[i] == 0 {
- return false;
- }
- }
- true
- }
-}
-
-impl std::ops::Index<usize> for Block {
Review Comment:
Right you are. Had Sbbf in my head 😅
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585589982
🤖 Arrow criterion benchmark running (GKE) | [trigger](https://github.com/apache/arrow-rs/pull/10011#issuecomment-4585582765)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c4585582765-382-4bwhf 6.12.68+ #1 SMP Wed Apr 1 02:23:28 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
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>
Comparing sbbf-simd (5ad8cc05544cb73e44887c87cb6b404849eff52c) to 511ad06 (merge-base) [diff](https://github.com/apache/arrow-rs/compare/511ad068ae2b7f511e16215d9d3c96fb0f334f2c..5ad8cc05544cb73e44887c87cb6b404849eff52c)
BENCH_NAME=bloom_filter
BENCH_COMMAND=cargo bench --features=arrow,async,test_common,experimental,object_store --bench bloom_filter
BENCH_FILTER=
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
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] parquet: SIMD-accelerate Sbbf probe via autovectorization [arrow-rs]
Posted by "dmatth1 (via GitHub)" <gi...@apache.org>.
dmatth1 commented on PR #10011:
URL: https://github.com/apache/arrow-rs/pull/10011#issuecomment-4607598032
Interesting. Looks like for `Neoverse-V2` wins are more minimal (hit win is ~1.3–1.6×, miss is parity or perhaps even a bit behind). I think on Neoverse-V2 scalar short-circuit is similar in speed to the vector kernel whereas for AVX2 and M1 Neon it's not (hence the wins on miss for those platforms too).
Should we extend the benchmark bot to run on x86 so we have those benchmarks auto-populated here?
--
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