mbutrovich commented on code in PR #11322: URL: https://github.com/apache/arrow-rs/pull/11322#discussion_r4264100091
########## 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: > on big AArch64 cores the six-stage version is faster in that middle band. Do you have numbers for this you could post here? The Neoverse-N2 tables in the description and the Neoverse-V2 bot runs compare this PR with `main`. The only comparison with the six-stage network I found is the `extract_bits` column in https://github.com/apache/arrow-rs/issues/11213#issuecomment-5860320119, which is from Zen 5. Which cores did you see it on? If it holds on Neoverse, should the aarch64 build use the six-stage network for 17 to 61 kept bits? It needs no nightly API, since HD 7-4 is plain shifts and masks. If that belongs in a separate PR, could you open an issue for it and reference it from this comment? Then the claim has data behind it, and the issue tracks the possible gain. ########## 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: What do you think about opening an issue for the block-level popcount idea from the description and linking it here? The sparse-mask cost stays on AArch64 even with `-C target-cpu=native`, because the `pext` path only exists for x86-64 with BMI2 ([`compress`](https://github.com/apache/arrow-rs/blob/27172a8d476fb6d01b5ed936b4a8e1f49b173ea0/arrow-buffer/src/util/bit_util.rs#L66-L78)). On the Neoverse-V2 bot run (https://github.com/apache/arrow-rs/pull/11322#issuecomment-6040082386), `filter_bits batches (random, kept 1/16)` went from 651.3 us to 695.8 us. An issue gives that case an owner after this merges. -- 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]
