Re: [boost] Proposed templated integer_sort

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

I've added support for functors and verified it with my keyplusdatasample.c,
available from http://sourceforge.net/project/showfiles.php?group_id=229739(spreadsort
project).
I've also attached the updated integer_sort source.

Some design decision notes, which I'd welcome comments on:
I'm using pointers to iterate over the bins where I can safely do so
(everywhere but recursion).
For some pointer values, the bins pointer can be offset by subtracting
div_min from it ahead of using it for bin lookups.  This shows a noticeable
speed improvement (around 2%), but requires checking whether this offset is
safe to do, is a hack, and requires an if/else with largely duplicate code.
My conclusion is that such a hack is not appropriate for Boost code.
One disadvantage I found with the 3-way swap is that it requires a public
default constructor data_type() to be efficient.  If I code it so that it
only uses a copy constructor (by moving the creation of tmp inside the if
and else, and thus making most of the code dependent upon the conditional
check), it is substantially slower.  Some object models deliberately
eliminate the public default constructor.  To stay more general, should I
use the conventional 2-way swap approach, even though it is slightly (around
1%) slower?
I'm only using constructs that compile on my old g++ compiler.  That means I
can't use some of the newer additions to the standard, but I'm doing this in
the interest of being able to compile on as many systems as possible.
After all my optimizations, the impact of pointers vs. random access
iterators has increased as a percentage of runtime (it's over 10% now).  I'd
be interested to hear if this issue is visible on other systems, or just
mine, and other suggestions for what might be the problem.  I tried an
earlier suggestion of a compiler option, and it had no speed impact, though
that might be because my compiler treats that option differently.

I'll start working on float_sort now.