mightsleep commented on code in PR #11322:
URL: https://github.com/apache/arrow-rs/pull/11322#discussion_r4264391921
##########
arrow-buffer/src/util/bit_util.rs:
##########
@@ -64,6 +73,29 @@ pub fn compress(value: u64, mask: u64) -> u64 {
#[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
{
+ compress_portable(value, mask)
+ }
+}
+
+/// [`compress`] without `pext`, by the number of kept bits `k`:
+///
+/// * `k <= 2`: the two lowest kept bits, tested directly
+/// * `k <= 16`: one step per kept bit
+/// * `k >= 62`: `value` with its at most two dropped bits removed
+/// * otherwise [`compress_bytes`]
+///
+/// The two ends need no loop, so no loop exit to mispredict when `k`
+/// varies from word to word.
+// Always: called once a word, so a call would cost more than a sparse word
+#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
+#[inline(always)]
+fn compress_portable(value: u64, mask: u64) -> u64 {
+ let kept = mask.count_ones();
Review Comment:
Opened #11543, on cores with SVE2 bitperm there is also BEXT (LLVM already
lowers llvm.pext to it there), but the SVE intrinsics are not stable in Rust
yet, so that one has to wait or come with asm!...
##########
arrow-buffer/src/util/bit_util.rs:
##########
@@ -51,8 +52,16 @@ use crate::bit_chunk_iterator::BitChunks;
/// assert_eq!(compress(0b1011_0100, 0b0110_1101), 0b0000_1010);
/// ```
//
-// Replace with `value.compress(mask)` when `uint_gather_scatter_bits` is
-// stabilised: <https://github.com/rust-lang/rust/issues/149069>
+// When `uint_gather_scatter_bits` is stabilised
+// (<https://github.com/rust-lang/rust/issues/149069>), measure
+// `value.extract_bits(mask)` against this before switching. Its portable
+// version runs six shift stages for every mask, with each stage's mask taken
+// from prefix counts of zero bits (Hacker's Delight 7-4, see
+//
<https://github.com/rust-lang/rust/blob/main/library/core/src/num/imp/int_bits.rs>).
+// The fallback here does less work on sparse and dense masks, and on x86 also
+// in between (three stages inside each byte plus one multiply, fewer shifts in
+// total); on big AArch64 cores the six-stage version is faster in that middle
+// band.
Review Comment:
Neoverse-N2 natively, from llvm/llvm-project#227292: pext 5.97 ns whole-word
vs 8.49 ns bytewise, llvm-mca 19 vs 33 cycles on V2. That is the LLVM code, not
this one, so I opened #11542 and linked it from the 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]
