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 [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 98D2C385736D for ; Fri, 10 Jun 2022 16:22:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 98D2C385736D Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-364-MQh0dp7nP-uUkulhDlA9sQ-1; Fri, 10 Jun 2022 12:22:18 -0400 X-MC-Unique: MQh0dp7nP-uUkulhDlA9sQ-1 Received: by mail-qk1-f199.google.com with SMTP id s11-20020a05620a254b00b006a6a23ff939so16401259qko.17 for ; Fri, 10 Jun 2022 09:22:18 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:subject :content-language:to:references:from:in-reply-to :content-transfer-encoding; bh=nFnXNMFy4uaAWDiGCeBm7BYIKBWvrY9897iEqizal3c=; b=NHkwDJOPsZobl9hfGIInw6ozSR7On2zKIwPhvhdBoByjsavLpphgS047uUTkqC9SPp 9D6HmF+Xkqg6LdGGKcMLUFHc73aoxXcPtNi3XxCRxT8AYrMawrjR6C5QZjKLHWLrOV/e q0jS06vNLU46pJlppaIawLejNdBxm1hvHZ8t3VZjPqnzNS0quop0Lnp2fNa3jApoq4Zz BqQ8/K4AeKlaQ6I2rPNna9peCWjcHSU/8UlG3yYPtoub6kJ6U63r1Rh6Wq/H6MKytlIU nFSlQdynbFtnc746HjYV5+5o+hnjJaWeCMeZO+VKHczXiTsq8yw7fVHVUPaVh/TvVIFR 0GEw== X-Gm-Message-State: AOAM530HJdsHxWCQYkP9LaPTFV3nghw8Fu2kixUe4Dkin7ctcik1kbE6 ItXGdkO1yDRynm2iCYjwizw8Uz5aFVENVrWvzo8Nrve/2O6INCndflbloy0oYqIKWqIlaJysSSM qokval5Xbo+kIzior+g== X-Received: by 2002:a05:622a:58c:b0:305:79a:f53 with SMTP id c12-20020a05622a058c00b00305079a0f53mr10983849qtb.601.1654878137473; Fri, 10 Jun 2022 09:22:17 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwK2fPvwOQS/OiOSrlTnNBpkXRUcqAXDiqO0lncgv6rrkeDOwgiq7ueDQgWdKUvnPz/NS4kKg== X-Received: by 2002:a05:622a:58c:b0:305:79a:f53 with SMTP id c12-20020a05622a058c00b00305079a0f53mr10983810qtb.601.1654878136905; Fri, 10 Jun 2022 09:22:16 -0700 (PDT) Received: from [192.168.1.100] (130-44-159-43.s15913.c3-0.arl-cbr1.sbo-arl.ma.cable.rcncustomer.com. [130.44.159.43]) by smtp.gmail.com with ESMTPSA id n64-20020a37bd43000000b006a60190ed0fsm20872514qkf.74.2022.06.10.09.22.16 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Fri, 10 Jun 2022 09:22:16 -0700 (PDT) Message-ID: Date: Fri, 10 Jun 2022 12:22:15 -0400 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.10.0 Subject: Re: [PATCH] c++: improve TYPENAME_TYPE hashing [PR65328] To: Patrick Palka , gcc-patches@gcc.gnu.org References: <20220610134020.1835431-1-ppalka@redhat.com> From: Jason Merrill In-Reply-To: <20220610134020.1835431-1-ppalka@redhat.com> X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-13.6 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, NICE_REPLY_A, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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, 10 Jun 2022 16:22:21 -0000 On 6/10/22 09:40, Patrick Palka wrote: > The reason compiling the testcase in this PR is so slow is ultimately > due to our poor hashing of TYPENAME_TYPE causing a huge amount of hash > table collisions in the spec_hasher and typename_hasher tables. > > In spec_hasher, we don't hash the components of a TYPENAME_TYPE at all, > presumably because TYPENAME_TYPE equivalence as determined by > structural_comptypes depends on whether the comparing_specializations > flag is set. This patch fixes this by setting comparing_specializations > from spec_hasher::hash, and making iterative_hash_template_arg hash the > relevant components of a TYPENAME_TYPE when this flag is set. > consistently. > > And in typename_hasher, the hash function doesn't consider the > TYPENAME_TYPE_FULLNAME, which this patch fixes accordingly. > > After this patch, compile time for the testcase in the PR is around > 34 seconds (10% faster than Clang). > > Bootstrapped and regtested on x86_64-pc-linux-gnu, does this look OK > for trunk? > > PR c++/65328 > > gcc/cp/ChangeLog: > > * decl.cc (typename_hasher::hash): Add extra overloads. > Use iterative_hash_object instead of htab_hash_pointer. > Hash the TYPENAME_TYPE_FULLNAME too. > (build_typename_type): Use typename_hasher::hash. > * pt.cc (spec_hasher::hash): Add two-parameter overload. > Set comparing_specializations around the call to > hash_tmpl_and_args. > (iterative_hash_template_arg) : > When comparing_specializations, hash the TYPE_CONTEXT > and TYPENAME_TYPE_FULLNAME. > (tsubst_function_decl): Use spec_hasher::hash instead of > hash_tmpl_and_args. > (tsubst_template_decl): Likewise. > (tsubst_decl): Likewise. > --- > gcc/cp/decl.cc | 26 +++++++++++++++++++------- > gcc/cp/pt.cc | 28 ++++++++++++++++++++++++---- > 2 files changed, 43 insertions(+), 11 deletions(-) > > diff --git a/gcc/cp/decl.cc b/gcc/cp/decl.cc > index 7f3b3c3c588..b7f624ca50b 100644 > --- a/gcc/cp/decl.cc > +++ b/gcc/cp/decl.cc > @@ -4007,14 +4007,27 @@ struct typename_hasher : ggc_ptr_hash > /* Hash a TYPENAME_TYPE. */ > > static hashval_t > - hash (tree t) > + hash (tree context, tree name, tree fullname) > { > - hashval_t hash; > + hashval_t hash = 0; > + hash = iterative_hash_object (context, hash); > + hash = iterative_hash_object (name, hash); I'd think we could omit considering 'name', since fullname is either the same as name or a wrapper for it? > + hash = iterative_hash_object (fullname, hash); > + return hash; > + } > > - hash = (htab_hash_pointer (TYPE_CONTEXT (t)) > - ^ htab_hash_pointer (TYPE_IDENTIFIER (t))); > + static hashval_t > + hash (const typename_info *ti) > + { > + return typename_hasher::hash (ti->scope, ti->name, ti->template_id); > + } > > - return hash; > + static hashval_t > + hash (tree t) > + { > + return typename_hasher::hash (TYPE_CONTEXT (t), > + TYPE_IDENTIFIER (t), > + TYPENAME_TYPE_FULLNAME (t)); > } > > /* Compare two TYPENAME_TYPEs. */ > @@ -4053,8 +4066,7 @@ build_typename_type (tree context, tree name, tree fullname, > ti.class_p = (tag_type == class_type > || tag_type == record_type > || tag_type == union_type); > - hashval_t hash = (htab_hash_pointer (ti.scope) > - ^ htab_hash_pointer (ti.name)); > + hashval_t hash = typename_hasher::hash (&ti); > > /* See if we already have this type. */ > tree *e = typename_htab->find_slot_with_hash (&ti, hash, INSERT); > diff --git a/gcc/cp/pt.cc b/gcc/cp/pt.cc > index 55129cf6f2c..381fc337cb0 100644 > --- a/gcc/cp/pt.cc > +++ b/gcc/cp/pt.cc > @@ -107,6 +107,7 @@ static bool excessive_deduction_depth; > struct spec_hasher : ggc_ptr_hash > { > static hashval_t hash (spec_entry *); > + static hashval_t hash (tree, tree); > static bool equal (spec_entry *, spec_entry *); > }; > > @@ -1768,13 +1769,22 @@ hash_tmpl_and_args (tree tmpl, tree args) > return iterative_hash_template_arg (args, val); > } > > +hashval_t > +spec_hasher::hash (tree tmpl, tree args) > +{ > + ++comparing_specializations; > + hashval_t val = hash_tmpl_and_args (tmpl, args); > + --comparing_specializations; > + return val; > +} > + > /* Returns a hash for a spec_entry node based on the TMPL and ARGS members, > ignoring SPEC. */ > > hashval_t > spec_hasher::hash (spec_entry *e) > { > - return hash_tmpl_and_args (e->tmpl, e->args); > + return spec_hasher::hash (e->tmpl, e->args); > } > > /* Recursively calculate a hash value for a template argument ARG, for use > @@ -1960,6 +1970,16 @@ iterative_hash_template_arg (tree arg, hashval_t val) > val = iterative_hash_template_arg (DECLTYPE_TYPE_EXPR (arg), val); > break; > > + case TYPENAME_TYPE: > + if (comparing_specializations) Please add a comment that this is to match structural_comptypes. OK with these changes. > + { > + tree context = TYPE_MAIN_VARIANT (TYPE_CONTEXT (arg)); > + tree fullname = TYPENAME_TYPE_FULLNAME (arg); > + val = iterative_hash_template_arg (context, val); > + val = iterative_hash_template_arg (fullname, val); > + } > + break; > + > default: > if (tree canonical = TYPE_CANONICAL (arg)) > val = iterative_hash_object (TYPE_HASH (canonical), val); > @@ -14116,7 +14136,7 @@ tsubst_function_decl (tree t, tree args, tsubst_flags_t complain, > /* Check to see if we already have this specialization. */ > if (!lambda_fntype) > { > - hash = hash_tmpl_and_args (gen_tmpl, argvec); > + hash = spec_hasher::hash (gen_tmpl, argvec); > if (tree spec = retrieve_specialization (gen_tmpl, argvec, hash)) > /* The spec for these args might be a partial instantiation of the > template, but here what we want is the FUNCTION_DECL. */ > @@ -14419,7 +14439,7 @@ tsubst_template_decl (tree t, tree args, tsubst_flags_t complain, > if (full_args == tmpl_args) > return t; > > - hash = hash_tmpl_and_args (t, full_args); > + hash = spec_hasher::hash (t, full_args); > spec = retrieve_specialization (t, full_args, hash); > if (spec != NULL_TREE) > { > @@ -14958,7 +14978,7 @@ tsubst_decl (tree t, tree args, tsubst_flags_t complain) > if (argvec == error_mark_node) > RETURN (error_mark_node); > } > - hash = hash_tmpl_and_args (gen_tmpl, argvec); > + hash = spec_hasher::hash (gen_tmpl, argvec); > spec = retrieve_specialization (gen_tmpl, argvec, hash); > } > }