On 11/5/20 8:31 PM, Patrick Palka wrote:
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).
True. But if doing this is a big speedup for satisfaction, I imagine it
would also be a big speedup for subsumption.
Maybe use the assumption and if CHECKING_P, make sure that the
structural comparison matches the pointer comparison?
The v2 patch is OK for now, this question doesn't need to block it.
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.
Makes sense.
/* 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);
}
