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 C50F238293EC for ; Fri, 10 Jun 2022 13:40:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C50F238293EC Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-344-7d_fph5cMYywSRcCVJCLsQ-1; Fri, 10 Jun 2022 09:40:23 -0400 X-MC-Unique: 7d_fph5cMYywSRcCVJCLsQ-1 Received: by mail-qk1-f197.google.com with SMTP id k13-20020a05620a414d00b006a6e4dc1dfcso8245547qko.19 for ; Fri, 10 Jun 2022 06:40:23 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=lW3ucUrMxaq+bBPry6+W0psb2wsacCI+izuMjemtIOc=; b=KsotIhaB4mqdvZgcGDzT/itSCQ78CFClhDrBI+hYc0NOIt91wmVDDCRAMnY7TpMNMo rUZVCRVhQaRAj4cqgjMbPu9IZIasWRXVUFcNss0ULPVpWUmWYDaGBVF3A+RaxVDWbFpL +G7YvKl/fnBI1AmqBrwq54OSV9W6XhBr9LiUX9pfXbdlyWk5PsPD4zlDrwlrZd5sAkBZ zerzXQ/sf/ksB6TkKIr+wznjyaKtInHGJBtwV1XOtaMAt4l5Hu0jKaYr7HR6AsSWyR0j SM9dRT6yDu7sqnLPNhSWU0rXUQwEoPsSLpS6UMzQ5UbGZuV85yLBzjOgSa5cn1cn1nAk UsYQ== X-Gm-Message-State: AOAM530evO25jRgdzmjZEOl+UB94hdvasOQwR0+Eyc5H3+LBjXmc1yML mJJfC59r9Lo0QCDvHRjine8aoTCmtjYO2eViI98dyLqWPN8eZEspEeKrmbqRI49lXR7FjK9Q0Je tKH/tKnvwq36NcBlkxAxsh+gc6WlVMx50oaW3K1p/lcBgawrKEb8453imzjdwevqjegk= X-Received: by 2002:a05:622a:64b:b0:305:18d:c148 with SMTP id a11-20020a05622a064b00b00305018dc148mr10937968qtb.67.1654868422658; Fri, 10 Jun 2022 06:40:22 -0700 (PDT) X-Google-Smtp-Source: ABdhPJy81as49c1QzJQElKBtu/uQys6QPKDT5sEE6Ez0NyDvtQBcKnFZY/+4t74j/8dI/e408vMj6A== X-Received: by 2002:a05:622a:64b:b0:305:18d:c148 with SMTP id a11-20020a05622a064b00b00305018dc148mr10937937qtb.67.1654868422257; Fri, 10 Jun 2022 06:40:22 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id bi19-20020a05620a319300b006a6dcd92eb3sm9167869qkb.121.2022.06.10.06.40.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 10 Jun 2022 06:40:21 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Subject: [PATCH] c++: improve TYPENAME_TYPE hashing [PR65328] Date: Fri, 10 Jun 2022 09:40:20 -0400 Message-Id: <20220610134020.1835431-1-ppalka@redhat.com> X-Mailer: git-send-email 2.36.1.363.g9c897eef06 MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-14.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, 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 13:40:27 -0000 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); + 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) + { + 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); } } -- 2.36.1.363.g9c897eef06