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
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.
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
On Sun, Apr 19, 2009 at 6:53 AM, Steven Watanabe <watanabesj_at_[hidden]>wrote:
> 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:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk