Re: [boost] [sorting] How radixsort can be more useful than quicksort

From: Sam Schetterer (samthecppman_at_[hidden])
Date: 2007-03-18 14:56:54

Henrik Sundberg wrote
>The '<' is used for branching anyway. Is this really a valid reason?
>Constructing concatenated strings for all values to be sorted to be
>able to use string sort, seems to be a big overhead.
In both normal and radix quicksort, when that is used for branching, the
compiler arranges the code so the the cpu will usually follow the right
branch path, meaning that it will pipeline into the if or while or for
statement. However, in cases like the example, many of the less than
statements in the operator< will not be satisfied, breaking the pipeline
again and again, especially when it goes all the way to the bottom of the
statement. On vault, I have uploaded source code for a radixosrt that shows
the problme with complex operator< (it uses normal radixsort), when compared
to the operator[] for normal radixsort. also, imagine that the class that
you have designed with a complex operator< is a template class that is used
for many types. For radixsort, that size of operator[] is constant. With
operator<, it grows to large sizes and causes coad bloat, and it is slow. In
addition, even if quicksort is still faster than radixsort, radixsort hs a
linear running time (complexity is O(N)),  and will always run that fast for
any possible order of the data. Finally, going back to the problem of
pipelining, radixsort is very pipeline friendy, and almost all of the
branches will be properly followed. The only time that will not happen is
when each for loop is exited. On computers with long pipelines, like the
Pentium Pro, which has a 20 step pipeline, along with many other computers,
radixsort will have a huge advantage of quicksort for complex operator<.
Then, about creating strings, it is not a very large overhead and only has
to be done when the objects change, and is only done on objects containing
strings. When strings are normally compared, each byte is examined each
time. radix quicksort only examines each byte once, giving it another large
advantage over normal quicksort and other non-radix sorts.