Rich-T-kid commented on code in PR #11055:
URL: https://github.com/apache/arrow-rs/pull/11055#discussion_r4011873007
##########
arrow-select/src/filter.rs:
##########
@@ -676,6 +677,74 @@ where
RunArray::try_new(&run_ends, &values)
}
+/// Extract bits from `src` at positions where `filter` has a 1, packed
densely,
+/// processing 64 filter bits at a time
+fn gather_bits(src: &BooleanBuffer, filter: &BooleanBuffer, count: usize) ->
Buffer {
+ let filter_chunks = filter.bit_chunks();
+ let src_chunks = BitChunks::new(src.values(), src.offset(), filter.len());
+
+ let out_u64s = bit_util::ceil(count, 64);
+ let mut out: Vec<u64> = Vec::with_capacity(out_u64s);
+ let mut current_word = 0u64;
+ let mut bits_filled = 0usize;
+
+ // Appends `bits_selected` densely-packed bits from `selected_bits` into
the output word stream.
+ let mut push_chunk = |selected_bits: u64, bits_selected: usize| {
+ let bits_remaining = 64 - bits_filled;
+ current_word |= selected_bits << bits_filled;
+ if bits_selected < bits_remaining {
+ bits_filled += bits_selected;
+ } else {
+ // Current word is full; carry the overflow into the next word.
+ out.push(current_word);
+ current_word = if bits_selected == bits_remaining {
+ 0
+ } else {
+ selected_bits >> bits_remaining
+ };
+ bits_filled = bits_selected - bits_remaining;
+ }
+ };
+
+ for (filter_word, src_word) in filter_chunks.iter().zip(src_chunks.iter())
{
+ if filter_word == 0 {
+ continue;
+ }
+ let n_set = filter_word.count_ones() as usize;
+ push_chunk(pext64(src_word, filter_word), n_set);
+ }
+
+ let rem_filter = filter_chunks.remainder_bits();
+ if rem_filter != 0 {
+ let n_set = rem_filter.count_ones() as usize;
+ push_chunk(pext64(src_chunks.remainder_bits(), rem_filter), n_set);
+ }
+
+ if bits_filled > 0 {
+ out.push(current_word);
+ }
+
+ let mut buf: MutableBuffer = out.into();
+ buf.truncate(bit_util::ceil(count, 8));
+ buf.into()
+}
+
+/// Collects the bits of `val` wherever `mask` is 1, packed into the low bits
of the result.
+#[inline(always)]
+fn pext64(val: u64, mut mask: u64) -> u64 {
Review Comment:
yea I think moving this out so it can be re-used is a good idea. Would be
nice to see how much of a speed up parquet gets from this as well
--
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]
