Rich-T-kid commented on code in PR #11055:
URL: https://github.com/apache/arrow-rs/pull/11055#discussion_r3983383730
##########
arrow-select/src/filter.rs:
##########
@@ -676,6 +677,79 @@ where
RunArray::try_new(&run_ends, &values)
}
+/// Extract bits from `src` at positions where `filter` has a 1, packed
densely.
+///
+/// Processes 64 filter bits per iteration: one u64 load from each buffer, then
+/// software PEXT to scatter the selected source bits. This reduces source
reads
+/// from O(selected_count) byte loads to O(filter_len/64) u64 loads.
+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 out_word = 0u64;
+ let mut out_bits = 0usize; // bits written into `out_word` so far (0..=63)
+
+ macro_rules! push_chunk {
+ ($compressed:expr, $n_set:expr) => {{
Review Comment:
I think we should just use a nested function here
##########
arrow-select/src/filter.rs:
##########
@@ -684,22 +758,20 @@ fn filter_bits(buffer: &BooleanBuffer, predicate:
&FilterPredicate) -> Buffer {
match &predicate.strategy {
IterationStrategy::IndexIterator => {
- let bits =
- // SAFETY: IndexIterator uses the filter predicate to derive
indices
- IndexIterator::new(&predicate.filter,
predicate.count).map(|src_idx| unsafe {
- bit_util::get_bit_raw(buffer.values().as_ptr(), src_idx +
offset)
- });
-
- // SAFETY: `IndexIterator` reports its size correctly
- unsafe { MutableBuffer::from_trusted_len_iter_bool(bits).into() }
+ gather_bits(buffer, predicate.filter.values(), predicate.count)
}
IterationStrategy::Indices(indices) => {
- // SAFETY: indices were derived from the filter predicate
- let bits = indices.iter().map(|src_idx| unsafe {
- bit_util::get_bit_raw(buffer.values().as_ptr(), *src_idx +
offset)
- });
- // SAFETY: `Vec::iter()` reports its size correctly
- unsafe { MutableBuffer::from_trusted_len_iter_bool(bits).into() }
+ // gather_bits scans every filter chunk (filter_len/64 u64 loads).
+ // For very sparse selections the precomputed Vec is smaller and
cheaper to walk.
+ // Threshold: switch when the selected count exceeds one u64 per
filter chunk.
Review Comment:
dont need
--
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]
