From patchwork Mon Jun 20 16:57:51 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: =?utf-8?q?Fran=C3=A7ois_Dumont?= X-Patchwork-Id: 55202 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 43FC23851ABC for ; Mon, 20 Jun 2022 17:01:09 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 43FC23851ABC DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1655744469; bh=v2NGbGFf0TG4X5idb5HnR6fbdw4j0Xvgcg+nCMZN07c=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=fBRNAyZQqFNA75sziT8HddgCQ13d3dx4N514CbkCypHcTNSaWay71J0ghS8HgbU54 tApRuk2UX+ciGvqNY0uC+/dfY1Xe3ItXrkEhL5FHJosn7qmT4/5iSrVIkbe1D5+FFD WI53MkKqadmeW/Y3EbfUzudGztPWm7kjY0geNQ2s= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ej1-x634.google.com (mail-ej1-x634.google.com [IPv6:2a00:1450:4864:20::634]) by sourceware.org (Postfix) with ESMTPS id 8E8913851AB4; Mon, 20 Jun 2022 16:57:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8E8913851AB4 Received: by mail-ej1-x634.google.com with SMTP id g26so954813ejb.5; Mon, 20 Jun 2022 09:57:56 -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:from :subject:to:cc:content-language; bh=v2NGbGFf0TG4X5idb5HnR6fbdw4j0Xvgcg+nCMZN07c=; b=FtfvSe3z/PYzrtCwZa+t6I/7Ni1DnteDuumL+kkDY7du+egdq66yZI7WE5UR0V6gf6 /4AMCuyKr09c5M4UnNtNElXo3vmevJEn0GDujZ2864Tg6JvFoUkGSPDpkRFb8XirjPgt U8PF/P98roKCaljfDI/MnHN6p8GRwljc7Olz4kBvcRufX00aJgXjIpyKTcDlHqvTu44j AN1nzspLR+y2SDrcpkdJap4X+9m3HUCwNn4ASZTOnqG47MhKPCCfx5RUOGvTNHdRIUSC YfzaDndc+B1gMz988f/T3rpxCfDnlKXksix1wk1SZ6iY0vA+1g7/RsZG8fqOX9Rg5rZa kCeQ== X-Gm-Message-State: AJIora/r+zZOz98wjU0VpcGIXdaQkRWJKc8knAAR6Piq2mPNJR90nxK0 JSsLCIdVlX1mt8+a2wbLDKQnewLU8mo= X-Google-Smtp-Source: AGRyM1sbpEZ27SNRwiLXCcasaQBnmgkDmoQ/TBsmbi76ibShQTGK5OWkaw23cgCA6K9u8Liia5yhqQ== X-Received: by 2002:a17:907:da7:b0:722:dac3:13e0 with SMTP id go39-20020a1709070da700b00722dac313e0mr1556349ejc.337.1655744275175; Mon, 20 Jun 2022 09:57:55 -0700 (PDT) Received: from [10.126.3.254] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id ff10-20020a1709069c0a00b006fec69696a0sm6197972ejc.220.2022.06.20.09.57.53 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 20 Jun 2022 09:57:54 -0700 (PDT) Message-ID: <82bd8c6e-760f-a6c8-2e4a-fad412a0ce2c@gmail.com> Date: Mon, 20 Jun 2022 18:57:51 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.9.1 Subject: [PATCH 2/5][_Hashtable] New method to check current bucket To: "libstdc++@gcc.gnu.org" Content-Language: fr X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_BARRACUDACENTRAL, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, 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-Patchwork-Original-From: =?utf-8?q?Fran=C3=A7ois_Dumont_via_Gcc-patches?= From: =?utf-8?q?Fran=C3=A7ois_Dumont?= Reply-To: =?utf-8?q?Fran=C3=A7ois_Dumont?= Cc: gcc-patches Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" libstdc++: [_Hashtable] Use next bucket node and equal_to to check if same bucket To find out if we are still in the same bucket we can first check that current node is not the next bucket's before-begin and then that hash code are equals when cached. If not we can also use the equal_to functor in a multi-container context. As a last resort, compute node bucket index. libstdc++-v3/ChangeLog:     * include/bits/hashtable_policy.h (_Hashtable_base<>::_S_hash_code_equals): New.     * include/bits/hashtable.h (_Hashtable<>::_M_is_in_bucket): New, use latter.     (_Hashtable<>::_M_find_before_node): Use latter.     (_Hashtable<>::_M_find_before_node_tr): Likewise. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 8318da168e3..e53cbaf0644 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -801,6 +801,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_base_ptr _M_find_before_node(const key_type&); + bool + _M_is_in_bucket(size_type __bkt, __node_ptr, __node_ptr __n, + true_type /* __uks */) const + { return _M_bucket_index(*__n) == __bkt; } + + bool + _M_is_in_bucket(size_type __bkt, __node_ptr __prev_n, __node_ptr __n, + false_type /* __uks */) const + { + return this->_M_key_equals(_ExtractKey{}(__prev_n->_M_v()), *__n) + || _M_bucket_index(*__n) == __bkt; + } + + bool + _M_is_nxt_in_bucket(size_type __bkt, __node_ptr __prev_n, + __node_base_ptr __nxt_bkt_n) const + { + if (__prev_n == __nxt_bkt_n) + return false; + + __node_ptr __n = __prev_n->_M_next(); + if (this->_S_hash_code_equals(*__prev_n, *__n)) + return true; + + return _M_is_in_bucket(__bkt, __prev_n, __n, __unique_keys{}); + } + // Find and insert helper functions and types // Find the node before the one matching the criteria. __node_base_ptr @@ -1999,13 +2026,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (!__prev_p) return nullptr; + __node_base_ptr __nxt_bkt_n + = __bkt < _M_bucket_count - 1 ? _M_buckets[__bkt + 1] : nullptr; for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; __p = __p->_M_next()) { if (this->_M_equals(__k, __code, *__p)) return __prev_p; - if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) + if (!__p->_M_nxt || !_M_is_nxt_in_bucket(__bkt, __p, __nxt_bkt_n)) break; __prev_p = __p; } @@ -2029,13 +2058,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (!__prev_p) return nullptr; + __node_base_ptr __nxt_bkt_n + = __bkt < _M_bucket_count - 1 ? _M_buckets[__bkt + 1] : nullptr; for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);; __p = __p->_M_next()) { if (this->_M_equals_tr(__k, __code, *__p)) return __prev_p; - if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt) + if (!__p->_M_nxt || !_M_is_nxt_in_bucket(__bkt, __p, __nxt_bkt_n)) break; __prev_p = __p; } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 83a9ff2bb3d..e848ba1d3f7 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -1721,6 +1721,16 @@ namespace __detail : __hash_code_base(__hash), _EqualEBO(__eq) { } + static bool + _S_hash_code_equals(const _Hash_node_code_cache&, + const _Hash_node_code_cache&) + { return false; } + + static bool + _S_hash_code_equals(const _Hash_node_code_cache& __lhn, + const _Hash_node_code_cache& __rhn) + { return __lhn._M_hash_code == __rhn._M_hash_code; } + bool _M_key_equals(const _Key& __k, const _Hash_node_value<_Value,