JonSnow1807 commented on issue #11543: URL: https://github.com/apache/arrow-rs/issues/11543#issuecomment-6593467057
Measured, not shipping. Four block-wise / multi-word variants of `filter_bits` were built and benchmarked against the current per-word loop on an M2 Pro (AArch64, no pext; rustc 1.97.1; `cargo bench -p arrow-select --bench filter_bits`, criterion, 100 samples per row, a fresh baseline per round). None meets “sparse rows faster and nothing else more than ~2 % slower”: | random batch, kept | 8-word block, strategy per block | 2-word count window | sparse gate + 2-bit extraction + 4-word empty skip | 2-word shared extraction loop | |---|---:|---:|---:|---:| | 1/16 | +16 % | +0.2 % | -10.7 % | -27.1 % | | 1/64 | +49 % | -5.7 % | +33.5 % | +1.3 % | | 1/256 | +64 % | +13.7 % | +20.6 % | +30.2 % | | 1/1024 | +52 % | +8.9 % | +26.5 % | +16.4 % | (the 8-word variant also put “indices, kept 1/256” at +173 % and the dense random rows at +7..+12 %) Why it loses: the current loop already skips a zero mask word before it loads the value word, and the compiler keeps one popcount per non-zero word (the two source-level counts fold into one `cnt`/`addv`). At 1/256 and sparser almost every word is empty, so any per-block gathering, counting or dispatch is pure overhead on those rows. The variants that win the 1/16 row (where blocks are rarely empty) pay for it on the sparser rows, and the sparse-index path (`count <= len / 64`) already covers the “indices” rows. On this machine the per-word structure is close to the floor without pext. Not opening a PR for this. The candidate diffs, criterion logs and assembly are kept locally. Happy to share them if someone wants to build on it. Releasing the claim. -- 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]
