[
https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17282023#comment-17282023
]
Kirill Lykov edited comment on ARROW-10899 at 2/9/21, 8:38 PM:
---------------------------------------------------------------
Your intuition is correct, at least for int32_t key. I benchmarked separately
from arrow std::sort, std::stable_sort, boost::spreadsort, myNaiveRadixSort.
And surprisingly to me even naive radix sort is faster than std sorts. But
boost's spread sort is better. Y-axis is kMilliseconds, X-axis is number of
elements in the array. It suggests to use boost::spreadsort
!Screen Shot 2021-02-09 at 17.48.13.png!
was (Author: klykov):
Your intuition is correct, at least for int32_t key. I benchmarked separately
from arrow std::sort, std::stable_sort, boost::spreadsort, myNaiveRadixSort.
And surprisingly to me even naive radix sort is faster than std sorts. But
boost's spread sort is better. Y-axis is kMilliseconds, X-axis is number of
elements in the array.
!Screen Shot 2021-02-09 at 17.48.13.png!
> [C++] Investigate radix sort for integer arrays
> -----------------------------------------------
>
> Key: ARROW-10899
> URL: https://issues.apache.org/jira/browse/ARROW-10899
> Project: Apache Arrow
> Issue Type: Wish
> Components: C++
> Reporter: Antoine Pitrou
> Assignee: Kirill Lykov
> Priority: Major
> Attachments: Screen Shot 2021-02-09 at 17.48.13.png
>
>
> For integer arrays with a non-tiny range of values, we currently use a stable
> sort. It may be faster to use a radix sort instead.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
