Typically we do not standardize particular implementations or algorithms.
We standardize interfaces.

By selecting the semantics and requirements of interfaces, we control
implementation options without dictating a particular path.

It would be helpful to separate description of the proposed new sorting
interface from a description of how it might be implemented.

On Sat, Jun 27, 2020, 19:10 Matthew Bentley via SG14 <sg14_at_[hidden]>
wrote:

> Hi all,
> so,
> on Jens' suggestion I split the sort technique out of plf::colony, and
> then improved it so it was more efficient with it's use of memory.
> That's been released now here:
> https://plflib.org/indiesort.htm
>
> And the benchmarks for it on various container types are here:
> https://plflib.org/benchmarks_haswell_gcc.htm#sort
>
>
> My question is whether it's worth pursuing this in a paper as an
> additional algorithm for the standard library. I'd like your opinions as to
> why/why not.
>
> The basic benefits of the algorithm are:
> * You get a sort to use with non-random-access containers/iterators, like
> colony and std::list - there are currently no sort algorithms in the
> standard library which sort non-random-access iterators - aside from
> std::list's internal sort function
> * Better sort performance for random-access containers/arrays/iterators
> and types larger than 152 bytes (average +130% with vector and 496 byte
> structs), vs std::sort.
> * Better sort performance for std::list with types smaller than 272 bytes
> (average +28%), vs it's own internal sort(). Although std::list would be
> greatly improved to have a new function of it's own based on the same
> concept, as that could just write next/previous pointers instead of
> relocating elements.
>
>
> The downsides are:
> * increased temporary memory use: (N * (sizeof(T *) + sizeof(size_t)))
> * decreased performance for random-access containers with types smaller
> than 152 bytes. Both this and memory usage for random access ranges this
> may be improved in a specialization for random-access iterators, but I
> haven't implemented or tested that theory yet
> * current implementation uses std::sort internally - I'm pretty sure the
> algorithm could be improved somehow if the current gather and sort phases
> (possibly scatter phase too) were combined in a single algorithm
>
> At the moment the existing implementation could be improved by allowing
> the user to specify an alternative sort algorithm without use of macros,
> but I couldn't figure it out.
> It could also be improved by being implemented as allocator-aware. That
> may happen at some point.
>
> Anyway.
> Your thoughts?
> M@
> _______________________________________________
> SG14 mailing list
> SG14_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/sg14
>