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: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-06-03 12:10:31

Edouard A. wrote:
>>> What matters is that a reasonable degree of assurance regarding
>>> correctness and performance can be given. This concerns the library
>>> as a whole, not just whatever algorithm(s) it may use.
>> 
>> So how do we define "reasonable degree of assurance"?
> 
> Defining it would be like building Mathematics all over again... ;)
> 
> We can however agree on some guidelines I guess.
> 
> Actually, I think when a reviewer has got a doubt about the underlying
> algorithm, he/she has got no choice but to carefully review the
> algorithm itself.
> 
> Formality is a tool, not a goal.

I was skeptical of the algorithm itself originally, but Steven's persistence in explaining it eventually provided me with enough information to assure me that the algorithm is sound and does what he says it does.

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.

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.

Regards,
Luke