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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id AB2023861001 for ; Tue, 3 Nov 2020 20:43:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org AB2023861001 Received: from mail-qv1-f72.google.com (mail-qv1-f72.google.com [209.85.219.72]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-217-D9M2rJvYNt-NzhNk33g0Sw-1; Tue, 03 Nov 2020 15:43:33 -0500 X-MC-Unique: D9M2rJvYNt-NzhNk33g0Sw-1 Received: by mail-qv1-f72.google.com with SMTP id x10so6452126qvo.22 for ; Tue, 03 Nov 2020 12:43:33 -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:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=lCb4e/FFWhbqQXya+dE2B76ehMd2+ZRu75e2vOEQNRs=; b=IDOQH1zfcI0CxdZYOyG+QgGBnc9u43pK4ksHw6/9zrDiRYQwLw9OG5ukRfoHSoJef0 9U6vJKvesFWyGwk9aFbW6Z5RZ9RzwTfUSqINf81YyUxaGYPHbbxrdLzhQl4R6mWG3tGb RDafp92lh6sQ2gbVZqfqMauqsEBftVTKDrbSi/MtCFdoqLlPNYTivdcrZPtFAcJQR4GL /KkDXaPd1DYcy0q81dt2dp+uj0XCyqNLn3FY901HmKjPR+Tpd2TH9GT4+9F94kLatKTK V+svqKtNZNf02P8+vmBWcFYQUXviRRMD4cs2G2nj8nZk/pLbFBidqgSOo4FPVpcsPEta SqDw== X-Gm-Message-State: AOAM5315/ix6E06O02oWBESTmT3PRDBk/KlGP7TEUYJfoZcZ8XiirkGH NWrFSArp3k3myvRPAareyCJMWMC/IWtRHCTurQwb5/4ef90mgxq0yF65aoDU0jXNyLlvyhsJ6s3 +Yst8Ui3G3egjG6pfUg== X-Received: by 2002:a0c:85e3:: with SMTP id o90mr26981063qva.46.1604436212138; Tue, 03 Nov 2020 12:43:32 -0800 (PST) X-Google-Smtp-Source: ABdhPJzNbIXqzcj9APEtg/MZz9rNFCPd64ATjSFbtWTf3EGTLDlxgoVZwxncqr4dPHNIcn3vaml6zA== X-Received: by 2002:a0c:85e3:: with SMTP id o90mr26981037qva.46.1604436211839; Tue, 03 Nov 2020 12:43:31 -0800 (PST) Received: from localhost.localdomain (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id r190sm11849808qkf.101.2020.11.03.12.43.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 03 Nov 2020 12:43:31 -0800 (PST) From: Patrick Palka To: gcc-patches@gcc.gnu.org Subject: [PATCH] c++: Reuse identical ATOMIC_CONSTRs during normalization Date: Tue, 3 Nov 2020 15:43:29 -0500 Message-Id: <20201103204329.4069400-1-ppalka@redhat.com> X-Mailer: git-send-email 2.29.2.154.g7f7ebe054a 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-Spam-Status: No, score=-16.2 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_H4, 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: Tue, 03 Nov 2020 20:43:38 -0000 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); + } +}; + +/* Used by normalize_atom to cache ATOMIC_CONSTRs. */ + +static GTY((deletable)) hash_table *atom_cache; + /* 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) { - 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); } -- 2.29.2.154.g7f7ebe054a