Rich-T-kid commented on code in PR #11918:
URL: https://github.com/apache/arrow-rs/pull/11918#discussion_r4415673198
##########
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:
Thanks for digging into this. I tried the shared packer as suggested,
including the loop around `compress` and `#[inline(always)]` on
`filter_bits_compress`, and added the Boolean `filter_kernels` cases in a
separate commit.
On Neoverse-V2, the shared packer made the regular Boolean path worse: the
80% cases regressed by about 19% without nulls and 22% with nulls, while the
10% cases regressed by about 5-6%
([run](https://github.com/apache/arrow-rs/pull/11918#issuecomment-6502693642)).
I also tried keeping the shared packer but restoring `#[inline(never)]`; that
was slightly worse again, with 21-24% regressions at 80% and 8-11% at 10%
([run](https://github.com/apache/arrow-rs/pull/11918#issuecomment-6503338040)).
I reverted the shared-packer change. The final-head run is back to roughly
flat at 80% (+2% without nulls, flat with nulls), while preserving the sparse
gains
([run](https://github.com/apache/arrow-rs/pull/11918#issuecomment-6503625387)).
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.
--
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]
