mbutrovich commented on PR #11818: URL: https://github.com/apache/arrow-rs/pull/11818#issuecomment-6511109586
Thanks @andygrove. I switched the tail to count words. I think it reads better, and it gets a bit of speedup. > A 64-bit input is a single word, so it goes entirely through the byte loop and loses its single `popcnt`. That's my best explanation for the 64-bit regression above. A 64-bit input doesn't reach `count_ones_words`. `UnalignedBitChunk::new` puts a buffer of at most 8 bytes in `prefix` ([bit_chunk_iterator.rs](https://github.com/apache/arrow-rs/blob/a3f07846a55fd6e412eb9b0cc12788e709288953/arrow-buffer/src/util/bit_chunk_iterator.rs#L63-L75)), so `chunks` is empty. The 1024-bit and 65536-bit arrays in the bench are aligned and a whole number of 64-byte chunks, so their remainder is empty too. None of the existing `true_count` cases run the tail, so I read the 64-bit and 1024-bit differences as code layout. On an M5 Max, rerunning the PR head against its own baseline moved the 64-bit cases by 3.5%. The tail runs when the aligned middle isn't a multiple of 8 words. I added 448-bit (7 tail words, no full chunk) and 960-bit (one chunk and 7 tail words) cases to the bench. Per word, the byte tail compiles to `cnt.8b`, two `tbl`, and four `uaddw.2d`. The word tail compiles to `cnt.16b`, `udot`, and `uadalp` per two words. These are the `all_true` cases on an M5 Max with the default bench profile: | bits | byte tail | word tail | change | |---|---|---|---| | 448 | 5.67 ns | 4.50 ns | -20.5% | | 960 | 6.63 ns | 5.12 ns | -22.4% | The 64, 1024, and 65536-bit cases moved by less than 3.1%. With `-C llvm-args=-align-all-functions=7 -C llvm-args=-align-all-nofallthru-blocks=7`, the 448-bit and 960-bit cases were 26.5% and 24.4% faster. I split with `words.as_chunks::<8>()` instead of slicing `words` by `remainder.len() / 8`, so the tail comes from the split. Both compile to the same loops. > one case with random bytes would guard against a future change to the lane indexing. I added a seeded random input to `test_unaligned_bit_chunk_count_ones`. Changing `chunk[16 + lane]` to `chunk[lane]` fails on the random input and passes on the uniform ones. -- 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]
