Boost logo

Boost :

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
and here
Memory allocations occur at those points, however they could be easily
avoided. Here's a typical use case of `size_bins` function:

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

     - What is your evaluation of the documentation?


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


> - 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

Boost list run by bdawes at, gregod at, cpdaniel at, john at