You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "alamb (via GitHub)" <gi...@apache.org> on 2026/09/25 10:14:20 UTC

[I] Improve performance of `filter`kernel (when `pext` instruction is not available) [arrow-rs]

alamb opened a new issue, #11213:
URL: https://github.com/apache/arrow-rs/issues/11213

   ### Is your feature request related to a problem or challenge?
   
   @devanbenz / @Rich-T-kid and others updated the filter kernel to be more efficient 
   - https://github.com/apache/arrow-rs/pull/10136
   
   If the CPU has the [`pext`](https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set#Parallel_bit_deposit_and_extract) instruction, the `compress` function uses that (and is quite speedy on intel CPUs)
   
   ```rust
   #[inline]
   pub fn compress(value: u64, mask: u64) -> u64 {
       #[cfg(all(target_arch = "x86_64", target_feature = "bmi2"))]
       {
           unsafe { std::arch::x86_64::_pext_u64(value, mask) }
       }
      #[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
       {
         // <--------- Fallback code HERE
        }
   }
   ```
   
   However, as @mbutrovich and others pointed out , the fallback seem like it could be improved as it operates one bit at a time
   
   
   
   ### Describe the solution you'd like
   
   Find a better / faster implementation for `compress` on hardware that doesn't support `pext`
   
   ### Describe alternatives you've considered
   
    @mbutrovich suggests https://github.com/apache/arrow-rs/pull/10136/changes#r4094221099
   
   
   > What do you think about having the fallback walk whichever set of bits is smaller? The current loop runs once per set bit in `mask`, so at 9/10 density it takes about 58 iterations per word. Each iteration is 9 instructions on aarch64:
   > 
   > LBB1036_14:
   > 	mov x26, x25
   > 	sub x25, x25, #1
   > 	and x25, x25, x26        ; mask &= mask - 1
   > 	eor x26, x25, x26        ; lowest set bit
   > 	tst x26, x7
   > 	csel x26, xzr, x24, eq
   > 	orr x6, x26, x6
   > 	lsl x24, x24, #1
   > 	cbnz x25, LBB1036_14
   > When more than half the bits are set, removing the dropped bits instead (highest first, so lower positions don't move) takes about 6. The dense loop in the suggestion below compiles to 8 instructions per dropped bit:
   > 
   > LBB1036_16:
   > 	clz x25, x6
   > 	eor x25, x25, #0x3f      ; ilog2
   > 	lsl x25, x5, x25         ; !below
   > 	bic x26, x7, x25         ; value & below
   > 	and x7, x25, x7, lsr #1  ; (value >> 1) & !below
   > 	orr x7, x26, x7
   > 	bics x6, x6, x25         ; dropped &= below
   > 	b.ne LBB1036_16
   > The compiler also reuses one `count_ones` for both the `kept > 32` check and `Packer::push`, so the extra branch costs no extra popcount.
   > 
   > On an Apple M5 Max, `filter_bits` at 9/10 goes from 33.9 us to 3.3 us (-90%) for the lazy, optimized, and sliced cases, and 1/2 improves by 7-11%. The 1/10 through 1/1024 cases move between -5% and +8%, mostly under 3%. `test_compress`, the `arrow-select` filter tests, the `compress` doctest, and clippy all pass. The Parquet caller of `compress` gets the same speedup. I haven't checked whether the `dense` cutoff in `filter_bits` should move now that dense masks are cheaper here.
   > 
   > Suggested change
   >     {
   >         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;
   >         }
   >         result
   >     }
   >     {
   >         let kept = mask.count_ones();
   >         if kept > 32 {
   >             // Dense mask: remove the dropped bits instead, highest first, so
   >             // the loop runs once per clear bit of `mask`
   >             let mut value = value;
   >             let mut dropped = !mask;
   >             while dropped != 0 {
   >                 let below = (1_u64 << dropped.ilog2()) - 1;
   >                 value = (value & below) | ((value >> 1) & !below);
   >                 dropped &= below;
   >             }
   >             return value & (u64::MAX >> (64 - kept));
   >         }
   >         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;
   >         }
   >         result
   >     }
   
   
   
   I had claude code suggest a table based approach from hackers delight: https://github.com/apache/arrow-rs/pull/10136/changes#r4087490049
   
   > Claude flagged this as not very efficient as it is still doing bit at a time
   > 
   > Here is some version it wrote that operates using a precomputed table (citing the [Hacker's Delight](https://www.amazon.com/dp/0321842685?lv=shuf&channelId=500&plpRedirect=mhFallback), one of my favorite books -- I think [@XiangpengHao](https://github.com/XiangpengHao) has a copy!)
   > 
   > Perhaps we can flag this as a potential improvement for follow on work in another ticket
   > 
   > {
   >     // Nibble at a time through a 256 byte table: 16 steps per word
   >     // regardless of how many bits `mask` selects
   >     let mut result = 0_u64;
   >     let mut shift = 0_u32;
   >     let mut i = 0;
   >     while i < 16 {
   >         let m = ((mask >> (i * 4)) & 0xF) as usize;
   >         let v = ((value >> (i * 4)) & 0xF) as usize;
   >         result |= (COMPRESS_NIBBLE[m][v] as u64) << shift;
   >         shift += m.count_ones();
   >         i += 1;
   >     }
   >     result
   > }
   > 
   > /// `COMPRESS_NIBBLE[mask][value]` is `compress(value, mask)` for 4-bit inputs
   > #[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
   > static COMPRESS_NIBBLE: [[u8; 16]; 16] = {
   >     let mut t = [[0u8; 16]; 16];
   >     let mut m = 0;
   >     while m < 16 {
   >         let mut v = 0;
   >         while v < 16 {
   >             let mut r = 0u8;
   >             let mut d = 0;
   >             let mut b = 0;
   >             while b < 4 {
   >                 if m >> b & 1 == 1 {
   >                     r |= ((v >> b & 1) as u8) << d;
   >                     d += 1;
   >                 }
   >                 b += 1;
   >             }
   >             t[m][v] = r;
   >             v += 1;
   >         }
   >         m += 1;
   >     }
   >     t
   > };
   
   
   
   
   
   ### Additional context
   
   _No response_


-- 
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: github-unsubscribe@arrow.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [I] Improve performance of `filter` kernel (when `pext` instruction is not available) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #11213: Improve performance of `filter` kernel (when `pext` instruction is not available)
URL: https://github.com/apache/arrow-rs/issues/11213


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [I] Improve performance of `filter` kernel (when `pext` instruction is not available) [arrow-rs]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #11213:
URL: https://github.com/apache/arrow-rs/issues/11213#issuecomment-5872447831

   Hi @mightsleep  -- I don't quite follow your suggestion -- we should probably open a PR to discuss specifics
   
   Basically the critera I think would be:
   1. Show performance improvements for some cases
   2. No regressions
   
   If you think we need some additional benchmarks, perhaps you can propose a separate PR to add then / explaining what they are covering
   
   
   Thank you for your help
   Andrew


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [I] Improve performance of `filter` kernel (when `pext` instruction is not available) [arrow-rs]

Posted by "sdf-jkl (via GitHub)" <gi...@apache.org>.
sdf-jkl commented on issue #11213:
URL: https://github.com/apache/arrow-rs/issues/11213#issuecomment-5833617015

   > currently nightly-only impl in the [rust stdlib](https://github.com/rust-lang/rust/blob/main/library/core/src/num/imp/int_bits.rs#L103)
   
   +1


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [I] Improve performance of `filter` kernel (when `pext` instruction is not available) [arrow-rs]

Posted by "mightsleep (via GitHub)" <gi...@apache.org>.
mightsleep commented on issue #11213:
URL: https://github.com/apache/arrow-rs/issues/11213#issuecomment-5860320119

   Yes hello,
   I ran the options from this thread, plus the two @jhorstmann linked, through the whole `filter_bits_compress` loop (compress plus the packer) on random, clustered and periodic masks. Default target features: no BMI2, and on x86 no POPCNT.
   
   Two things first. On random masks the current loop spends most of its time on its exit, not its work: the kept count per word is random, so the exit mispredicts almost every time. And the existing bench repeats one 1024-word mask, which a recent core memorises, so its random cases run about twice as fast as fresh data does. I spent a while benchmarking the branch predictor before noticing.
   
   Against the current loop, Zen 5, above 1 is faster:
   
   | mask | smaller side | nibble LUT | `extract_bits` | Arrow C++ | this |
   |---|---|---|---|---|---|
   | random, 1/64 | 0.86 | 0.43 | 0.58 | 0.50 | 2.8 |
   | random, 1/2 | 0.72 | 1.69 | 2.30 | 1.77 | 3.0 |
   | random, 15/16 | 2.8 | 2.5 | 3.3 | 2.7 | 4.2 |
   | runs of 4096, 1/2 | 8.0 | 1.2 | 1.6 | 9.4 | 7.6 |
   | every 10th row | 0.99 | 0.28 | 0.41 | 0.34 | 1.00 |
   
   Each of them loses to the loop somewhere. "This" dispatches on `k = mask.count_ones()`, which the packer needs anyway. `k <= 2`: the lowest set bit and the one above it, tested directly, so no loop and no exit to mispredict. `k <= 16`: the current loop, the cheapest thing going when the data make its branches predictable (clustered or periodic rows). `k >= 62`: a full word returns `value`, otherwise the at most two dropped bits are removed highest first, branch-free. The rest goes to `compress_bytes`, constant time and table-free. Each kept bit has to move down by the number of dropped bits below it; write that distance in binary, and round `i` moves every bit whose distance has bit `i` set by `2^i`. This is the network of `core`'s `extract_bits`, but run within each byte, where distances are below 8: three rounds instead of six, on all eight bytes at once, every shift masked so no bit crosses into its neighbour. That leaves each byte's kept bits at its bottom. A popcount per byte
  multiplied by `0x0101..01` gives every byte's offset in one go (the product's byte `j` is the sum of the counts below it), and eight independent shifts join the bytes. About 7 ns a word flat, against 10 to 15 for the full network, which spends its three long rounds moving whole bytes that one multiply can place. About 55 lines. The existing test draws uniform masks only (about 32 kept bits), so it would reach one of the four paths; the new one covers every mask with at most two kept or two dropped bits, random masks at every density, and every popcount.
   
   GitHub runners, 4 Mi-row masks of fresh data, against main (two interleaved runs each agree within 1 %):
   
   | mask | Neoverse-N2 | Xeon 8573C |
   |---|---|---|
   | random, 1/64 | 1.26 | 1.23 |
   | random, 1/16 | 1.00 | 0.97 |
   | random, 1/2 | 3.6 | 2.7 |
   | random, 15/16 | 5.8 | 3.7 |
   | runs of 4096, 1/2 | 16.4 | 10.1 |
   
   The 0.97 is the one loss I could not remove: x86 without POPCNT, where a software popcount now sits in front of every word.
   
   Further gains exist, but they change `filter_bits_compress` rather than `compress`, so they would be a follow-up rather than part of this:
   
   - count ahead: the masks are all in memory, so the popcounts of a block can be computed in one pass that vectorises even on SSE2, which takes  the software popcount (the 0.97 above) off the per-word path; it needs a `compress` that takes the count;
   - choose per call, not per word: whether the loop or the constant-time kernel wins for 3 to 16 kept bits depends on whether the branches are predictable, which one word cannot tell but the variation of the counts across a batch can.
   
   If the direction is fine I'll open a PR, with the larger bench cases as its first commit.
   


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [I] Improve performance of `filter` kernel (when `pext` instruction is not available) [arrow-rs]

Posted by "jhorstmann (via GitHub)" <gi...@apache.org>.
jhorstmann commented on issue #11213:
URL: https://github.com/apache/arrow-rs/issues/11213#issuecomment-5832430356

   Also worth looking at the currently nightly-only impl in the [rust stdlib](https://github.com/rust-lang/rust/blob/main/library/core/src/num/imp/int_bits.rs#L103) and the [impl in arrow cpp](https://github.com/apache/arrow/blob/3ad410b7b1a2d3712e2d6a55d905a7035d026cae/cpp/src/parquet/level_conversion_inc.h#L237).


-- 
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: github-unsubscribe@arrow.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org