sdf-jkl opened a new pull request, #11086: URL: https://github.com/apache/arrow-rs/pull/11086
# Which issue does this PR close? Related to #11055. This draft builds on Richard's changes at `4727e6a654d28f6371a9fd352a34d8a77af9c0e8` and includes those commits. The measurements below compare against that PR head, not against `main`. # Rationale for this change Filtering a bitmap requires gathering the selected bits from each input word and concatenating the resulting fragments. Finishing one word's variable-length extraction loop before starting the next leaves this work scalar in the inspected builds. This draft processes eight words together, advancing one selected bit per active lane per iteration. It exposes independent operations across words to LLVM's vectorizer while keeping the implementation in stable, portable Rust. A batch runs until its largest mask population count is exhausted, so shorter lanes can do idle work; the sparse tradeoff still needs evaluation. # What changes are included in this PR? - Extract eight independent `u64` fragments by testing each mask's lowest set bit and conditionally OR-ing a shared destination bit into the lane's result. Empty masks naturally contribute zero. - Pack each batch immediately using stack arrays and the masks' population counts. There is no input-sized fragment allocation. - Preallocate the output, write the current partial word, and advance its index when it fills. Handle carry shifts without shifting by 64 and store words in little-endian byte order. - Retain the original scalar `pext64` for leftover words and the final partial word. - Cover differing lane lengths, empty/full masks, zero-valued fragments, unaligned buffers, longer sources, and word/batch boundaries. The batch helper is kept as a separate optimization unit with `#[inline(never)]`. There are no ISA intrinsics, CPU-feature dispatch branches, or unstable Rust APIs. # Are these changes tested? - `cargo test -p arrow-select --lib --release --offline`: all 432 tests passed. - Separate generic/native boundary checks passed 15,300 variant/oracle comparisons per build. Benchmark inputs were also checked before timing. - Formatting and `git diff --check` passed. Local exploratory measurements of full Boolean filtering, 65,536 rows, in microseconds (lower is better): | Build | Selected | Filter reuse | #11055 | This draft | |---|---:|---|---:|---:| | Generic x86-64 | 10% | repeated | 3.76 | 5.94 | | Generic x86-64 | 10% | cycling | 9.78 | 6.31 | | Generic x86-64 | 50% | repeated | 18.54 | 17.05 | | Generic x86-64 | 50% | cycling | 20.56 | 17.23 | | Generic x86-64 | 79% | repeated | 28.92 | 24.02 | | Generic x86-64 | 79% | cycling | 29.27 | 24.08 | | Native Ryzen | 10% | repeated | 4.01 | 3.34 | | Native Ryzen | 10% | cycling | 8.94 | 3.93 | | Native Ryzen | 50% | repeated | 23.33 | 8.60 | | Native Ryzen | 50% | cycling | 25.53 | 9.19 | | Native Ryzen | 79% | repeated | 41.16 | 11.97 | | Native Ryzen | 79% | cycling | 41.39 | 12.08 | Ryzen AI 9 HX PRO 470; rustc 1.98.1 / LLVM 22.1.8. The native build uses `RUSTFLAGS="-C target-cpu=native"` for the harness and dependencies; the generic build has no CPU override. Each build compares the implementations in one executable, pinned to CPU 2, with rotated order over 21 rounds and approximately 3 ms per variant per round. Numbers are median thread CPU time, including allocation and excluding input/predicate construction. Repeated reuses one bitmap; cycling uses 64 prebuilt bitmaps. These are exploratory harness results, not Criterion confidence intervals, and thread CPU time does not eliminate clock/cache interference. The generic repeated 10% case regresses. Very sparse direct-gather cases also remain a concern; optimized sparse filtering may bypass this kernel. Inspection of the extraction loop found scalar conditional moves in the final generic x86 build and ZMM SIMD in the native build. Standalone Rust probes produce YMM SIMD with `target-cpu=x86-64-v3` and NEON for both generic AArch64 and `target-cpu=neoverse-v2`. ARM results are code-generation checks only: no ARM performance measurements or inspection of the bot's compiled binary yet. # Are there any user-facing changes? Filtering results and public APIs are unchanged. This draft changes performance and needs further evaluation, particularly on the ARM benchmark runner and sparse workloads. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
