mbutrovich commented on PR #9683:
URL: https://github.com/apache/arrow-rs/pull/9683#issuecomment-6851851176

   I added `limit: Option<usize>` to `radix_sort_to_indices`. With a limit, the 
MSD radix sort skips buckets that start at or after `limit` and stops ordering 
tied rows past it.
   
   An unlimited sort passes a zero-sized `Unlimited` type instead of a `usize`. 
A first version passed the limit as a `usize` argument to `msd_radix_sort` in 
every case, and I changed it after checking small inputs. The zero-sized type 
keeps the unlimited sort's arguments the same as before the limit.
   
   The benchmark bot at 03ee81c against d3824b8, which has no `limit`, shows no 
change on the full-sort path. The median speedup of `lexsort_radix` over 
`lexsort_to_indices` moved by 0.985x to 1.002x across the four runs 
(Neoverse-V2 and Xeon Platinum 8581C, default and aligned). The per-case 
minimums are 0.86x to 0.92x. The untouched `encode` cases have minimums of 
0.75x to 0.96x in the same runs, so that spread is run noise.
   
   With a `limit`, radix sort is faster than `lexsort_to_indices` from `limit` 
1000 on 32768 rows (1.28x to 1.68x) and at `limit` n/10 on 1M rows (2.89x to 
4.60x). It is slower at `limit` 100 (0.28x to 0.36x on 32768 rows, 0.09x to 
0.15x on 1M rows). The PR description has the limit tables and chart.
   


-- 
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]

Reply via email to