
Boost : 
Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 20090425 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 alreadysorted 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 lowrandomness data,
suggests that std::sort on Windows has some form of optimization for
mostlysorted data. Worstcase performance is 50% better for integer_sort
than std::sort. integer_sort has the better average and worstcase
performance, but std::sort has superior bestcase 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 bestcase 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 floatingpoint 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 crossplatform, 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
>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk