[ 
https://issues.apache.org/jira/browse/ARROW-1571?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17021827#comment-17021827
 ] 

Yibo Cai commented on ARROW-1571:
---------------------------------

Two variables need be figured out:
- Array Size: Array size to begin benefiting from such an optimization. The 
smaller, the better.
- Value Range: Gaps between max and min value for an array to benefit from such 
an optimization. The larger, the better.

It's non trivial to find the optimial parameters, as there two variables are 
correlated, and they depend on actual hardware.

I did some benchmark, and plotted how "array size" and "value range" affect 
performance (speed ratio of counting sort vs std::stable_sort).
Test code at: https://github.com/cyb70289/mytests/blob/master/cpp/sort-range.cc
Bench and plot code at: 
https://github.com/cyb70289/bench-graph/tree/master/sort-range

Per my investigation, leveraging counting sort in large integers with limited 
value range can improve performance significantly, if did right.

Below plot is tested on Tntel E5-2650 cpu.
- Y axis is "speed-of-counting-sort / speed-of-stl-stable-sort", its value 
above 1 means counting sort is better than stl stablesort.
- X axis is array size, plotted in log scale
- Different lines map to different value range

>From the plot, we can see if we leverage counting sort for arrays with at 
>least 1000 elements and value range less than 4096, we can always get above 7x 
>performance uplift.

 !e5-2650.png! 

> [C++] Implement argsort kernels (sort indices) for integers using O(n) 
> counting sort
> ------------------------------------------------------------------------------------
>
>                 Key: ARROW-1571
>                 URL: https://issues.apache.org/jira/browse/ARROW-1571
>             Project: Apache Arrow
>          Issue Type: New Feature
>          Components: C++
>            Reporter: Wes McKinney
>            Priority: Major
>              Labels: Analytics
>             Fix For: 2.0.0
>
>         Attachments: e5-2650.png
>
>
> This function requires knowledge of the minimum and maximum of an array. If 
> it is small enough, then an array of size {{maximum - minimum}} can be 
> constructed and used to tabulate value frequencies and then compute the sort 
> indices (this is called "grade up" or "grade down" in APL languages). There 
> is generally a cross-over point where this function performs worse than 
> mergesort or quicksort due to data locality issues



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

Reply via email to