mbutrovich commented on code in PR #11818:
URL: https://github.com/apache/arrow-rs/pull/11818#discussion_r4443565825
##########
arrow-buffer/src/util/bit_chunk_iterator.rs:
##########
@@ -168,10 +170,46 @@ impl<'a> UnalignedBitChunk<'a> {
/// Counts the number of ones
pub fn count_ones(&self) -> usize {
- self.iter().map(|x| x.count_ones() as usize).sum()
+ let edges = self.prefix.into_iter().chain(self.suffix);
+ edges.map(|x| x.count_ones() as usize).sum::<usize>() +
count_ones_words(self.chunks)
}
}
+#[cfg(not(target_arch = "aarch64"))]
+fn count_ones_words(words: &[u64]) -> usize {
+ words.iter().map(|x| x.count_ones() as usize).sum()
+}
+
+/// Summing four byte popcounts in `u8` lanes before widening lets LLVM emit
one
+/// widening per 64 bytes. A `u64::count_ones` sum widens every 16 bytes. On
x86
+/// the `u64` sum measured faster (#11776), so this is only used on aarch64.
+#[cfg(target_arch = "aarch64")]
+fn count_ones_words(words: &[u64]) -> usize {
Review Comment:
> Also, there was not really a noticable performance improvement in the
boolean_array benchmarks, I only ran through a small amount but noticing the
perf didn't really change I exited early lol
Thanks for digging into the codegen. The 64-bit cases don't reach this loop.
A buffer of at most 8 bytes goes into `prefix`
([bit_chunk_iterator.rs](https://github.com/apache/arrow-rs/blob/110c2e8254c12c7a2ed03a55a3328df86ec92306/arrow-buffer/src/util/bit_chunk_iterator.rs#L63-L75)),
so `count_ones_words` gets an empty slice. Only the 65536-bit cases run the
64-byte loop.
> The new version has 8 lanes in one register, so a single uaddlv.8h does it.
The 13-instruction reduction runs once per 2047 blocks, so in the loop
`uadalp` saves one instruction out of 14 per block. I'd keep the autovectorized
version because it needs no `unsafe`, and it compiles to the same loop from
LLVM 20 to 23.
--
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]
