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

Subject: Re: [boost] [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2014-11-10 09:29:07

2014-11-10 9:37 GMT+04:00 Edward Diener <eldiener_at_[hidden]>:

> The formal review of the Sort library by Steven Ross starts today,
> November 10 and is scheduled to continue through November 19th.
>
<...>

>      - What is your evaluation of the design?
>

API is good.

>      - What is your evaluation of the implementation?
>

Implementation is not tuned.

For example, take a look
here
https://github.com/spreadsort/sort/blob/master/include/boost/sort/detail/spread_sort_common.hpp#L110
and here
https://github.com/spreadsort/sort/blob/master/include/boost/sort/detail/spread_sort_common.hpp#L116
.
Memory allocations occur at those points, however they could be easily
avoided. Here's a typical use case of `size_bins` function:
https://github.com/spreadsort/sort/blob/master/include/boost/sort/detail/string_sort.hpp#L170.

Using a stack based buffer would significantly improve sort times on small
datasets.

     - What is your evaluation of the documentation?
>

OK

>      - What is your evaluation of the potential usefulness of the
>        library?
>

Useful.

>      - Did you try to use the library?  With what compiler?  Did you
>        have any problems?
>

Have not used it.

>      - How much effort did you put into your evaluation? A glance? A
>        quick reading? In-depth study?
>

Quick reading.

>      - Are you knowledgeable about the problem domain?
>

Not a pro in radix based sorts.

>
> And finally, every review should attempt to answer this question:
>
>      - Do you think the library should be accepted as a Boost library?
>

Not in its current state. And not as a separate library. This must be a
part of Boost.Algorithm library.

This library must be accepted only after some good optimization. As a
result, I'd like to see this library outperforming std::sort even on small
datasets (~150 elements). At the current point std::sort and sort from the
subject library differ on some constant value (see
graph/windows_integer_sort.htm or graph/windows_string_sort.htm), not
O(n*log(n)) vs O(n*log(k/s+s)).

-- 
Best regards,
Antony Polukhin