public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Jakub Jelinek <jakub@redhat.com>
To: Alexander Monakov <amonakov@ispras.ru>
Cc: gcc-patches@gcc.gnu.org
Subject: Re: [PATCH 0/2] Introduce gcc_qsort
Date: Thu, 10 May 2018 17:35:00 -0000	[thread overview]
Message-ID: <20180510172420.GK8577@tucnak> (raw)
In-Reply-To: <20180510155641.2950-1-amonakov@ispras.ru>

On Thu, May 10, 2018 at 06:56:39PM +0300, Alexander Monakov wrote:
> Overall the new implementation is roughly 30% faster compared to Glibc qsort,
> with 2x or more speedup for cases with tiny element count. I see one instance
> where the new approach is significantly (1.5x) slower: it is ipa-icf.c:
> sort_congruence_class_groups_by_decl_uid. It sorts a big array (1500 entries)
> and needs 14 indirect loads just to reach values to compare, so when branch
> prediction manages to guess correctly, it allows to overlap execution of two
> comparators and better hide their cache miss latency.
> 
> Overall GCC spends about 0.3% time under qsort, but this doesn't automatically
> mean that this brings a 0.1% speed improvement: it may be larger or smaller
> depending on how new code affects cache behavior and branch predictors in
> other code, and it's not trivial to measure precisely.
> 
> I can go into more detail about measured stats if there's interest :)
> 
> Makefile.in changes are separated to patch 2 in the hope it'd make review
> easier, but the two patches will need to be applied together.
> 
> Bootstrapped/regtested on x86-64, OK for trunk?

Have you gathered some statistics on the element sizes and how often they
appear in qsort calls (perhaps weighted by n*log(n) of the element count)
across bootstrap+regtest?

glibc uses indirect sorting (sorts pointers to the elements or indexes and
just reshuffles at the end) and has special case for the most commonly used
small element size (4/8).  With C++ templates you could achieve that even
without macros, just by instantiating the mergesort and its helpers for the
few common cases.  Or is that not worth it (as in, we never sort really
large (say > 32 bytes) element sizes and the 4 or 8 bytes long element sizes
aren't common enough to see benefit by using constant size memcpy for those
cases?

	Jakub

  parent reply	other threads:[~2018-05-10 17:24 UTC|newest]

Thread overview: 24+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-10 15:57 Alexander Monakov
2018-05-10 15:57 ` [PATCH 2/2] gcc_qsort: build system changes Alexander Monakov
2018-05-11  9:32   ` Richard Biener
2018-05-10 17:01 ` [PATCH 1/2] gcc_qsort: source code changes Alexander Monakov
2018-05-10 17:01   ` David Malcolm
2018-05-10 17:44   ` Richard Biener
2018-05-10 18:08     ` Alexander Monakov
2018-05-10 18:57       ` DJ Delorie
2018-05-11 12:03   ` Richard Biener
2018-05-11 13:12     ` Alexander Monakov
2018-05-13 23:56   ` H.J. Lu
2018-05-14  8:44     ` Alexander Monakov
2018-05-14  9:08       ` Richard Biener
2018-05-10 17:35 ` Jakub Jelinek [this message]
2018-05-10 17:48   ` [PATCH 0/2] Introduce gcc_qsort Alexander Monakov
2018-05-10 17:43 ` Richard Biener
2018-05-10 17:57   ` Alexander Monakov
2018-05-11 10:35   ` Segher Boessenkool
2018-05-11 10:44     ` Alexander Monakov
2018-05-11 12:00       ` Segher Boessenkool
2018-05-11 12:16         ` Alexander Monakov
2018-05-11 12:52           ` Segher Boessenkool
2018-05-11 16:54           ` Eric Botcazou
2018-05-11 11:17     ` Jakub Jelinek

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=20180510172420.GK8577@tucnak \
    --to=jakub@redhat.com \
    --cc=amonakov@ispras.ru \
    --cc=gcc-patches@gcc.gnu.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).