mbutrovich commented on code in PR #11055:
URL: https://github.com/apache/arrow-rs/pull/11055#discussion_r4299229146
##########
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
Since this branch last merged `main`, #11322 replaced the portable fallback
of `compress` with
[`compress_portable`](https://github.com/apache/arrow-rs/blob/8f4bb0caa723c9536e59669418d475a6b544d2e9/arrow-buffer/src/util/bit_util.rs#L80-L135).
The bot runs since October 7 compare against `6b34163`, which is before
#11322, so they show the gain over the old bit loop and not over what's on
`main` now.
To compare the two, I took current `main` (`8f4bb0c`) and changed only
`compress` to call this branch's `compress_with_count` (bit loop at 8 or fewer
kept bits, nibble table above). Then I ran the `filter_bits` bench against
`main` on an Apple M5 Max. That's aarch64, so there's no `pext`. I built with
`lto = true` and `codegen-units = 1`. A positive change means the nibble table
is slower:
| case | change vs `main` |
|---|---|
| `filter_bits (slices, kept 9/10)` | +104% |
| `filter_bits (indices, kept 1/2)` | +108% |
| `filter_bits (indices, kept 1/10)` | +27% |
| `filter_bits (indices, kept 1/64)` | +13% |
| `filter_bits (indices, kept 1/1024)` | -2% |
| `filter_bits batches (random, kept 1/64)` | +77% |
| `filter_bits batches (random, kept 1/16)` | +8% |
| `filter_bits batches (random, kept 1/2)` | +101% |
| `filter_bits batches (random, kept 15/16)` | +88% |
| `filter_bits batches (runs of 512, kept 1/2)` | +199% |
| `filter_bits batches (runs of 512, kept 7/8)` | +228% |
The best case across all 35 benchmarks was 5% faster, and a run without LTO
gave the same picture. Should we drop the `bit_util.rs` changes, including the
new public `compress_with_count`, and the `Packer::push` change that calls it?
--
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]
