Re: [boost] Proposed templated integer_sort

From: David Abrahams (dave_at_[hidden])
Date: 2008-07-06 06:31:26

on Sun Jul 06 2008, "Steven Ross" <spreadsort-AT-gmail.com> wrote:

> I've uploaded a new integer_sort release to
> http://sourceforge.net/projects/spreadsort/, and attached the source to this
> email.
> This uses randomaccessiterators just like std::sort, 

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.

> 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

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com