haohuaijin commented on code in PR #10968:
URL: https://github.com/apache/arrow-rs/pull/10968#discussion_r4100158131
##########
parquet/src/arrow/arrow_reader/selection/algebra.rs:
##########
@@ -430,11 +442,86 @@ fn and_then_masks(mask: &BooleanBuffer, other:
&BooleanBuffer) -> BooleanBuffer
builder.finish()
}
+/// Checks the length and selectivity thresholds for dense expansion.
+#[inline]
+fn should_use_dense_mask(mask_len: usize, selected_count: usize,
other_true_count: usize) -> bool {
+ mask_len >= AND_THEN_DENSE_MASK_MIN_LEN
+ && mask_len - selected_count <=
mask_len.div_ceil(AND_THEN_DENSE_MASK_MAX_DROPPED_FRACTION)
+ && other_true_count >= selected_count /
AND_THEN_DENSE_MASK_MIN_INNER_FRACTION
+}
+
+/// Scatters the next `mask_word.count_ones()` bits of `other` into each mask
word.
+/// Requires `other.len() == mask.count_set_bits()`.
+#[inline(never)]
+fn and_then_dense_masks(mask: &BooleanBuffer, other: &BooleanBuffer) ->
BooleanBuffer {
+ let mut other_chunks = other.bit_chunks().iter_padded();
+ let mut other_remaining = other.len();
+ let mut pending = 0_u128;
+ let mut pending_len = 0;
+ let mut output = MutableBuffer::with_capacity(mask.len().div_ceil(8));
+
+ for mask_word in mask
+ .bit_chunks()
+ .iter_padded()
+ .take(mask.len().div_ceil(64))
+ {
+ let selected = mask_word.count_ones() as usize;
+ while pending_len < selected {
+ let chunk = other_chunks
+ .next()
+ .expect("validated other length matches selected row count");
+ let chunk_len = other_remaining.min(64);
+ pending |= (chunk as u128) << pending_len;
+ pending_len += chunk_len;
+ other_remaining -= chunk_len;
+ }
+
+ let values = pending as u64;
+ output.extend_from_slice(&deposit_u64(values,
mask_word).to_le_bytes());
+ pending >>= selected;
+ pending_len -= selected;
+ }
+
+ debug_assert_eq!(other_remaining, 0);
+ debug_assert_eq!(pending_len, 0);
+ output.truncate(mask.len().div_ceil(8));
+ BooleanBuffer::new(output.into(), 0, mask.len())
+}
+
+/// Software `pdep`: scatters the lowest `mask.count_ones()` bits of `values`
Review Comment:
yes, we can. maybe we could also use BMI2's
`PDEP`([_pdep_u64](https://doc.rust-lang.org/core/arch/x86_64/fn._pdep_u64.html))
in a follow-up to improve this function's performance.
--
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]
