Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2008-12-13 11:28:02

On Wed, Jul 30, 2008 at 10:46 AM, Steven Watanabe <watanabesj_at_[hidden]>wrote:

> I'm thinking of something more like:
>
> template<class T>
> struct default_right_shift;
>
> template<>
> struct default_right_shift<float> {
>   typedef rightshift type;
> };
>
>
> Thanks for the suggestion Steve.  I thought about it, and decided that
asking the user to create a template for every override they wish to make is
probably too much for the average user.  Instead, I created a float_sort
call that takes first, last, and a data type to cast to.  Performance is not
significantly superior to the one that takes a functor, and I added a
wrapper casting_float_sort that casts the data type to an int (so the user
only needs to pass first and last).  Pointer type-casts that float_sort is
dependent upon must be used with caution.

I also created a string_sort which correctly handles embedded null
characters, with functor and reverse versions.  I wonder if it would be a
good idea to create a cstring_sort that treats a null character as a string
termination (and handles NULL ptrs), which should be noticeably faster?
This would enable an apples-to-apples comparison of speed with highly
optimized c-string sorting algorithms.  That said, I'm not sure whether
cstring_sort is appropriate for boost.

I've made some new optimizations.  Integer_sort and float_sort are both
roughly twice as fast as std::sort on my test suite of randomized data with
different distributions, and have roughly theta(n * square_root(log(n)))
performance, so it slowly improves its relative speed as data sets get
larger, with a crossover point of roughly 1000 elements.  String_sort has
O(n * length) runtime much like Postal Sort (which it is similar to), versus
O(n * log(n) * length) for std::sort, so though it has significant constant
overhead, it rapidly becomes faster as data sets become larger, being a
little less than twice as fast on random data, and roughly twice as fast on
real text (Dickens novel).  string_sort sacrifices a small constant overhead
on random data for superior performance in situations where there are
multiple character long matching substrings.  This does not impact its
asymptotic performance, better or worse.
String_sort is not appropriate for characters over 2 bytes in size, and is
optimized for 1-byte characters.
The runtime crossover point for string_sort is roughly 32000 elements.

All these algorithms are in-place, with less than linear memory overhead.

Testing was done on 10 million element data sets for integer_sort and
float_sort on OSX.  For string_sort, the data read in was 40MB in size, but
it was converted to strings of varying lengths, and additional embedded
nulls were added for testing, so the actual data set size is larger.

I encountered a compiler optimization bug with float_sort (but not
integer_sort) on Cygwin with -O2 and -O3 options.  Does anyone know the best
place to report that?  For now, I'm having float_sort call std::sort on
Cygwin.

I'm still running regression tests and doing a little commenting and
testcase cleanup, but once all that is done my Spreadsort-based library
suite should be done.  Does this sound like something that is worth adding
to Boost?  I plan to upload source here when I'm done testing.