Re: Considering merge optimizations from Timsort in __move_merge_adaptive, __move_merge_adaptive_backward

["Carlos O'Donell" <carlos at systemhalted dot org>]

On Tue, Jul 3, 2018 at 12:16 AM, jrmarsha <jrmarsha@mtu.edu> wrote:
> Hello all,
>
> I've been implementing a new version of Timsort in C++ using more standard
> facilities.  One thing I've come across which adds a divide between a larger
> codebase and faster code is the implementation of std::inplace_merge with
> sufficient memory.  This goes to the specific functions
> __move_merge_adaptive, and __move_merge_adaptive_backward.  In particular,
> there is an optimization where each insertion searches for the maximum
> number of elements it can move.  A brief in context explanation is here:
> https://en.wikipedia.org/wiki/Timsort#Individual_merges .  Would such a
> trick have a place in glibc or is the overhead likely too great in the
> general case?

It's possible. We have a tunable framework for changing runtime
parameters like this based on application needs.  The interface only
allows you to make the choice once at startup. So it may not be
sufficient to meet the needs of all users. However some choice in this
area may be better than no choice.

Cheers,
Carlos.