Rich-T-kid commented on code in PR #11055:
URL: https://github.com/apache/arrow-rs/pull/11055#discussion_r4120754633
##########
arrow-buffer/src/util/bit_util.rs:
##########
@@ -64,23 +64,113 @@ pub fn compress(value: u64, mask: u64) -> u64 {
#[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
{
- let mut mask = mask;
- let mut result = 0_u64;
- let mut dest_bit = 1_u64;
- while mask != 0 {
- // Clear the lowest set bit; the loop-carried dependency is only
- // this two-operation chain, everything else hangs off it
- let rest = mask & (mask - 1);
- let lowest = mask ^ rest;
- let keep = ((value & lowest) != 0) as u64;
- result |= dest_bit & keep.wrapping_neg();
- dest_bit <<= 1;
- mask = rest;
+ compress_with_count(value, mask, mask.count_ones())
+ }
+}
+
+/// Precomputed PEXT for all 4-bit mask/value combinations (256 bytes, one
cache line).
+/// `NIBBLE_PEXT[mask_nibble][value_nibble]` = bits of `value_nibble` at
positions set
+/// in `mask_nibble`, packed into the low bits of the result.
+const NIBBLE_PEXT: [[u8; 16]; 16] = {
+ let mut table = [[0u8; 16]; 16];
+ let mut mask_nibble = 0usize;
+ while mask_nibble < 16 {
+ let mut value_nibble = 0usize;
+ while value_nibble < 16 {
+ let mut packed = 0u8;
+ let mut output_bit = 0u8;
+ let mut remaining_mask = mask_nibble as u8;
+ while remaining_mask != 0 {
+ let selected_bit = remaining_mask &
remaining_mask.wrapping_neg();
+ if value_nibble as u8 & selected_bit != 0 {
+ packed |= 1 << output_bit;
+ }
+ output_bit += 1;
+ remaining_mask &= remaining_mask - 1;
+ }
+ table[mask_nibble][value_nibble] = packed;
+ value_nibble += 1;
+ }
+ mask_nibble += 1;
+ }
+ table
+};
Review Comment:
ill point out that this idea was heavily influenced by claude, so a second
set of eyes would be appreciated
##########
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())
{
Review Comment:
@sdf-jkl mhm I cant seem to get similar results to what you did on your
branch. everything was pretty much within noise. maybe you can take a closer
look
##########
arrow-select/src/filter.rs:
##########
@@ -756,11 +810,14 @@ fn filter_bits_compress(buffer: &BooleanBuffer,
predicate: &FilterPredicate) ->
}
impl Packer {
+ /// Computes `mask.count_ones()` once and reuses it for both the
+ /// compress dispatch and the bit-offset bookkeeping.
Review Comment:
✂️
--
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]
