You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@arrow.apache.org by gi...@apache.org on 2026/10/17 08:49:02 UTC
(arrow-rs) branch gh-readonly-queue/main/pr-11639-4c8d7086dd4ec5aa97520a3a1a8cb7a866b31f34 created (now 781baa4279)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-11639-4c8d7086dd4ec5aa97520a3a1a8cb7a866b31f34
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
at 781baa4279 perf(parquet): trim bitmap-backed row selections using 64-bit words (#11639)
This branch includes the following new commits:
new 781baa4279 perf(parquet): trim bitmap-backed row selections using 64-bit words (#11639)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
(arrow-rs) 01/01: perf(parquet): trim bitmap-backed row selections using 64-bit words (#11639)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-11639-4c8d7086dd4ec5aa97520a3a1a8cb7a866b31f34
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
commit 781baa42796c5b25c98fa8f0fc7379c16c782df2
Author: Huaijin <ha...@gmail.com>
AuthorDate: Sat Oct 17 08:48:38 2026 +0000
perf(parquet): trim bitmap-backed row selections using 64-bit words (#11639)
# Which issue does this PR close?
Closes #11640
# Rationale for this change
Trimming a bitmap-backed row selection scans trailing unset bits byte by
byte. Long tails of skipped rows add unnecessary selection setup
overhead.
# What changes are included in this PR?
Scan backwards through 64-bit words using `BitChunks`, checking the
masked remainder first. Use `leading_zeros` to locate the final selected
row.
This reuses existing handling of bit offsets and padding while
preserving the fast path for selections that need no trimming.
The implementation was prepared with AI assistance.
# Are these changes tested?
Validated with the existing randomized trim equivalence tests and cursor
tests covering word boundaries, long zero tails, non-zero bit offsets,
and set bits outside the logical slice. All 89 selection tests pass.
# Are there any significant user-facing changes?
No.
---
.../src/arrow/arrow_reader/selection/boolean.rs | 25 +++++++++-------------
1 file changed, 10 insertions(+), 15 deletions(-)
diff --git a/parquet/src/arrow/arrow_reader/selection/boolean.rs b/parquet/src/arrow/arrow_reader/selection/boolean.rs
index e5b698533a..ca21ffe0f4 100644
--- a/parquet/src/arrow/arrow_reader/selection/boolean.rs
+++ b/parquet/src/arrow/arrow_reader/selection/boolean.rs
@@ -250,22 +250,17 @@ pub(super) fn split_off_mask(
(head, tail)
}
-/// Position of the highest set bit in `mask`, scanning bytes from the end.
+/// Position of the highest set bit in `mask`, scanning words from the end.
fn last_set_bit_position(mask: &BooleanBuffer) -> Option<usize> {
- let values = mask.values();
- let offset = mask.offset();
- let end = offset + mask.len();
- for byte_idx in (offset / 8..end.div_ceil(8)).rev() {
- let byte_start = byte_idx * 8;
- let mut byte = values[byte_idx];
- if end - byte_start < 8 {
- byte &= (1u8 << (end - byte_start)) - 1;
- }
- if byte_start < offset {
- byte &= !((1u8 << (offset - byte_start)) - 1);
- }
- if byte != 0 {
- return Some(byte_start + 7 - byte.leading_zeros() as usize - offset);
+ let chunks = mask.bit_chunks();
+ let remainder = chunks.remainder_bits();
+ if remainder != 0 {
+ return Some(chunks.chunk_len() * 64 + 63 - remainder.leading_zeros() as usize);
+ }
+ for i in (0..chunks.chunk_len()).rev() {
+ let word = chunks.chunk(i);
+ if word != 0 {
+ return Some(i * 64 + 63 - word.leading_zeros() as usize);
}
}
None