Considering merge optimizations from Timsort in __move_merge_adaptive, __move_merge_adaptive_backward

[Joshua Marshall]

Humor me here, it looks like I was somehow dropped from the chain and I'm
not sure how to get it back on track.

It looks like you're focusing on the preferred sort implementation while I
was more focusing on if Timsort had a better general case approach to
merging runs of numbers.  It does a kind of exponential probing thing which
_should_ be about as fast for switching between merging sides often and
provide substantial benefits to long chains to be merged.

As for the actual implementations of std::sort, and std::stable_sort, isn't
introspective sort used and not quick sort + merge sort?  In any case, I'm
more interested in the std::stable_sort side of things and am nearly
finished with a Timsort implementation with is parallelizable but doesn't
outperform the current std::stable_sort I think in large part because of
the inplace merging.  For that matter, I can't seem to track down what the
actual sort type used for std::stable_sort is.



On Tue, Jul 3, 2018 at 7:30 PM, Carlos O'Donell <carlos@systemhalted.org>
wrote:

> On Tue, Jul 3, 2018 at 4:10 PM, 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.
> >
> > How would I get new code incorporated into this and make that decision
> > intelligently at compile time?  What would be a good way to add this
> > inplace_merge variant in?
>
> If you are looking specifically at std::inplace_merge, then you need to
> talk
> to the GCC developers, since libstdc++ is part of GCC.
> Please see: https://gcc.gnu.org/
>
> If you are interested in similar strategies for the C library, then you
> can look
> at the qsort() API, which can be implemented in any way really as long as
> it meets the API requirements (and is written in C). In glibc you might
> use a
> tunable to switch between one algorithm and another. You can see this
> implementation in stdlib/qsort.c in glibc, which does implement quicksort.
>
> Cheers,
> Carlos.
>