mbutrovich commented on code in PR #11918:
URL: https://github.com/apache/arrow-rs/pull/11918#discussion_r4462556460
##########
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:
> Should we go back to
[`176af76`](https://github.com/apache/arrow-rs/commit/176af76510f24cd26f45a7d6ad6730271adc7fcd)?
Thanks, the head's `filter_bits_compress` now matches `176af76`, apart from
the `uses_sparse_indices` helper and some comment edits.
> Could you put the Boolean `filter_kernels` cases in a commit before it and
run `filter_kernels` against that commit?
Could we get a run against the merge-base with only the benchmark commit on
top? The bench commit `f059b1e` still comes after `4d091cd`, so its tree
already has the callback version of
[`filter.rs`](https://github.com/apache/arrow-rs/blob/f059b1ecbb148409f813fe79189252c138b4bac5/arrow-select/src/filter.rs#L935-L952).
That's the version that was 5% to 11% slower at 10%. As I read it, the
[filter-kernel
run](https://github.com/apache/arrow-rs/pull/11918#issuecomment-6614858375) in
the description, and the 23% at `kept 1/2` with `x86-64-v3`
([run](https://github.com/apache/arrow-rs/pull/11918#issuecomment-6614584708)),
compare the head against that version rather than against `main`. A branch with
`f059b1e`'s benchmark change cherry-picked onto `b65bab9` would give the bot a
`baseline: ref:` with no filter changes.
Could that run also drop `BENCH_FILTER`, or include the nullable primitive
and string cases? `filter_nulls` sends every nullable type's null buffer
through `filter_bits`, so `^filter context boolean` covers only one of the
types this change reaches.
> Was the version from my [#11732
comment](https://github.com/apache/arrow-rs/pull/11732#issuecomment-6325226430)
tried, with no packer at all?
Is there a bot run for this one? The coalescer now goes through `Packer` and
calls `append_word(_, 64)` once per completed word. That probably wins over one
`append_word` per non-empty mask word, but no run here compares them.
--
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]
