Re: [boost] [sort] Timsort review reminder

Subject: Re: [boost] [sort] Timsort review reminder
From: Paul A. Bristow (pbristow_at_[hidden])
Date: 2017-06-07 08:55:49

> -----Original Message-----
> From: Boost [mailto:boost-bounces_at_[hidden]] On Behalf Of Klaim - Joël Lamotte via Boost
> Sent: 06 June 2017 20:09
> To: Boost Developers List
> Cc: Klaim - Joël Lamotte
> Subject: Re: [boost] [sort] Timsort review reminder
> 
> On 6 June 2017 at 17:40, Zach Laine via Boost <boost_at_[hidden]> wrote:
> 
> > Please provide a link to online documentation, if if one exists.  All I've
> > been able to find so far is a paper and Doxygen reference docs.  I got that
> > much by cloning the GitHub repo (putting docs online somewhere will get you
> > a lot more reviewers :).  Did I miss it somewhere?
> >
> > Zach
> >
> > On Tue, Jun 6, 2017 at 10:09 AM, Steven Ross via Boost <
> > boost_at_[hidden]> wrote:
> >
> > > The review for C++ Timsort in Boost is ongoing and will continue through
> > > June 12.  I am the review manager.  The code can be found here:
> > > https://github.com/boostorg/sort/pull/12
> > > To merge it into a local copy of the Boost.Sort library:
> > > git checkout -b ZaMaZaN4iK-feature_branch/TimSort develop
> > > git pull https://github.com/ZaMaZaN4iK/sort.git \
> > > feature_branch/TimSort
> > >
> > > If you want to see a proposed version of the Sort library source with
> > > Francisco's changes and Timsort included, download the zip file
> > > <https://drive.google.com/file/d/0B4s-GPKYVV0jOGx5ckJUTkZzMWM/view?
> > > usp=sharing>.
> > > Feel free to compare flat_stable_sort with Timsort.
> > >
> > > Please answer these questions in reply to this thread:
> > >
> > >    1. What is your evaluation of the Timsort implementation?
> > >    2. What is your evaluation of the comments?
> > >    3. Did you try to use the library? With what compiler? Did you have
> > any
> > >    problems?
> > >    4. How much effort did you put into your evaluation? A glance? A quick
> > >    reading? In-depth study?
> > >    5. How familiar are you with the details of hybrid and stable sorts?
> > >    6. Would you actually use Timsort if it was in Boost.Sort?  If so, how
> > >    is it better than the next best alternative?
> > >    7. Do you think Timsort should be included in Boost.Sort?
> > >
> > >
> > > Please ask Alexander Zaitsev any questions you have about Timsort for
> > this
> > > review before submitting your final review.
> > >
> > > Thanks,
> > >
> > > Steven Ross
> > >
> >
> 
> I agree, a summary of what the hell is TimSort would be useful for
> potential reviewers.

It is totally unacceptable for there not to be any documentation at all (even if the Wikipedia article gives good details).

At the very least it should say "This is a C++ implementation of the referenced algorithm by Tim Peters."

I note this in the Wikipedia article

"Formal verification- 
In 2015, Dutch and German researchers in the EU FP7 ENVISAGE project found a bug in the standard implementation of Timsort.[8]"

I think we must have a comment on if this is 'fixed' - or ?

"GNU Octave's oct-sort.cc – the C++ implementation of Timsort used in GNU Octave"
are there any licensing issues from 'borrowing' from this code?

I see mention of documentation - is this intended to be merged into the main Boost.Sort documentation?

Paul

---
Paul A. Bristow
Prizet Farmhouse
Kendal UK LA8 8AB
[phone]