Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-01-14 16:39:51

In reply to Steve Watanabe:
Thanks.  I'd already tried bjam, but what I figured out is that a link
error:
/usr/bin/ld: unknown flag: --start-group
is preventing the executable from being built, so the tests don't run.
So instead I link the .o file that it was built by bjam, run it, and it runs
my tests.
 This ought to just work.  I presume that you are using gcc.  What OS?
I am using gcc 4.0.1 on Mac OSX10.4 (PPC).  I attempted to install gcc4.3.2,
and it failed, even though I added the libraries it stated it was dependent
upon.  Apple only provides binaries past gcc4.0 for 10.5, so I'm inclined to
believe that 10.4 is missing necessary support in the OS for the latest gcc
libraries.

On Wed, Jan 14, 2009 at 9:51 AM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:

>
> <http://www.boostpro.com/vault/index.php?action=downloadfile&filename=algorithm_sorting.tar.gz&directory=&>Some
> first impressions follow.  I will try to find time to look at it more
> carefully at some point but I can't promise.
>
> You seem to have quite a lot of code that's duplicated for the functor and
> non-function versions.  Can't this be eliminated by using e.g. std::less as
> a default for the compare template parameter?  (Isn't this what std::sort
> does?)

In the version of STL I downloaded to look at, there is the functor version
of std::sort, and the non-functor version.  The code is entirely duplicated
at all levels where comparison are used, because the functor adds overhead
(it takes up space on the stack, if nothing else).  This overhead is small
(around 2-5%), but measurable.  Considering how much effort I went to
squeezing out every 1% improvement I could, I would consider it wasteful to
accept that kind of penalty just to reduce code size in the library.  I've
combined functions between functor/non-functor versions where I could
without sacrificing measurable performance.  My philosophy is that I (as the
library developer) go to the effort to make things as fast and flexible as
possible, so that those who include the library don't have to worry about
any of that.

> I suggest that you get rid of the tab characters in the source.  I
> personally find your lines rather long, but that's a matter of taste.

I'll make sure to remove the ones I missed, thanks for the reminder.  I'll
also shorten lines over 80 characters.

> I think you can use things like typename RandomAccessIter::value_type
> instead of passing *first in order to determine data_type.

I tried that, but it didn't compile on my system (MacOSX PPC gcc4.0.1).
*first works just the same, though I agree, ::value_type is prettier.  I'll
see if I can find out how to make it work on my system, and thus hopefully
everybody's system, but no guarantees.

> I'm not sure how useful your functor-versions are since they still seem to
> depend on the "integer-ness" or "float-ness" of the sorted type.  Apart from
> sorting backwards, what use cases are there?  Using functors would be more
> useful if it let you sort types that are neither integers nor floats; for
> example, fixed-point types or pointers-to-integers or structs containing a
> key field to be sorted on.

Did you look at my KeyPlusData sample or the index.html?
integer_sort can sort anything with an integer or integer-convertible key
float_sort can sort anything with a floating-point key
string_sort can sort anything with a string key, including (though not
tested yet) wide character strings
That's what the functor versions are there for: sorting classes or
structures based upon a key.  All you have to do is define the correct
functor.
I believe that most single-key data types can be sorted by one of these
three functions and the appropriate functors.
Fixed-point types can sort as an integer of the same size in bytes.  The
only real requirement is that they must return a data type that when
subtracted from an item of the same type returns something convertible to a
size_t, that if (b - a) < (c - a) then b < c, and that bitshifting works as
division by a power of two would, reducing the difference by a power of two
per shift.
Pointers-to-integers need a shift functor: *x >> offset; and a compare
functor *x < *y.
KeyPlusData shows an example of a struct with a key field.

>  I think that the key here is that you make assumptions about the return
> type of operator>> or the right_shift functor which are not true in those
> cases.  It may be that you just need to rename that functor and document
> what it needs to do.  I think it's really "get N bits from key".  I would
> have thought that the floating-point algorithm would just be an instance of
> the generic algorithm with custom functors, with a bit of specialisation to
> cope with the reverse-order-for-negatives thing.

Positive floats can be sorted just like integers, with the right functor.
Negative floats have to be sorted backwards.  I didn't see any efficient way
to write a functor to handle negative floats.  Hence, a mostly separate
algorithm, but positive float sorting shares code with integer_sort.
The nice thing about how I wrote float_sort is that it sorts floats almost
as fast as integers (I see differences of under 10%).

> One of the things that your string sort does is to not compare known-equal
> initial substrings.  Does anyone know if there is a variant of a
> conventional sort (e.g. quicksort) that does this?

I'm pretty sure that's a radix-sorting trick; it's incompatible with only
taking a comparison function, and requires paying attention to the radix
index.  Plenty of radix sorts do it.  The speedup I attained was on the
order of 5%; more than enough to be worth doing, but not a huge gain.
String comparisons are cache-friendly, so they're still fast relative to
swap operations on my test systems.

> Some more documentation of the performance benefit would be useful.  How
> about some graphs?
>

Okay.  It will vary substantially from system to system (such as my odd 28X
float_sort speedup on Cygwin, where on my system it's roughly 2X as fast, or
the minimal speed improvement of string_sort on Cygwin, vs 2X on my system),
across different compilers, and depending upon the data distribution.  I
could graph runtime vs. file size on evenly distributed random data on
multiple platforms for each of the 3 algorithms relative to std::sort.  Does
that sound like what you're looking for?
My experience is that Spreadsort tends to be a little faster on unevenly
distributed data than evenly distributed data, as it starts bucketsorting;
my performance tests include various distributions, but they take a long
time to run and it would be impractical and probably confusing to the reader
to graph their results.

I'll look at std::numeric_limits<>::is_iec559 and see if that does what I
want.