andygrove commented on PR #11818: URL: https://github.com/apache/arrow-rs/pull/11818#issuecomment-6481787819
I relied on AI to help with this review, and I ran the checks below myself. Please push back if I've got something wrong. Thanks @mbutrovich. The approach looks right to me. **Correctness** - A `u8` lane sums at most four byte popcounts (4 × 8 = 32), so it can't overflow. `CHUNKS_PER_FLUSH = u16::MAX / 32 = 2047` keeps each `u16` lane at or below 65504, so one flush per 2047 chunks is safe. - Counting `prefix`/`suffix` separately from `chunks` covers the same words as `iter()`. - I checked that `test_unaligned_bit_chunk_count_ones` actually guards the flush boundary. I bumped `CHUNKS_PER_FLUSH` by one and the test failed in debug (add overflow) and in release (it returned 0 instead of 1048576), thanks to the 131_008/131_072/131_136-byte sizes. **Benchmark on Apple Silicon** `boolean_array` `true_count`, compared against the PR's parent commit: | Case | Change | |---|---| | 65536 bits, no nulls | ~24% faster | | 1024 bits, no nulls | ~4% faster | | 64 bits, no nulls (all_true, all_false, mixed_early) | ~5% **slower** (5.69 → 5.96 ns) | **Suggestion: count the tail in words, not bytes** `count_ones_words` counts the remainder after the 64-byte chunks one byte at a time. `words` is always a whole number of `u64`s, so the remainder is at most 7 words. 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. I tried this instead: ```rust let tail = &words[words.len() - remainder.len() / 8..]; total + tail.iter().map(|w| w.count_ones() as usize).sum::<usize>() ``` `test_unaligned_bit_chunk_count_ones` still passes. The 64-bit cases went back to baseline (no significant change), and the 1024-bit cases improved from ~4% to ~12% faster. This was one run on one machine, and your bot results show the 64-bit cases as faster on Axion, so some of what I saw may be code layout. The change is small and reads more directly, so I think it's worth taking either way. **Nits** - The test only uses uniform bytes (`0xFF`, `0xA5`, `0x00`). That's fine today because the sum doesn't depend on lane order, but one case with random bytes would guard against a future change to the lane indexing. - You note that with `codegen-units = 1` consumers won't see most of the 64-bit/1024-bit gain. That seems right, so I'd treat the 65536-bit numbers as the real benefit. I couldn't test the non-aarch64 `count_ones_words` here (no x86 target), but it looks like the old code moved into a helper. -- 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]
