From: Joshua Marshall <jrmarsha@mtu.edu>
To: "Carlos O'Donell" <carlos@systemhalted.org>,
adhemerval.zanella@linaro.org
Cc: libc-help@sourceware.org
Subject: Re: Considering merge optimizations from Timsort in __move_merge_adaptive, __move_merge_adaptive_backward
Date: Fri, 20 Jul 2018 03:48:00 -0000 [thread overview]
Message-ID: <CANV=t7nhSxdaYqFknQ8ZrHo7s8G8_vRD5igcHEpd9RJi1J48yg@mail.gmail.com> (raw)
In-Reply-To: <CAE2sS1hv9TH4oSHMf6VyZB6r_K6RbUsvcxaE05W6-X14wmTJWA@mail.gmail.com>
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.
>
next prev parent reply other threads:[~2018-07-20 3:48 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-07-03 4:16 jrmarsha
2018-07-03 20:04 ` Carlos O'Donell
2018-07-03 20:10 ` jrmarsha
2018-07-03 23:30 ` Carlos O'Donell
2018-07-04 12:08 ` Adhemerval Zanella
2018-07-20 3:48 ` Joshua Marshall [this message]
2018-07-23 20:57 ` Carlos O'Donell
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CANV=t7nhSxdaYqFknQ8ZrHo7s8G8_vRD5igcHEpd9RJi1J48yg@mail.gmail.com' \
--to=jrmarsha@mtu.edu \
--cc=adhemerval.zanella@linaro.org \
--cc=carlos@systemhalted.org \
--cc=libc-help@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).