Re: [boost] Proposed templated integer_sort

From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-07-06 15:15:53

> FWIW, the requirements of std::sort are satisfied by quicksort, an
> algorithm that works on bidirectional iterators only (it just depends on
> partition and swap), and if you allow it to be adaptive (i.e. use
> temporary storage) it can work on forward iterators (see
> std::stable_partition) -- although the latter may not be any faster than
> copying into a vector, sorting that, and copying back.
>

That may be true, but Introsort is significantly faster both on average and
worst-case than Quicksort, and SGI's STL implementation uses Introsort,
which uses a random access iterator.
The first version of Spreadsort I wrote in 2001 allocated separate memory
for each bin, and with a linked-list approach instead each sorting operation
could be done in a single pass (as opposed to the three passes used in the
version I'm turning into integer_sort), though without finding the maximum
and minimum values.  That would make more sense to use with a linked-list
data set.  It's not complicated to implement, but my testing shows that
iterating through linked lists is slow because they often have cache misses,
and besides, binary search only makes sense in a data structure that
supports random access.
Do you have a genuine desire for a real application to see a bidirectional
(or unidirectional) iterator version of a hybrid sort?  Spreadsort isn't
much slower on a linked list than on an array, so it should do much better
than Quicksort.  I normally think of sorting linked lists as a rare niche
application.  In my own work I avoid linked lists because there is a better
standard data structure for every problem I've run into.

>
> > and should be just as
> > flexible.  I will see if using some generic algorithms for iterators
> > improves the performance a little; I'm seeing a noticeable speed penalty
> > with iterators instead of pointers.  I get the same performance as the
> old
> > code when I pass in pointers as the iterators, but a roughly 15% increase
> in
> > runtime when I use .begin() and .end().
>
> What compiler are you testing?  VC++ uses checked iterators by default,
> which slows everything down terribly.  You might try putting
> -D_SECURE_SCL=0 in your command line.  See
>
> http://einaros.blogspot.com/2007/02/iteration-techniques-put-on-benchmark.html
>

I'm using g++ on an OSX laptop with a G4 processor (slow and old, in other
words).  I tried your suggested command line option and it made no visible
difference, but thanks for the suggestion.  If I sort using &(vec[0]),
&(vec[0])+vec.size(), it still runs 15% faster than with vec.begin(),
vec.end().

Steve