mbutrovich commented on code in PR #11918:
URL: https://github.com/apache/arrow-rs/pull/11918#discussion_r4446166932
##########
arrow-select/src/filter.rs:
##########
@@ -801,80 +801,150 @@ fn filter_bits_strategy(buffer: &BooleanBuffer,
predicate: &FilterPredicate) ->
}
/// Filter the packed bitmask `buffer` with `predicate` by extracting the kept
-/// bits of each 64-bit word with [`bit_util::compress`] (`pext`)
-///
-/// Not inlined: within `filter_array` the packing state spills to the stack
+/// bits of each 64-bit word with [`bit_util::compress`] (`pext`).
#[inline(never)]
-fn filter_bits_compress(buffer: &BooleanBuffer, predicate: &FilterPredicate)
-> Buffer {
+pub(crate) fn filter_bits_compress(
+ buffer: &BooleanBuffer,
+ predicate: &FilterPredicate,
+ mut append: impl FnMut(u64, usize),
+) {
+ filter_bits_compress_impl::<false>(buffer, None, predicate, |word, _,
count| {
+ append(word, count)
+ })
+}
+
+/// Filters two packed bitmaps using the same predicate and mask traversal.
+#[inline(never)]
+pub(crate) fn filter_bits_compress_pair(
+ first: &BooleanBuffer,
+ second: &BooleanBuffer,
+ predicate: &FilterPredicate,
+ mut append: impl FnMut(u64, u64, usize),
+) {
+ filter_bits_compress_impl::<true>(first, Some(second), predicate, |first,
second, count| {
+ append(first, second.unwrap(), count)
+ })
+}
+
+#[inline(always)]
+fn filter_bits_compress_impl<const PAIR: bool>(
+ first: &BooleanBuffer,
+ second: Option<&BooleanBuffer>,
+ predicate: &FilterPredicate,
+ mut append: impl FnMut(u64, Option<u64>, usize),
+) {
/// Packs the bits extracted from successive words into the low `filled`
- /// bits of `current`; once complete it is written at `idx` and restarts
- /// from the bits that did not fit
+ /// bits of `current`.
+ #[derive(Default)]
struct Packer {
- ptr: *mut u64,
- idx: usize,
+ /// Bits waiting to be written.
current: u64,
+ /// Number of populated low bits in `current`.
filled: u32,
}
impl Packer {
#[inline(always)]
- fn push(&mut self, values: u64, mask: u64) {
- let bits = bit_util::compress(values, mask);
+ fn push(&mut self, bits: u64, count: u32) -> Option<u64> {
self.current |= bits << self.filled;
- let total = self.filled + mask.count_ones();
+ let total = self.filled + count;
if total < 64 {
self.filled = total;
- } else {
- // SAFETY: `count` is the number of set bits in the filter, so
- // at most `count / 64` words are ever completed and the
- // buffer holds `count / 64 + 1`
- unsafe { self.ptr.add(self.idx).write(self.current) };
- self.idx += 1;
- // `bits >> (64 - filled)`, written so that `filled == 0`
- // shifts everything out
- self.current = (bits >> 1) >> (63 - self.filled);
- self.filled = total - 64;
+ return None;
}
+
+ let complete = self.current;
+ // `bits >> (64 - filled)`, written so that `filled == 0`
+ // shifts everything out
+ self.current = (bits >> 1) >> (63 - self.filled);
+ self.filled = total - 64;
+ Some(complete)
Review Comment:
> The 10% cases are still about 7-8% slower, so that part remains
unresolved, but the shared packer does not appear to be the fix on Neoverse-V2.
Should we go back to
[`176af76`](https://github.com/apache/arrow-rs/commit/176af76510f24cd26f45a7d6ad6730271adc7fcd)?
It's what I asked for in my [first
comment](https://github.com/apache/arrow-rs/pull/11918#discussion_r4380932889):
a `pub(crate)`
[`Packer`](https://github.com/apache/arrow-rs/blob/176af76510f24cd26f45a7d6ad6730271adc7fcd/arrow-select/src/filter.rs#L808-L840)
whose `push(values, mask)` returns `Option<u64>`, with `filter_bits_compress`
still writing each completed word itself. The bot had it flat at 10% and 80%,
with the same sparse gains as the head:
| run | commit | 0.1% kept, 10% nulls | 10% kept, no nulls | 10% kept, 10%
nulls | 80% kept, 10% nulls |
|---|---|---|---|---|---|
|
[run](https://github.com/apache/arrow-rs/pull/11918#issuecomment-6426044605) |
`176af76` | 2.08x faster | 2% faster | 1% faster | 2% faster |
|
[run](https://github.com/apache/arrow-rs/pull/11918#issuecomment-6426047002) |
`176af76` | 2.04x faster | 1% faster | flat | 2% faster |
|
[run](https://github.com/apache/arrow-rs/pull/11918#issuecomment-6503625387) |
`f059b1e` (head) | 2.14x faster | 7% slower | 8% slower | flat |
All eight runs since `filter_bits_compress` started emitting words through a
callback (`9b48802` onward, including your two shared-packer variants) have the
10% rows 5% to 11% slower. All seven runs before that are within 2% of the
merge-base. My shared-packer suggestion above also emits through a callback, so
I'd drop it.
Was the version from my [#11732
comment](https://github.com/apache/arrow-rs/pull/11732#issuecomment-6325226430)
tried, with no packer at all? It calls `values.append_word(compress(chunk,
mask), k)` and `nulls.append_word(...)` once per non-empty mask word, and
`append_word` handles the bit offset. Every commit with a bot run here has a
packer, so we don't know how it compares. It would leave the `filter` kernel
unchanged, so the regular `filter` couldn't regress. Could you run it on the
bot next to `176af76`?
I also had the cause wrong in my last comment. `176af76`'s `push` also
returns `Option<u64>`, and its loop compiles to the same code as the
merge-base: a branch on `total < 64`, the carry computed only when a word
completes, and `idx` in a register. At the head, the path where no word
completes still computes the carry on every non-zero mask word and picks it
with `csel`. A completed word then loads `ptr` and `idx` through the closure's
captures and stores `idx` back. This is a release build of `arrow-select` on
aarch64:
```text
lsr x8, x23, #1 ; carry, on every non-zero mask word
eor w10, w10, #0x3f
lsr x8, x8, x10
subs w10, w20, #64
cmp w20, #63
csel w10, w10, w20, hi ; filled
csel x8, x8, x21, hi ; current
cmp w20, #64
b.lo ... ; no word completed
ldr x20, [x11] ; ptr, through the closure
ldr x22, [x9] ; idx, through the closure
str x21, [x20, x22, lsl #3]
ldr x20, [x9]
add x20, x20, #1
str x20, [x9] ; idx stored back
```
With `--target x86_64-unknown-linux-gnu -C target-cpu=x86-64-v3`, the head
has the same shape with `cmovb` and `inc qword ptr [rbp]`, and `176af76` keeps
the branch and `inc rax`.
This reaches beyond Boolean columns, because `filter_nulls` sends the null
buffer of every nullable type through `filter_bits`
([filter.rs](https://github.com/apache/arrow-rs/blob/f059b1ecbb148409f813fe79189252c138b4bac5/arrow-select/src/filter.rs#L580)).
`176af76` hasn't had the `filter_kernels` run my first comment asked for,
since `push` returning words changes the loop that `filter_bits_compress` was
tuned around. Could you put the Boolean `filter_kernels` cases in a commit
before it and run `filter_kernels` against that commit? Today they're in the
last commit, so the merge-base has no Boolean rows to compare. The bot's
[`baseline:
ref:`](https://github.com/adriangb/datafusion-benchmarking#comparing-specific-branches-or-commits)
option does this:
run benchmark filter_kernels
```yaml
baseline:
ref: <SHA of the benchmark commit>
```
--
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]
