Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-04-25 04:02:41

Thanks for the tip Steve, but I'm not sure how to tell for sure that I'm in
Windows inside PERL.  The .tunelog works for now, without adding excessive
clutter.

I've finished a set of default constants, that provides a roughly 5%
performance penalty on Windows, and roughly 10% performance penalty versus
optimal settings on MacOSX.  That avoids the hassles of the user needing to
tune for themselves, and I figure it's good enough.

I have a final draft up on the boost vault named algorithm_sorting.zip.

These were my findings:
On Mac OSX, I get a 60% to 3X speedup for on large data sets, depending on
the problem type.  floats and integers sorted at comparable speeds.

On Windows:
integer_sort is about 20% faster than std::sort.
integer_sort on already-sorted data takes 3X as long to run as std::sort.
The pattern of these differences, where integer_sort is roughly 50% faster
on highly random data, but (relatively) slower on low-randomness data,
suggests that std::sort on Windows has some form of optimization for
mostly-sorted data.  Worst-case performance is 50% better for integer_sort
than std::sort.  integer_sort has the better average and worst-case
performance, but std::sort has superior best-case performance.
sorting an integer key plus string data, integer_sort is 3.5X as fast as
std::sort.  This is because integer_sort uses asymptotically fewer swaps,
and swaps take longer the larger the data type.

float_sort is roughly 7X faster than std::sort, but this follows a similar
pattern to integer_sort:
The worst case for float_sort is 13X as fast as std::sort is on the same
case.  float_sort is faster on all tests except the one where all data
elements are identical, the best-case for both algorithms.  Because of this
huge difference in performance (which I believe is due to extremely slow
float comparisons on Windows) the ideal LOG_CONST for float_sort on Windows
is probably 1 (where on Mac OS, it's about the same as for integer_sort, the
default of 4).
I found that floating-point sorting with std::sort on a new Windows system
took as much as 50X longer than on an old Macintosh Altivec (G4) laptop, so
it's no so much that float_sort is fast as std::sort is slow.

string_sort is roughly 2.3X faster than std::sort.  This doesn't seem to
follow any particular pattern; it's consistently faster.

Comments and suggestions are welcome.  I should be ready for a formal
submission soon.

Steven Ross

On Sun, Apr 19, 2009 at 6:53 AM, Steven Watanabe <watanabesj_at_[hidden]>wrote:

> AMDG
>
> Steven Ross wrote:
>
>> To make the tuning script cross-platform, I send undesired output to a
>> .tunelog file (/dev/null doesn't work on windows)
>>
>>
>
> On windows you can use >nul.
>
>
> In Christ,
> Steven Watanabe
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>