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); > > } > > > >