Re: [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization

[Patrick Palka <ppalka@redhat.com>]

On Thu, 5 Nov 2020, Patrick Palka wrote:

> 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).

On second thought, if we make the hasher in logic.cc and other places
(e.g. add_constraint and constraints_equivalent_p) take advantage of
pointer-based identity for ATOMIC_CONSTR, then we'd be relying on the
uniqueness assumption in a crucial way rather than just relying on it in
the satisfaction cache in a benign way that doesn't affect the semantics
of the program if the assumption is somehow violated (we just get a
cache miss if it is violated).

So it seems to me it'd be better to not infect other parts of the code
with this assumption, and to keep it local to the satisfaction cache,
so as to minimize complexity.  So I suppose we should go with combining
these two "structural" hashers.

> 
> > 
> > > +/* 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);
> > >     }
> > > 
> > 
> > 
>