Re: [boost] sorting library proposal (Was: Review Wizard Status Report for June 2009)o

Subject: Re: [boost] sorting library proposal (Was: Review Wizard Status Report for June 2009)o
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-06-03 12:43:13

On Wed, Jun 3, 2009 at 9:10 AM, Simonson, Lucanus J <
lucanus.j.simonson_at_[hidden]> wrote:

> That leaves what consitutes a reasonable degree of assurance that the code
> implements the algorithm.  In my work I put a lot of effort into validation
> of things that are often hard to validate.  Sorting is embarrasingly easy to
> validate because the correct output is well defined and correct algorithms
> for getting the correct output are easy to come by.  Unit tests that
> demonstrate correctness of the code on pseudo exhastive test cases should be
> easy for Steven to provide.  I think there is very little chance of him
> getting a sorting algorithm that doesn't sort into boost no matter how badly
> the review is bungled, and I doubt the review will be bungled at all.

I currently use an approach of generating large files of pseudo-random
numbers with between 1 and 32 random bits, and running many different sample
tests on these.
I could add some unit tests for crazy cases too; I guess I might as well
create the "ALR breaker" worst-case testcase, among others.  My current
"unit" tests other than for random data are for sorting sorted data (a task
it performs quickly), and for sorting mostly-sorted data (a task it performs
about as well or slightly slower than std::sort).  I'll see if I can think
of others, but if people have suggestions, I'd be happy to include them.

I eliminate NANs and -0.0s from my tests because std::sort orders them
arbitrarily (I change them to 0s in the tests); is that a problem?  This was
discussed before, and the only response was someone saying that I shouldn't
have to worry about them.  float_sort will order them in its radix-based
portion based upon their cast integer value (which for -0.0 is just less
than 0.0), but then when std::sort is called it will order them arbitrarily
in its sub-sort.

> My only concern is that the cast from integer to floating point be done in
> a way that won't break when the code is ported.  I'm pretty sure Steven has
> that covered because I followed the discussion about it a while back, but
> I'll double check when the review comes up that such conversions are only
> enabled when a test that they will work for a given platform exists in the
> unit tests and that the default behavior is to fall back on std::sort when
> there is no certaintly that conversion will work.
>

Currently it will fire a compile-time assertion if the cast won't work.  I
can change that to a warning and an enable_if, so it will do what you
suggest.

It sounds like I have significantly more work to do before this is ready for
review; it'll probably take me at least a month to get all the requested
changes in (including doc updates, especially a thorough explanation and
proof of worst-case performance).