Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19

Subject: Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19
From: Vladimir Prus (vladimir_at_[hidden])
Date: 2014-11-10 11:31:58

On 11/10/2014 07:15 PM, Peter Dimov wrote:
> Vladimir Prus wrote:
>> If I see that function whatever_sort implements an algorithm from paper N, with 200 citations, then I can assume enough people reviewed
>> the algorithm. If that function implements an adaptation, then I'm not really sure what complexity I can expect.
>
> ...
>
>> So the question, is who is is qualified to review your algorithm as an algorithm - you know, formal proof of correctness, formal
>> complexity estimates, tests and statistical validity of them, and the quality relative to other existing algorithms. I would not think
>> it's a job for Boost.
>
> Demanding that the library be backed by a paper containing formal proof of correctness, formal complexity estimates, and 200 citations,
> strikes me as grossly unfair.
>
> We've never done this to any library under consideration. Had we done so, none of them would've passed.

I don't think we ever had a library whose primary value was algorithmic improvement, where the algorithm
was also developed by library author.

For many libraries, algorithms and complexities are implementation details. For this one, its the reason
for the library to exist, and the presented performance charts only demonstrate constant factor difference
with std::sort with old compiler and old CPU.  It seems quite fair to ask that the main selling point of a
library is well justified.

-- 
Vladimir Prus
CodeSourcery / Mentor Embedded
http://vladimirprus.com