mightsleep commented on issue #11213: URL: https://github.com/apache/arrow-rs/issues/11213#issuecomment-5860320119
Yes hello, I ran the options from this thread, plus the two @jhorstmann linked, through the whole `filter_bits_compress` loop (compress plus the packer) on random, clustered and periodic masks. Default target features: no BMI2, and on x86 no POPCNT. Two things first. On random masks the current loop spends most of its time on its exit, not its work: the kept count per word is random, so the exit mispredicts almost every time. And the existing bench repeats one 1024-word mask, which a recent core memorises, so its random cases run about twice as fast as fresh data does. I spent a while benchmarking the branch predictor before noticing. Against the current loop, Zen 5, above 1 is faster: | mask | smaller side | nibble LUT | `extract_bits` | Arrow C++ | this | |---|---|---|---|---|---| | random, 1/64 | 0.86 | 0.43 | 0.58 | 0.50 | 2.8 | | random, 1/2 | 0.72 | 1.69 | 2.30 | 1.77 | 3.0 | | random, 15/16 | 2.8 | 2.5 | 3.3 | 2.7 | 4.2 | | runs of 4096, 1/2 | 8.0 | 1.2 | 1.6 | 9.4 | 7.6 | | every 10th row | 0.99 | 0.28 | 0.41 | 0.34 | 1.00 | Each of them loses to the loop somewhere. "This" dispatches on `k = mask.count_ones()`, which the packer needs anyway. `k <= 2`: the lowest set bit and the one above it, tested directly, so no loop and no exit to mispredict. `k <= 16`: the current loop, the cheapest thing going when the data make its branches predictable (clustered or periodic rows). `k >= 62`: a full word returns `value`, otherwise the at most two dropped bits are removed highest first, branch-free. The rest goes to `compress_bytes`, constant time and table-free. Each kept bit has to move down by the number of dropped bits below it; write that distance in binary, and round `i` moves every bit whose distance has bit `i` set by `2^i`. This is the network of `core`'s `extract_bits`, but run within each byte, where distances are below 8: three rounds instead of six, on all eight bytes at once, every shift masked so no bit crosses into its neighbour. That leaves each byte's kept bits at its bottom. A popcount per byte multiplied by `0x0101..01` gives every byte's offset in one go (the product's byte `j` is the sum of the counts below it), and eight independent shifts join the bytes. About 7 ns a word flat, against 10 to 15 for the full network, which spends its three long rounds moving whole bytes that one multiply can place. About 55 lines. The existing test draws uniform masks only (about 32 kept bits), so it would reach one of the four paths; the new one covers every mask with at most two kept or two dropped bits, random masks at every density, and every popcount. GitHub runners, 4 Mi-row masks of fresh data, against main (two interleaved runs each agree within 1 %): | mask | Neoverse-N2 | Xeon 8573C | |---|---|---| | random, 1/64 | 1.26 | 1.23 | | random, 1/16 | 1.00 | 0.97 | | random, 1/2 | 3.6 | 2.7 | | random, 15/16 | 5.8 | 3.7 | | runs of 4096, 1/2 | 16.4 | 10.1 | The 0.97 is the one loss I could not remove: x86 without POPCNT, where a software popcount now sits in front of every word. Further gains exist, but they change `filter_bits_compress` rather than `compress`, so they would be a follow-up rather than part of this: - count ahead: the masks are all in memory, so the popcounts of a block can be computed in one pass that vectorises even on SSE2, which takes the software popcount (the 0.97 above) off the per-word path; it needs a `compress` that takes the count; - choose per call, not per word: whether the loop or the constant-time kernel wins for 3 to 16 kept bits depends on whether the branches are predictable, which one word cannot tell but the variation of the counts across a batch can. If the direction is fine I'll open a PR, with the larger bench cases as its first commit. -- 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]
