Repository navigation
perf(arrow-buffer): faster portable fallback for bit_util::compress - #11322
Open
mightsleep wants to merge 2 commits into
Open
mightsleep wants to merge 2 commits into
mightsleep wants to merge 2 commits into
Conversation
Contributor
Author
|
run benchmark filter_bits |
This comment has been minimized.
This comment has been minimized.
Contributor
|
run benchmark filter_bits |
This comment has been minimized.
This comment has been minimized.
Contributor
|
run benchmark filter_bits |
|
🤖 Benchmark starting (GKE) | trigger Target: filter_bits Sharding factor: 1 (1 workers). Comparing compress-portable (2e6f713) to 08651bc (merge-base) diff Run configurationrun benchmark filter_bits
env:
BENCH_FILTER: batches
shards: 1
Results will be posted when all workers finish. File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Target: filter_bits Comparing compress-portable (2e6f713) to 08651bc (merge-base) diff Run configurationrun benchmark filter_bits
env:
BENCH_FILTER: batches
shards: 1
DetailsPer-runner informationfilter_bits — shard 1/1Node: gk3-benchmark-cluster-nap-k44dd5ur-758ad03e-dbbg Instance: c4a-highmem-16 (12 vCPU / 65 GiB) uname: BENCH_COMMAND: cargo bench --features=arrow,async,test_common,experimental,object_store --bench filter_bitsCPU Details (lscpu)Resource Usagebase (merge-base)
branch
File an issue against this benchmark runner |
Contributor
Author
|
ty for running. Could you also run filter_kernels? #11055 has it on the same runner, and that would put both compress versions side by side on the null-mask paths too |
Contributor
|
run benchmark filter_kernels |
1 similar comment
Contributor
|
run benchmark filter_kernels |
|
🤖 Benchmark starting (GKE) | trigger Target: filter_kernels Sharding factor: 1 (1 workers). Comparing compress-portable (2e6f713) to 08651bc (merge-base) diff Run configurationrun benchmark filter_kernels
shards: 1
Results will be posted when all workers finish. File an issue against this benchmark runner |
|
🤖 Benchmark starting (GKE) | trigger Target: filter_kernels Sharding factor: 1 (1 workers). Comparing compress-portable (2e6f713) to 08651bc (merge-base) diff Run configurationrun benchmark filter_kernels
shards: 1
Results will be posted when all workers finish. File an issue against this benchmark runner |
Contributor
|
FYI @devanbenz |
|
🤖 Benchmark completed (GKE) | trigger Target: filter_kernels Comparing compress-portable (2e6f713) to 08651bc (merge-base) diff Run configurationrun benchmark filter_kernels
shards: 1
DetailsPer-runner informationfilter_kernels — shard 1/1Node: gk3-benchmark-cluster-nap-138ltj7s-756b5f7d-kl2n Instance: c4a-highmem-16 (12 vCPU / 65 GiB) uname: BENCH_COMMAND: cargo bench --features=arrow,async,test_common,experimental,object_store --bench filter_kernelsCPU Details (lscpu)Resource Usagebase (merge-base)
branch
File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Target: filter_kernels Comparing compress-portable (2e6f713) to 08651bc (merge-base) diff Run configurationrun benchmark filter_kernels
shards: 1
DetailsPer-runner informationfilter_kernels — shard 1/1Node: gk3-benchmark-cluster-nap-138ltj7s-6d311157-rlzv Instance: c4a-highmem-16 (12 vCPU / 65 GiB) uname: BENCH_COMMAND: cargo bench --features=arrow,async,test_common,experimental,object_store --bench filter_kernelsCPU Details (lscpu)Resource Usagebase (merge-base)
branch
File an issue against this benchmark runner |
This branch has not been deployed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Which issue does this PR close?
filterkernel (whenpextinstruction is not available) #11213.Rationale for this change
Without
pext(every aarch64 build, and x86-64 builds without BMI2, the default target)compresswalks 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 loopk <= 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 loopcompress_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 by0x0101..01.Builds with BMI2 enabled keep
pextand are unchanged.Are these changes tested?
test_compress_portablechecks 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_bitsbatches from #11271 (512 batches of 8K rows):The other callers of
compress:filter_kernels: filter context i32 w NULLs (kept 1/2)filter_kernels: filter context u8 w NULLs (kept 1/2)filter_kernels: filter context string dictionary w NULLs (kept 1/2)filter_kernels: other w NULLs casesarrow_reader: ListArray and struct (definition levels)What gets slower, ideas welcome
Sparse masks. Up to 9 % on EPYC 7763 (random, kept 1/16), 7 % with x86-64-v2 (
filter_bitsindices, 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:
perf stathad 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).k <= 2andk >= 62cases 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.What I have not tried, in case it itches someone:
The runners are shared VMs. The
macos-15runner is not in the tables: its rounds differed by up to 30 % even on cases that never reachcompress.Are there any user-facing changes?
No.
compresskeeps its signature and its results; only its speed without BMI2 changes.