[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17378494#comment-17378494 ] Antoine Pitrou commented on ARROW-10899: Also worth taking a look at https://github.com/scandum/quadsort , even if it's not radix-based. > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.png, differentdistrib.png, > uniform_1B_wolf.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17360244#comment-17360244 ] Antoine Pitrou commented on ARROW-10899: Ha, the search space for sorting algorithms looks a bit crowded :-) Generally speaking, I don't think there's a need to press forward on this issue. But your experiments and findings are extremely useful and will probably serve us in the future, so thanks a lot! > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.png, differentdistrib.png, > uniform_1B_wolf.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17360162#comment-17360162 ] Kirill Lykov commented on ARROW-10899: -- Well, it looks like it is called "wolf sort" (https://github.com/scandum/wolfsort). I compared the implementation of Igor with Travis lsd and stable sort, see !uniform_1B_wolf.png! I don't know if his implementation is good/bad. I just took it and made it a bit more typed to be compiled by C++ compiler, see https://github.com/KirillLykov/int-sort-bmk/blob/wolfSortCheck/ branch if really interested > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.png, differentdistrib.png, > uniform_1B_wolf.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17360141#comment-17360141 ] Antoine Pitrou commented on ARROW-10899: Good question about bandwidth! A possible solution for the bandwidth issue may be to 1) run a LSD radix sort on small-sized chunks (for example 64kB or 128kB, to fit in L2) 2) run a merge sort on the resulting sorted chunks. I'm not sure what the performance would be. > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.png, differentdistrib.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17360115#comment-17360115 ] Kirill Lykov commented on ARROW-10899: -- LSD sort is stable. Do you want to try with Travis' LSD sort implementation? > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.png, differentdistrib.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17359997#comment-17359997 ] Antoine Pitrou commented on ARROW-10899: Thanks for the investigation! Were you able to check on the claim that Travis' LSD sort is stable? > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.png, differentdistrib.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17359990#comment-17359990 ] Kirill Lykov commented on ARROW-10899: -- I have to drop this ticket but if someone will take it, I will be glad to assist. Below is a summary of the research I did. First of all I couldn't find ready to use stable radix sort implementation which is fast and generic. boost::spread_sort is the best available implementation of in-place radix sort because it designed to perform well on all the inputs. On the contrary, vanilla radix sort will perform poorly on some types of distributions as shown on the plot below. spread_sort performs better for two reasons: * it detect some cases when radix sort will perform poorly and relies on boost's pdqsort sorting algorithm * it uses adaptive size of the radix rather than fixed What makes spreadsort unstable is that it sometimes relies on pdqsort which is unstable and that it is in-place sort. Hence, it is possible to make it stable by replacing calls to pdqsort to stable_sort and by using additional buffer instead of doing in-place sorting. !differentdistrib.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, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.png, differentdistrib.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17341925#comment-17341925 ] Kirill Lykov commented on ARROW-10899: -- I believe that the LSD implementation by Travis is stable by construction, I will recheck it. Regarding stable_sort – i'm trying to find a way to rely on stable_sort instead of radix sort for particular types of distributions. These checks are done in boost::spread_sort but I haven't got the math behind yet. > [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, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[
https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17341893#comment-17341893
]
Antoine Pitrou commented on ARROW-10899:
Thanks a lot for running these benchmarks, by the way. It seems that
{{std::stable_sort}} is already quite good on several cases.
> [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, Screen Shot
> 2021-02-10 at 10.58.23.png, all_random_wholeRange.png,
> all_random_wholeRange.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17341891#comment-17341891 ] Antoine Pitrou commented on ARROW-10899: We can't presume anything about the distribution of integers. It could be anything. Also, they may be signed or unsigned (but I don't think that makes a lot of difference, does it?). Do note that we need a stable sort, so I don't think using LSD can work. > [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, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17341526#comment-17341526 ] Kirill Lykov commented on ARROW-10899: -- Do we have some information about distribution of integers? And also are they signed/unsigned? I've did some more benchmarking and plots [int-sort-bmks repo|[https://github.com/KirillLykov/int-sort-bmk].] In short, radix sort is almost always performs better than std::stable_sort. But there are some cases when stable_sort is better – sorted sequence, all elements are equal. Another observation is that it looks like LSD implementation is faster than MSD implementation. Yet it is possible to have almost the same performance using MSD/LSD hybrid algorithm if we think that MSD is better for memory bandwidth. The question is how to measure memory bandwidth consumption, I employed LLC-cache-misses events. > [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, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17332655#comment-17332655 ] Kirill Lykov commented on ARROW-10899: -- Actually, I don't see significant effect of prefetch in my benchmarks. Probably, because I use clang. Now wondering how it is compiling > [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, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[
https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17332650#comment-17332650
]
Antoine Pitrou commented on ARROW-10899:
You should probably bench against {{radix_sort6}} because {{radix_sort7}}
merely adds an explicit prefetch which is a bit orthogonal.
> [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, Screen Shot
> 2021-02-10 at 10.58.23.png, all_random_wholeRange.png,
> all_random_wholeRange.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17332609#comment-17332609 ] Kirill Lykov commented on ARROW-10899: -- I'm continuing experiments with MSD sort. Please ignore code style sine it is for experiments. I'm using gist as log for optimizations https://gist.github.com/KirillLykov/c641e63adfd68591bafbdb342f75d141 Each comment in this gist is an iteration of optimization. Please let me know someone has ideas to try. I was planing try to get rid of recursion by using stack explicitly. Don't see any other big things to do with it. !all_random_wholeRange.png! Idea by [~michalno] to use another sorting algorithm if the size of the subarray to sort is smaller than some level surprisingly doesn't work well on my array (for now only uniform distribution). > [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, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.png, > all_random_wholeRange.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[
https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17324903#comment-17324903
]
Antoine Pitrou commented on ARROW-10899:
I'm not sure we need intense benchmarking. Admittedly, it's better to test
sorting on all kinds of input (almost sorted, random, etc.). However, we don't
necessarily need that if we just want to find a cutoff point between radix
sorting and {{std::stable_sort}} (which is probably a merge sort with fallback
to a simpler sort for small sizes).
> [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, Screen Shot
> 2021-02-10 at 10.58.23.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17324878#comment-17324878 ] Kirill Lykov commented on ARROW-10899: -- Updates, I've contacted Travis and he wrote that he has a luck of time to work on it yet it seems interesting to him. He mentioned also that MSD implementation might be better for bandwidth. I'm thinking about the way to proceed. One option might be 1. Travis will create a PR just with his radix sort implementation 2. I will add tests and benchmarks to his PR One thing which kind of worries me is that sorting requires quite intense ad-hoc testing and benchmarking, are we fine with adding all these to the Arrow repository? > [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, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17319494#comment-17319494 ] Kirill Lykov commented on ARROW-10899: -- Right, I agree that it is stable. >From performance prospective, the main difference with naive implementation of >Cormen's pseudo code: 1) Skip unnecessary iterations (if all the numbers have current bits (8 bits in Travis code) set to the same value). Gives ~36% 2) Instead of using offset array use array of pointers which take into account these offsets. So instead of `out[offset[(value>>shift)]]=123 `do `pOut[(value>>shift)] = 123` where pOut is precomputed to be `[0] + offset[]`. Gives ~24% He also uses `__builtin_prefetch` from gcc library, I'm not sure if it is portable. It might give 12% of performance on some large datasets. I will write to Travis directly. Probably, he will like to contribute a version of this sort and I will do plumbing > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17319476#comment-17319476 ] Antoine Pitrou commented on ARROW-10899: I don't know if Travis would be interested, as plumbing work would probably dominate the actual optimization work (but I don't know what his interests are). That said, it probably doesn't hurt to ask him :-) > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17319478#comment-17319478 ] Antoine Pitrou commented on ARROW-10899: Also, AFAIU his radix sort implementation is simply a left-to-right (most significant digit first) radix sort, so should be stable unless there is a bug. > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17318707#comment-17318707 ] Kirill Lykov commented on ARROW-10899: -- Thanks for the reference to the blog, I read all of his posts. I've checked with my benchmarks Travis' final radix_sort7 version, see below. It kind of rocks! !all_random_wholeRange.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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.png, all_random_wholeRange.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17318133#comment-17318133 ] Antoine Pitrou commented on ARROW-10899: Interesting read here: https://travisdowns.github.io/blog/2019/05/22/sorting.html > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17314867#comment-17314867 ] Antoine Pitrou commented on ARROW-10899: Thanks for the update [~klykov]. It will be useful if someone else takes up this issue. > [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 >Priority: Major > Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot > 2021-02-10 at 10.58.23.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17314850#comment-17314850 ] Kirill Lykov commented on ARROW-10899: -- I added a repository to put there some experiments i've done for the earlier added plots: [https://github.com/KirillLykov/int-sort-bmk] Unfortunately, I couldn't achieve a fast progress on this ticket and since it is not my main activity I decided to freeze it on my side. By fast progress I mean delivering a stable non-comparison-based sorting algorithm which is faster than std::stable_sort. Naiveradix sort which is implemented there is much slower on int64_t as one might find by looking into the plots in scripts/imgs. The last thing that I was trying to do is to modify boost's integer_sort to make it stable (as unstable version is really fast). To simplify experiments with integer_sort I've extracted it in one separate file called [https://github.com/KirillLykov/int-sort-bmk/blob/master/src/boost_spread_sort.h] One can find that integer_sort sometimes relies on pdqsort. This can be replaced with stable_sort. A more interesting part of the code which I think makes integer_sort unstable is [https://github.com/KirillLykov/int-sort-bmk/blob/master/src/boost_spread_sort.h#L210] I think in-place version can be replaced with non-in-place. > [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, Screen Shot > 2021-02-10 at 10.58.23.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17282484#comment-17282484 ] Kirill Lykov commented on ARROW-10899: -- On a higher level I honestly thought that I will easily find a suitable opensource sort implementation. So did just basic benchmarking. I think I will create a separate repo just for benchmarking existing sorting algorithms alone together with candidate implementation. > [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, Screen Shot > 2021-02-10 at 10.58.23.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17282355#comment-17282355 ] Antoine Pitrou commented on ARROW-10899: Even a radix sort is not necessarily stable. You have to be careful when implementing it: see https://en.wikipedia.org/wiki/Radix_sort Also, I assume your benchmarks are on random data? Data is very often not randomly distributed. On real-world data, a int32 or int64 column doesn't necessarily span the whole int32 or int64 range, for example. Perhaps heuristics would need to be devised, based on the input range and the input size you would either use a radix sort (which is O(n)) or a comparison-based sort such as spinsort (which is O(n log n)). > [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, Screen Shot > 2021-02-10 at 10.58.23.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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17282030#comment-17282030 ] Kirill Lykov commented on ARROW-10899: -- Right, I will check also spinsort from boost > [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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17282026#comment-17282026 ] Antoine Pitrou commented on ARROW-10899: Note that we need a stable sort, which spreadsort apparently isn't. > [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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17282023#comment-17282023 ] Kirill Lykov commented on ARROW-10899: -- 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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[
https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17281908#comment-17281908
]
Antoine Pitrou commented on ARROW-10899:
[~klykov] Feel free to experiment, but note that adding SIMD into the mix will
add a layer of complication.
For a non-SIMD implementation, my intuition is that a radix sort could be
significantly faster on large data than the current merge sort (a.k.a
{{std::stable_sort}}).
> [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
>
> 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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17281864#comment-17281864 ] Kirill Lykov commented on ARROW-10899: -- 1. From the paper "Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort" by Satish et al: They compare, beside other things, performance of radix sort and merge sort using intrinsics. Both implementations are highly optimized for simd architecture and radix has many not obvious improvements to make it more cache-friendly. Radix sort performance depends on the key size because the longer key we have the more passes we need to do. Radix is bandwidth-bound starting at 48-bits keys. Further, Satish et al report that merge sort is 1.7X slower than radix sort on 32- bit keys, but becomes comparable in performance to radix on 64-bit keys and 1.3X better on 128-bit keys. Their conclusion is that "bandwidth-oblivious SIMD friendly merge sort, should, therefore, be the sorting method of choice for future databases". 2. I haven't found a good opensource radix sort for CPUs. There is one in boost called spread sort but it is not actually a radix sort and according to my benchmarks for integers it demonstrates exactly the same performance as gcc's stable_sort. From description, It might be designed for strings. > [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 > > 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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17280272#comment-17280272 ] Kirill Lykov commented on ARROW-10899: -- Thanks for the clarification, I will check it out next week. > [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 >Priority: Major > > 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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17280197#comment-17280197 ] Yibo Cai commented on ARROW-10899: -- [~apitrou], please correct me if I missed somthing. Code: [vector_sort.cc|https://github.com/apache/arrow/blob/master/cpp/src/arrow/compute/kernels/vector_sort.cc] Unit test: [vector_sort_test.cc|https://github.com/apache/arrow/blob/master/cpp/src/arrow/compute/kernels/vector_sort_test.cc] Benchmark: [vector_sort_benchmark.cc|https://github.com/apache/arrow/blob/master/cpp/src/arrow/compute/kernels/vector_sort_benchmark.cc] Please note current code supports sorting multiple columns, so looks a bit complex. I think we can start with single array sorter. Specifically, below code line calling std::stable_sort https://github.com/apache/arrow/blob/a321cdedb75b27b669995065ffe5596b3cfb3ae4/cpp/src/arrow/compute/kernels/vector_sort.cc#L378 > [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 >Priority: Major > > 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)
[jira] [Commented] (ARROW-10899) [C++] Investigate radix sort for integer arrays
[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17279881#comment-17279881 ] Kirill Lykov commented on ARROW-10899: -- Sounds interesting to me, I would like to have a look. Could give some more details from where to start? I mean: * where exactly this sorting happens, * are there existing benchmarks for this sorting (if not, what is the best place to add them) > [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 >Priority: Major > > 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)
