mightsleep opened a new pull request, #11322: URL: https://github.com/apache/arrow-rs/pull/11322
# Which issue does this PR close? - Closes #11213. # Rationale for this change Without `pext` (every aarch64 build, and x86-64 builds without BMI2, the default target) `compress` walks the kept bits one at a time. With masks from independent rows the number of kept bits changes from word to word, so the loop exit mispredicts on almost every word, and a dense word takes up to 64 steps. # What changes are included in this PR? The fallback dispatches on the number of kept bits `k`: - `k <= 2`: the lowest two kept bits, no loop - `k <= 16`: the existing loop, still the cheapest when its branches are predictable (clustered or periodic rows) - `k >= 62`: the word with its at most two dropped bits removed, no loop - otherwise `compress_bytes`: constant time, no table. The parallel suffix network of HD 7-4 inside each byte (three rounds on all eight bytes at once), then the bytes joined at offsets from one multiply by `0x0101..01`. Builds with BMI2 enabled keep `pext` and are unchanged. # Are these changes tested? `test_compress_portable` checks every path against a reference: every mask with at most two kept or two dropped bits, random masks at every popcount. The existing test only draws uniform masks (about 32 kept bits), which reach ne path of four. Filter tests pass on x86-64, x86-64-v2 and with BMI2. ## Measurements main / this PR, above 1 is faster. GitHub runners: Neoverse-N2 (`ubuntu-24.04-arm`) and AMD EPYC 7763 (`ubuntu-latest`), both default target, plus x86-64-v2 (which has POPCNT). Each variant built once, three interleaved rounds. Between rounds a row moves by 0.6 % (median), at most 5.5 %. `filter_bits` batches from #11271 (512 batches of 8K rows): | mask | Neoverse-N2 | EPYC 7763 | EPYC 7763, v2 | |---|---|---|---| | random, kept 1/1024 | 0.99 | 1.01 | 0.95 | | random, kept 1/256 | 1.03 | 0.96 | 1.03 | | random, kept 1/64 | 1.21 | 1.20 | 1.27 | | random, kept 1/16 | 0.97 | 0.91 | 0.97 | | random, kept 1/4 | 1.21 | 1.12 | 1.19 | | random, kept 1/2 | 3.37 | 2.65 | 2.74 | | random, kept 3/4 | 4.68 | 3.54 | 3.64 | | random, kept 15/16 | 5.40 | 3.61 | 3.94 | | runs of 64, kept 1/8 | 2.11 | 1.77 | 1.87 | | runs of 64, kept 1/2 | 3.00 | 2.35 | 2.51 | | runs of 64, kept 7/8 | 4.75 | 3.46 | 3.78 | | runs of 512, kept 1/2 | 6.99 | 5.44 | 5.70 | The other callers of `compress`: | benchmark | Neoverse-N2 | EPYC 7763 | |---|---|---| | `filter_kernels`: filter context i32 w NULLs (kept 1/2) | 1.80 | 1.69 | | `filter_kernels`: filter context u8 w NULLs (kept 1/2) | 1.83 | 1.66 | | `filter_kernels`: filter context string dictionary w NULLs (kept 1/2) | 1.77 | 1.63 | | `filter_kernels`: other w NULLs cases | 0.96 to 1.78 | 0.96 to 1.64 | | `arrow_reader`: ListArray and struct (definition levels) | 0.99 to 1.11 | 0.98 to 1.07 | ## What gets slower, ideas welcome Sparse masks. Up to 9 % on EPYC 7763 (random, kept 1/16), 7 % with x86-64-v2 (`filter_bits` indices, kept 1/10), 5 % on Neoverse-N2 (indices, kept 1/1024). On a word with one or two kept bits the old loop did almost nothing, and it did it very well. The new code first counts the bits and branches on the count, and on the default x86-64 target that count is a software popcount, so every mispredicted dispatch also waits for it. What I tried, so nobody has to again: - Counting one word ahead, so the count is ready before its branch. `perf stat` had shown the same instructions and the same mispredictions as main, just about five cycles more per misprediction: the software popcount the branch waits on. The lookahead hid it, and Zen 5 hated it (EPYC 9V45, a large mask kept 1/256: 0.56 against main instead of 0.89). - Finding the `k <= 2` and `k >= 62` cases without a count, `m & (m - 1)` twice. Cheaper for those words, but every other word paid both tests before its count; words with exactly three kept bits went to 0.59 to 0.75. - The same tests plus the previous word's count as a hint for the rest: smaller gains everywhere, one slow case fixed and several new ones. On random rows the previous word is a poor hint. What I have not tried, in case it itches someone: - Pipeline by blocks instead of words: popcount four to eight words at once (SWAR works even on the SSE2 baseline) and dispatch on the block. A sparse block could then walk its set bits across words in one loop, and pay for the loop exit once per block, not once per word. - Anything that gets the sparse case back to the naive loop and then past it. The runners are shared VMs. The `macos-15` runner is not in the tables: its rounds differed by up to 30 % even on cases that never reach `compress`. # Are there any user-facing changes? No. `compress` keeps its signature and its results; only its speed without BMI2 changes. -- 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]
