From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by sourceware.org (Postfix) with ESMTP id 66D1A39F8424 for ; Fri, 6 Nov 2020 01:31:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 66D1A39F8424 Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-108-sVysTzv3O3OB7pcs2Eac7w-1; Thu, 05 Nov 2020 20:31:27 -0500 X-MC-Unique: sVysTzv3O3OB7pcs2Eac7w-1 Received: by mail-qk1-f197.google.com with SMTP id x2so2239435qkd.23 for ; Thu, 05 Nov 2020 17:31:27 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:date:to:cc:subject:in-reply-to:message-id :references:mime-version; bh=Vzrz1OrQvTV3Q48M2hfgSkmD9NxfsMnDslT+u/hHF1s=; b=G076njqSe6hj+dsSJQymgxJ126m8QFbjE6be3Ht3a/EjJshDsCSIhVOtzWExxMHV6N Pck7MNxTXbpPwggAOTPf4yvE1Gq7j1vDEDBvdt1m8BiUB02LZXElBoqA7J1iHRdyErH1 WMkLvQoK59NnKlmOBJ5r2Hds1a243Tpsij4IK1lAg32/Q4gDN97Wlwo0xRUvbfNYZoYd D5topTomTuHHcnX8f354sV+VYncusOGmhojFnsA7a+2IxTMOq3BXR7MV6dHoLTDiJQsZ VA74CnZtvHY1uFoV7vG13eWzduMpazVqz5ddbWGrieY8OdPBldunQvVZ3+R701IncIMh s9eA== X-Gm-Message-State: AOAM531Q1DK0A89gwQ2qO7jqyCw7Pw6/SDBsmod58OO430yB96t5uh5p 0ca0k1xfX+fu+NhH63m4mbOOvpMC0KehYzlW/XUEK0O8/We25mqNvKO8FNIMF97PbkweWQqBchu VXR8kHehU7K62HuYc+g== X-Received: by 2002:a37:98c7:: with SMTP id a190mr2458496qke.471.1604626286548; Thu, 05 Nov 2020 17:31:26 -0800 (PST) X-Google-Smtp-Source: ABdhPJxc0dZybeqr5aR5TZsCkmG++pd27QZ3R2DBhcAJZnhdbxRxxTDVyBrUN2F4ITtVMVOPfj7AnQ== X-Received: by 2002:a37:98c7:: with SMTP id a190mr2458476qke.471.1604626286235; Thu, 05 Nov 2020 17:31:26 -0800 (PST) Received: from [192.168.1.130] (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id n35sm1065346qtc.55.2020.11.05.17.31.25 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 05 Nov 2020 17:31:25 -0800 (PST) From: Patrick Palka X-Google-Original-From: Patrick Palka Date: Thu, 5 Nov 2020 20:31:24 -0500 (EST) To: Patrick Palka cc: Jason Merrill , gcc-patches@gcc.gnu.org Subject: Re: [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization In-Reply-To: <53fc78ba-78f0-73d8-643f-6af69826891@idea> Message-ID: <5294f3e6-7bfe-2ce9-b15b-36110e01a88@idea> References: <20201103204329.4069400-1-ppalka@redhat.com> <9bf0b275-3dc2-1d91-c959-eb9d110a9672@redhat.com> <53fc78ba-78f0-73d8-643f-6af69826891@idea> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-16.5 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 06 Nov 2020 01:31:33 -0000 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 > > > +{ > > > + 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_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::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 > > > { > > > 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); > > > } > > > > > > > >