haohuaijin opened a new pull request, #10446:
URL: https://github.com/apache/arrow-rs/pull/10446
# Which issue does this PR close?
- Closes #10425.
> [!IMPORTANT]
> **Draft: stacked on #10444.** This branch is based on that PR, so the diff
here currently shows both commits. The optimization depends on the fix in
#10444 — without it the mask tail gets corrupted and the tests below fail. Once
#10444 merges I'll rebase onto `main` and this reduces to the single
`algebra.rs` commit.
# Rationale for this change
When two mask-backed `RowSelection`s have different lengths,
`intersect_masks`/`union_masks` allocate twice: once for the bitwise result
over the common prefix, then again for a `BooleanBufferBuilder` that appends
the prefix and the longer side's tail — copying both.
# What changes are included in this PR?
Copy the longer mask once into a `MutableBuffer` and apply `&=`/`|=` in
place over the common prefix via `bit_util::apply_bitwise_binary_op`. The tail
is already in the right place, so it needs no copy at all.
Neither the mask offsets nor the prefix length are assumed to be byte
aligned — masks reaching this path may carry a non-zero bit offset from
`BooleanBuffer::slice`, and the prefix may end mid byte. The copy keeps the
longer mask's sub-byte offset instead of re-aligning it, so it stays a plain
byte copy, and that offset is carried over to the result.
# Are these changes tested?
Yes — `test_uneven_masks_with_offsets` sweeps offsets `{0,1,5,8,13,64,67}` ×
`{0,1,3,8,60,64,70}` against several length pairs, and `test_uneven_masks_fuzz`
runs 200 randomized rounds. Both compare against a bit-by-bit reference
implementation. `cargo test -p parquet --all-features` passes (1284 tests);
clippy and fmt clean.
Criterion over mask-backed `RowSelection::intersection`/`union` at ~1/3
density:
| case | before | after | change |
| --- | --- | --- | --- |
| intersect 3M / 2M | 16.60 µs | 12.96 µs | −21.9% |
| union 3M / 2M | 16.57 µs | 13.12 µs | −20.8% |
| intersect 3M / 3M−1 | 20.22 µs | 16.51 µs | −18.3% |
| union 3M / 3M−1 | 20.19 µs | 16.66 µs | −17.5% |
| intersect 100K / 1K | 509 ns | 278 ns | −45.4% |
| union 100K / 1K | 525 ns | 270 ns | −48.6% |
Measured with an ad-hoc bench harness rather than a committed one, since
there's no existing bench covering mask-backed selections — `row_selector.rs`
builds its inputs with `from_filters`, which is selector-backed and doesn't
reach this path. Happy to add a permanent bench if you'd like one.
The gain grows with the tail, which the old code copied through the builder
for no reason.
# Are there any user-facing changes?
No API changes. `intersect_masks`/`union_masks` are `pub(super)`; the
observable behaviour of `RowSelection::intersection`/`union` is unchanged.
--
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]
