[
https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17319494#comment-17319494
]
Kirill Lykov edited comment on ARROW-10899 at 4/12/21, 3:04 PM:
----------------------------------------------------------------
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 takes 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% 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
was (Author: klykov):
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)
