mightsleep commented on PR #11055: URL: https://github.com/apache/arrow-rs/pull/11055#issuecomment-5880717323
Yes hello, @Rich-T-kid some numbers, since you asked for a second pair of eyes. For #11213 I have a different portable `compress` (not a PR yet) and timed it with this PR and #11086 against main on GitHub runners: `filter_bits` from main, the large masks from #11271, and 22 masks from real TPC-H and NYC taxi predicates. main / variant, above 1 is faster, 71 cases: | | N2 geomean | N2 min | Zen 4 geomean | Zen 4 min | |---|---|---|---|---| | this PR | 1.31 | 0.62 | 1.16 | 0.57 | | #11086 | 0.90 | 0.27 | 0.83 | 0.20 | | #11213 draft | 2.24 | 0.92 | 1.94 | 0.89 | The draft is w/o any LUT table for nibbles; it dispatches on the kept count k, with the bit loop for k ≤ 16 and a direct formula when k ≤ 2 or k ≥ 62. In between, each kept bit moves down by the number of dropped bits below it within its byte, done as shifts by 1, 2 and 4 on all eight bytes at once. Byte i then lands at the sum of the counts of bytes below it, and one multiply by `0x0101..01` gives all eight of those sums. Before opening a PR I am still on its tests, which cover every path of the dispatch, and on Zen 4, where it is still slower on sparse masks. The benchmarks in #11271 might be useful here too: the existing `filter_bits` cases repeat a 1024-word mask, which the branch predictor learns, so they hide most of the difference between fallbacks. The large random and clustered masks there do not. `gather_bits` in the strategy paths is a clear win (N2: indices 1/2 1.44, slices 9/10 2.58). The nibble table loses to main at about 9 to 20 kept bits per word, which is common in real predicates (TPC-H Q6 date range 0.62). Would it work to keep `gather_bits` here and take the portable `compress` into a separate PR for #11213? Happy to rebase on whichever lands first. Runs: https://github.com/mightsleep/arrow-rs/actions/runs/36493097865 Is this ok? -- 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]
