[ https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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)&bitmask]]=123 `do `pOut[(value>>shift)&bitmask] = 123` where pOut is precomputed to be `&out[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)