From: Patrick Palka <ppalka@redhat.com>
To: Jason Merrill <jason@redhat.com>
Cc: Patrick Palka <ppalka@redhat.com>, gcc-patches@gcc.gnu.org
Subject: Re: [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization
Date: Thu, 5 Nov 2020 18:00:06 -0500 (EST) [thread overview]
Message-ID: <53fc78ba-78f0-73d8-643f-6af69826891@idea> (raw)
In-Reply-To: <9bf0b275-3dc2-1d91-c959-eb9d110a9672@redhat.com>
On Thu, 5 Nov 2020, Jason Merrill wrote:
> On 11/3/20 3:43 PM, Patrick Palka wrote:
> > Profiling revealed that sat_hasher::equal accounts for nearly 40% of
> > compile time in some cmcstl2 tests.
> >
> > This patch eliminates this bottleneck by caching the ATOMIC_CONSTRs
> > returned by normalize_atom. This in turn allows us to replace the
> > expensive atomic_constraints_identical_p check in sat_hasher::equal
> > with cheap pointer equality, with no loss in cache hit rate.
> >
> > With this patch, compile time for the cmcstl2 test
> > test/algorithm/set_symmetric_difference4.cpp drops from 19s to 11s with
> > an --enable-checking=release compiler.
> >
> > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK for
> > trunk?
> >
> > gcc/cp/ChangeLog:
> >
> > * constraint.cc (struct atom_hasher): New descriptor class for a
> > hash_table. Use it to define ...
> > (atom_cache): ... this.
> > (normalize_atom): Use it to cache ATOMIC_CONSTRs when not
> > generating diagnostics.
> > (sat_hasher::hash): Use htab_hash_pointer instead of
> > hash_atomic_constraint.
> > (sat_hasher::equal): Test for pointer equality instead of
> > atomic_constraints_identical_p.
> > ---
> > gcc/cp/constraint.cc | 37 ++++++++++++++++++++++++++++++++++---
> > 1 file changed, 34 insertions(+), 3 deletions(-)
> >
> > diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> > index b6f6f0d02a5..ce720c641e8 100644
> > --- a/gcc/cp/constraint.cc
> > +++ b/gcc/cp/constraint.cc
> > @@ -710,6 +710,25 @@ normalize_concept_check (tree check, tree args,
> > norm_info info)
> > return normalize_expression (def, subst, info);
> > }
> > +/* Hash functions for ATOMIC_CONSTRs. */
> > +
> > +struct atom_hasher : default_hash_traits<tree>
> > +{
> > + static hashval_t hash (tree atom)
> > + {
> > + return hash_atomic_constraint (atom);
> > + }
> > +
> > + static bool equal (tree atom1, tree atom2)
> > + {
> > + return atomic_constraints_identical_p (atom1, atom2);
> > + }
> > +};
>
> This is the same as constraint_hash in logic.cc; either they should be
> combined, or (probably) the hash table in logic.cc should be changed to also
> take advantage of pointer equivalence.
Ah, I forgot about the existence of this hasher. Consider this hasher
changed to take advantage of the pointer equivalence (I'll post a
revised and tested patch later today).
>
> > +/* Used by normalize_atom to cache ATOMIC_CONSTRs. */
> > +
> > +static GTY((deletable)) hash_table<atom_hasher> *atom_cache;
>
> If we're relying on pointer identity, this can't be deletable; if GC discards
> it, later normalization will generate a new equivalent ATOMIC_CONSTR, breaking
> the uniqueness assumption.
But because no ATOMIC_CONSTR is ever reachable from a GC root (since
they live only inside GC-deletable structures), there will never be two
equivalent ATOMIC_CONSTR trees live at once, which is a sufficient
enough notion of uniqueness for us, I think.
>
> > /* The normal form of an atom depends on the expression. The normal
> > form of a function call to a function concept is a check constraint
> > for that concept. The normal form of a reference to a variable
> > @@ -729,7 +748,19 @@ normalize_atom (tree t, tree args, norm_info info)
> > /* Build a new info object for the atom. */
> > tree ci = build_tree_list (t, info.context);
> > - return build1 (ATOMIC_CONSTR, ci, map);
> > + tree atom = build1 (ATOMIC_CONSTR, ci, map);
> > + if (!info.generate_diagnostics ())
> > + {
> > + /* Cache the ATOMIC_CONSTRs that we return, so that sat_hasher::equal
> > + later can quickly compare two atoms using just pointer equality. */
> > + if (!atom_cache)
> > + atom_cache = hash_table<atom_hasher>::create_ggc (31);
> > + tree *slot = atom_cache->find_slot (atom, INSERT);
> > + if (*slot)
> > + return *slot;
> > + *slot = atom;
> > + }
> > + return atom;
> > }
> > /* Returns the normal form of an expression. */
> > @@ -2284,13 +2315,13 @@ struct sat_hasher : ggc_ptr_hash<sat_entry>
> > {
> > static hashval_t hash (sat_entry *e)
> > {
>
> We could use a comment here about why we can just hash the pointer.
Will do. The subsequent patch ("Use two levels of caching in
satisfy_atom") also adds
+ /* Atoms with uninstantiated mappings are built in normalize_atom.
+ Their identity is determined by their pointer value due to
+ the caching of ATOMIC_CONSTRs performed therein. */
to sat_hasher::equal, but it could use repeating in sat_hasher::hash.
>
> > - hashval_t value = hash_atomic_constraint (e->constr);
> > + hashval_t value = htab_hash_pointer (e->constr);
> > return iterative_hash_template_arg (e->args, value);
> > }
> > static bool equal (sat_entry *e1, sat_entry *e2)
> > {
> > - if (!atomic_constraints_identical_p (e1->constr, e2->constr))
> > + if (e1->constr != e2->constr)
> > return false;
> > return template_args_equal (e1->args, e2->args);
> > }
> >
>
>
next prev parent reply other threads:[~2020-11-05 23:00 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-11-03 20:43 Patrick Palka
2020-11-05 20:45 ` Jason Merrill
2020-11-05 23:00 ` Patrick Palka [this message]
2020-11-06 1:31 ` Patrick Palka
2020-11-06 20:26 ` Jason Merrill
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=53fc78ba-78f0-73d8-643f-6af69826891@idea \
--to=ppalka@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jason@redhat.com \
/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).