On Wed, Jun 3, 2009 at 9:10 AM, Simonson, Lucanus J < lucanus.j.simonson@intel.com> 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).