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