perfloop-agent opened a new pull request, #10576: URL: https://github.com/apache/arrow-rs/pull/10576
## Summary Add a guarded counting-scatter path for full dictionary index sorts. When dictionary cardinality is favorable and sampled ranks show sustained disorder, the sort counts ranks, computes bucket offsets, and scatters source indices instead of comparison-sorting index/rank pairs. The existing comparison path remains in use for partial sorts, large or sparsely used dictionaries, ordered and nearly ordered inputs, and small valid-row inputs where dense rank workspace is not worthwhile. ## Performance On workload `permuted dictionary string sort to indices, n=4096 k=256`, median metric `ns/op` changed from 48731 to 12412; paired median delta -36327 (-74.5% of baseline; at least 19/20 confidence interval -36500 to -35827 from 10 pairs). On workload `permuted dictionary string sort to indices, n=65536 k=4096`, median metric `ns/op` changed from 1006540 to 539478; paired median delta -467948 (-46.5% of baseline; at least 19/20 confidence interval -483070 to -446952 from 10 pairs). On workload `permuted dictionary string sort to indices, n=65536 k=131072 (K=2N)`, median metric `ns/op` changed from 2091726 to 1454605; paired median delta -632116 (-30.2% of baseline; at least 19/20 confidence interval -657761 to -610537 from 10 pairs). On workload `permuted dictionary string sort to indices, n=65536 k=524288 (K=8N)`, median metric `ns/op` changed from 5397514 to 5145035; paired median delta -254849 (-4.7% of baseline; at least 19/20 confidence interval -406003 to -131290 from 10 pairs). On workload `dictionary sorting CPU profile, permuted n=65536 k=524288`, median metric `dictionary_pair_sort_cpu_pct` changed from 29.16 to 0; paired median delta -29.16 (-100% of baseline; at least 19/20 confidence interval -32.88 to -26.01 from 10 pairs). On workload `dictionary sorting CPU profile, permuted n=65536 k=524288`, median metric `count_scatter_cpu_pct` changed from 0 to 28.47; paired median delta 28.47 (at least 19/20 confidence interval 26.18 to 32.14 from 10 pairs). ## Testing Ran formatting, arrow-ord tests with all features and in release mode, clippy for arrow-ord and arrow, and the complete sort-kernel benchmark test suite. Selector unit coverage includes ordered, periodic, permuted, and isolated-inversion inputs; existing sorting tests cover ordering, null placement, limits, and sort options. All 6 declared correctness checks passed. --- Authored and verified by [Perfloop](https://app.perfloop.ai): every claim above was co-measured on both trees and independently re-verified before submission — the full record is public: [case_a0kjk42gzp](https://app.perfloop.ai/t/oss/case_a0kjk42gzp). Replies from this account are human-approved, and a human operator is accountable for this contribution. -- 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]
