From patchwork Mon Jun 20 16:57:37 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: 55201 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 8726138515C5 for ; Mon, 20 Jun 2022 16:59:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 8726138515C5 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1655744365; bh=RWNEwUj8TGB6hZ5NK6zr+9QOjyl7lO5aOpXzhdw1lGY=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=cglXUK0ZWVbyE/vzEN4PPo2lUtSS+3wG6D8L2QX/e5JSDT/LQPFFZWNttvtxsGxJJ 5ee0uv1wnJupQ4E8EoI+ASQ06d/fHwcdVYZTid2eyQY7ufHy2J82Ash7Ov5J2lpMw7 xCZBfx29/y/qbmUzd4vm/mPnZlW4fS6igLAvS4Ic= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ej1-x629.google.com (mail-ej1-x629.google.com [IPv6:2a00:1450:4864:20::629]) by sourceware.org (Postfix) with ESMTPS id 88F083851AA5; Mon, 20 Jun 2022 16:57:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 88F083851AA5 Received: by mail-ej1-x629.google.com with SMTP id u12so22307741eja.8; Mon, 20 Jun 2022 09:57:42 -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=RWNEwUj8TGB6hZ5NK6zr+9QOjyl7lO5aOpXzhdw1lGY=; b=cX3s4Re8YkhY4O/PjC+2xi43toa9Oz/9OtGbfR+8EvZMuzRQNxIbo7tvldFnNbWxt3 BZub9oLH0qP9JB8plSUz0Rph/B111L9T4SNn3U9II1s9HGXkixSjfjHU2bBFmTUTxgtn cVXIsg01jEXWIJ1rmfDm2wM7JRYyIyXI5HpcoGYrPVzNolyL7AzsqYiZskYzJfYgSYJn hMYSHUz0ajqu66tJjSrSzYzSMvns5fkgJr/SvXQ3/pIsmGMZ6eqZg+xK3uWQaqqE+MXI lrx6uvw7o+QCoeA1TB18adGcD/Iu27DvOCTGYDQWNvxN+4Uk6rXAa20f20FWCQ/cLZ6j mS7w== X-Gm-Message-State: AJIora/LTJT0ewya96WxyF+JtH86ELZ5fvYMVxfm8C4ZiNn9CoUY5MTe SqsMkAqd8AoQ3RJHqco6kVmrkLDg3zk= X-Google-Smtp-Source: AGRyM1ugzE4tB0lRzcI/uO4DLlFZoJF/LKMDqP9xWB76UcTv2Wj7DyFKOpyEyELBUzPt3EuguCZsng== X-Received: by 2002:a17:906:748b:b0:712:2a23:7395 with SMTP id e11-20020a170906748b00b007122a237395mr22348641ejl.666.1655744261036; Mon, 20 Jun 2022 09:57:41 -0700 (PDT) Received: from [10.126.3.254] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id b23-20020aa7df97000000b004357ab9cfb1sm4313706edy.26.2022.06.20.09.57.38 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 20 Jun 2022 09:57:40 -0700 (PDT) Message-ID: <712cf294-e646-b470-f862-30aadd543894@gmail.com> Date: Mon, 20 Jun 2022 18:57:37 +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 1/5][_Hashtable] Make more use of user provided hint 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] Make more use of insertion hint Make use of the user provided hint iterator in unordered containers operations. Hint is used: - As a hint for allocation to potentially reduce memory fragmentation. - For unordered_set/unordered_map we check if it does not match the key of the element to insert, before computing the hash code. - For unordered_multiset/unordered_multimap, if equals to the key of the element to insert, the hash code is taken from the hint so that we can take advantage of the potential hash code cache. libstdc++-v3/ChangeLog:     * include/bits/hashtable_policy.h (_NodeBuilder<>::_S_build): Add _NodePtr template     parameter.     (_ReuseOrAllocNode::operator()): Add __node_ptr parameter.     (_AllocNode::operator()): Likewise.     (_Insert_base::try_emplace): Adapt to use hint.     (_Hashtable_alloc<>::_M_allocate_node(__node_ptr, _Args&&...)): Add __node_ptr parameter.     * include/bits/hashtable.h     (_Hashtable<>::_Scope_node<>(__hashtable_alloc*, __node_ptr, _Args&&...)):     Add __node_ptr parameter.     (_Hashtable<>::_M_get_hint(size_type, __node_ptr)): New.     (_Hashtable<>::_M_emplace_unique(const_iterator, _Args&&...)): New.     (_Hashtable<>::_M_emplace_multi(const_iterator, _Args&&...)): New.     (_Hashtable<>::_M_emplace()): Adapt to use latter.     (_Hashtable<>::_M_insert_unique): Add const_iterator parameter.     (_Hashtable<>::_M_insert(const_iterator, _Arg&&, const _NodeGenerator&, true_type)):     Use latter.     (_Hashtable<>::_M_reinsert_node(const_iterator, node_type&&)):     Add const_iterator parameter, adapt to use it.     (_Hashtable<>::_M_reinsert_node_multi): Make more use of hint parameter.     * include/bits/unordered_map.h (unordered_map<>::insert(node_type&&)): Pass cend as     hint.     (unordered_map<>::insert(const_iterator, node_type&&)): Adapt to use hint.     * include/bits/unordered_set.h (unordered_set<>::insert(node_type&&)): Pass cend as     hint.     (unordered_set<>::insert(const_iterator, node_type&&)): Adapt to use hint. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index 1b21b795f89..8318da168e3 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -302,9 +302,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Allocate a node and construct an element within it. template - _Scoped_node(__hashtable_alloc* __h, _Args&&... __args) + _Scoped_node(__hashtable_alloc* __h, + __node_ptr __hint, _Args&&... __args) : _M_h(__h), - _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...)) + _M_node(__h->_M_allocate_node(__hint, + std::forward<_Args>(__args)...)) { } // Destroy element and deallocate node. @@ -829,6 +831,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return nullptr; } + // Gets a hint after which a node should be allocated given a bucket. + __node_ptr + _M_get_hint(size_type __bkt, __node_ptr __hint = nullptr) const + { + __node_base_ptr __node; + if (__node = _M_buckets[__bkt]) + return __node != &_M_before_begin + ? static_cast<__node_ptr>(__node) : __hint; + + return __hint; + } + // Insert a node at the beginning of a bucket. void _M_insert_bucket_begin(size_type, __node_ptr); @@ -860,26 +874,40 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_emplace(true_type __uks, _Args&&... __args); + _M_emplace_unique(const_iterator, _Args&&... __args); + + template + iterator + _M_emplace_multi(const_iterator, _Args&&... __args); + + template + std::pair + _M_emplace(true_type /*__uks*/, _Args&&... __args) + { return _M_emplace_unique(cend(), std::forward<_Args>(__args)...); } template iterator - _M_emplace(false_type __uks, _Args&&... __args) - { return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); } + _M_emplace(false_type /*__uks*/, _Args&&... __args) + { return _M_emplace_multi(cend(), std::forward<_Args>(__args)...); } - // Emplace with hint, useless when keys are unique. template iterator - _M_emplace(const_iterator, true_type __uks, _Args&&... __args) - { return _M_emplace(__uks, std::forward<_Args>(__args)...).first; } + _M_emplace(const_iterator __hint, true_type /*__uks*/, + _Args&&... __args) + { + return _M_emplace_unique(__hint, + std::forward<_Args>(__args)...).first; + } template iterator - _M_emplace(const_iterator, false_type __uks, _Args&&... __args); + _M_emplace(const_iterator __hint, false_type /*__uks*/, + _Args&&... __args) + { return _M_emplace_multi(__hint, std::forward<_Args>(__args)...); } template std::pair - _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&); + _M_insert_unique(const_iterator, _Kt&&, _Arg&&, const _NodeGenerator&); template static __conditional_t< @@ -899,9 +927,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION template std::pair - _M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen) + _M_insert_unique_aux(const_iterator __hint, + _Arg&& __arg, const _NodeGenerator& __node_gen) { - return _M_insert_unique( + return _M_insert_unique(__hint, _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))), std::forward<_Arg>(__arg), __node_gen); } @@ -913,7 +942,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION { using __to_value = __detail::_ConvertToValueType<_ExtractKey, value_type>; - return _M_insert_unique_aux( + return _M_insert_unique_aux(cend(), __to_value{}(std::forward<_Arg>(__arg)), __node_gen); } @@ -928,14 +957,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks); } - // Insert with hint, not used when keys are unique. + // Insert with hint when keys are unique. template iterator - _M_insert(const_iterator, _Arg&& __arg, - const _NodeGenerator& __node_gen, true_type __uks) + _M_insert(const_iterator __hint, _Arg&& __arg, + const _NodeGenerator& __node_gen, true_type /* __uks */) { - return - _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first; + using __to_value + = __detail::_ConvertToValueType<_ExtractKey, value_type>; + return _M_insert_unique_aux(__hint, + __to_value{}(std::forward<_Arg>(__arg)), __node_gen).first; } // Insert with hint when keys are not unique. @@ -999,7 +1030,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #if __cplusplus > 201402L /// Re-insert an extracted node into a container with unique keys. insert_return_type - _M_reinsert_node(node_type&& __nh) + _M_reinsert_node(const_iterator __hint, node_type&& __nh) { insert_return_type __ret; if (__nh.empty()) @@ -1009,20 +1040,30 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_assert(get_allocator() == __nh.get_allocator()); const key_type& __k = __nh._M_key(); - __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__code); - if (__node_ptr __n = _M_find_node(__bkt, __k, __code)) + if (__hint._M_cur + && this->_M_key_equals(__k, *__hint._M_cur)) [[__unlikely__]] { __ret.node = std::move(__nh); - __ret.position = iterator(__n); + __ret.position = iterator(__hint._M_cur); __ret.inserted = false; } else { - __ret.position - = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); - __nh._M_ptr = nullptr; - __ret.inserted = true; + __hash_code __code = this->_M_hash_code(__k); + size_type __bkt = _M_bucket_index(__code); + if (__node_ptr __n = _M_find_node(__bkt, __k, __code)) + { + __ret.node = std::move(__nh); + __ret.position = iterator(__n); + __ret.inserted = false; + } + else + { + __ret.position + = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); + __nh._M_ptr = nullptr; + __ret.inserted = true; + } } } return __ret; @@ -1038,7 +1079,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_assert(get_allocator() == __nh.get_allocator()); const key_type& __k = __nh._M_key(); - auto __code = this->_M_hash_code(__k); + __hash_code __code; + if (__hint._M_cur + && this->_M_key_equals(__k, *__hint._M_cur)) [[__unlikely__]] + __code = this->_M_hash_code(*__hint._M_cur); + else + { + __code = this->_M_hash_code(__k); + __hint = cend(); + } + auto __ret = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr); __nh._M_ptr = nullptr; @@ -1131,8 +1181,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { auto __pos = __i++; - __hash_code __code - = this->_M_hash_code(__src.hash_function(), *__pos._M_cur); + const key_type& __k = _ExtractKey{}(*__pos); + __hash_code __code; + if (__hint && this->_M_key_equals(__k, *__hint)) [[__unlikely__]] + __code = this->_M_hash_code(*__hint); + else + { + __code = this->_M_hash_code(__src.hash_function(), *__pos._M_cur); + __hint = nullptr; + } + auto __nh = __src.extract(__pos); __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; __nh._M_ptr = nullptr; @@ -1355,7 +1413,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // _M_before_begin. __node_ptr __ht_n = __ht._M_begin(); __node_ptr __this_n - = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v())); + = __node_gen(nullptr, __fwd_value_for<_Ht>(__ht_n->_M_v())); this->_M_copy_code(*__this_n, *__ht_n); _M_update_bbegin(__this_n); @@ -1363,7 +1421,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __node_ptr __prev_n = __this_n; for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next()) { - __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v())); + __this_n + = __node_gen(__prev_n, __fwd_value_for<_Ht>(__ht_n->_M_v())); __prev_n->_M_nxt = __this_n; this->_M_copy_code(*__this_n, *__ht_n); size_type __bkt = _M_bucket_index(*__this_n); @@ -2065,11 +2124,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_emplace(true_type /* __uks */, _Args&&... __args) + _M_emplace_unique(const_iterator __hint, _Args&&... __args) -> pair { // First build the node to get access to the hash code - _Scoped_node __node { this, std::forward<_Args>(__args)... }; + _Scoped_node __node { this, __hint._M_cur, std::forward<_Args>(__args)... }; const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); if (size() <= __small_size_threshold()) { @@ -2079,12 +2138,25 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return { __it, false }; } - __hash_code __code = this->_M_hash_code(__k); - size_type __bkt = _M_bucket_index(__code); + __hash_code __code; + size_type __bkt; if (size() > __small_size_threshold()) - if (__node_ptr __p = _M_find_node(__bkt, __k, __code)) - // There is already an equivalent node, no insertion - return { iterator(__p), false }; + { + if (__hint._M_cur + && this->_M_key_equals(__k, *__hint._M_cur)) [[__unlikely__]] + return { iterator(__hint._M_cur), false }; + + __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + if (__node_ptr __p = _M_find_node(__bkt, __k, __code)) + // There is already an equivalent node, no insertion + return { iterator(__p), false }; + } + else + { + __code = this->_M_hash_code(__k); + __bkt = _M_bucket_index(__code); + } // Insert the node auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); @@ -2100,14 +2172,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_emplace(const_iterator __hint, false_type /* __uks */, - _Args&&... __args) + _M_emplace_multi(const_iterator __hint, _Args&&... __args) -> iterator { // First build the node to get its hash code. - _Scoped_node __node { this, std::forward<_Args>(__args)... }; - const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); + _Scoped_node __node + { this, __hint._M_cur, std::forward<_Args>(__args)... }; + const key_type& __k = _ExtractKey{}(__node._M_node->_M_v()); auto __res = this->_M_compute_hash_code(__hint, __k); auto __pos = _M_insert_multi_node(__res.first._M_cur, __res.second, @@ -2126,9 +2198,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_compute_hash_code(const_iterator __hint, const key_type& __k) const -> pair { + if (__hint._M_cur + && this->_M_key_equals(__k, *__hint._M_cur)) [[__unlikely__]] + return { __hint, this->_M_hash_code(*__hint._M_cur) }; + if (size() <= __small_size_threshold()) { - if (__hint != cend()) + if (__hint._M_cur) [[__unlikely__]] { for (auto __it = __hint; __it != cend(); ++__it) if (this->_M_key_equals(__k, *__it._M_cur)) @@ -2198,17 +2274,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Find the node before an equivalent one or use hint if it exists and // if it is equivalent. __node_base_ptr __prev - = __builtin_expect(__hint != nullptr, false) - && this->_M_equals(__k, __code, *__hint) - ? __hint - : _M_find_before_node(__bkt, __k, __code); + = __builtin_expect(__hint != nullptr && + this->_M_equals(__k, __code, *__hint), false) + ? __hint + : _M_find_before_node(__bkt, __k, __code); if (__prev) { // Insert after the node before the equivalent one. __node->_M_nxt = __prev->_M_nxt; __prev->_M_nxt = __node; - if (__builtin_expect(__prev == __hint, false)) + if (__prev == __hint) [[__unlikely__]] // hint might be the last bucket node, in this case we need to // update next bucket. if (__node->_M_nxt @@ -2237,10 +2313,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION auto _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_unique(_Kt&& __k, _Arg&& __v, + _M_insert_unique(const_iterator __hint, + _Kt&& __k, _Arg&& __v, const _NodeGenerator& __node_gen) -> pair { + if (__hint._M_cur + && this->_M_key_equals_tr(__k, *__hint._M_cur)) [[__unlikely__]] + return { iterator(__hint._M_cur), false }; + if (size() <= __small_size_threshold()) for (auto __it = begin(); __it != end(); ++__it) if (this->_M_key_equals_tr(__k, *__it._M_cur)) @@ -2254,11 +2335,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION return { iterator(__node), false }; _Scoped_node __node { - __node_builder_t::_S_build(std::forward<_Kt>(__k), + __node_builder_t::_S_build(_M_get_hint(__bkt, __hint._M_cur), + std::forward<_Kt>(__k), std::forward<_Arg>(__v), __node_gen), this }; + auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node); __node._M_node = nullptr; @@ -2280,12 +2363,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION -> iterator { // First allocate new node so that we don't do anything if it throws. - _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this }; + _Scoped_node __node + { __node_gen(__hint._M_cur, std::forward<_Arg>(__v)), this }; // Second compute the hash code so that we don't rehash if it throws. auto __res = this->_M_compute_hash_code( __hint, _ExtractKey{}(__node._M_node->_M_v())); - auto __pos = _M_insert_multi_node(__res.first._M_cur, __res.second, __node._M_node); diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index f2696ae9b07..83a9ff2bb3d 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -153,12 +153,14 @@ namespace __detail template<> struct _NodeBuilder<_Select1st> { - template - static auto - _S_build(_Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen) - -> typename _NodeGenerator::__node_type* + template + static _NodePtr + _S_build(_NodePtr __hint, + _Kt&& __k, _Arg&& __arg, const _NodeGenerator& __node_gen) { - return __node_gen(std::forward<_Kt>(__k), + return __node_gen(__hint, + std::forward<_Kt>(__k), std::forward<_Arg>(__arg).second); } }; @@ -166,11 +168,12 @@ namespace __detail template<> struct _NodeBuilder<_Identity> { - template - static auto - _S_build(_Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen) - -> typename _NodeGenerator::__node_type* - { return __node_gen(std::forward<_Kt>(__k)); } + template + static _NodePtr + _S_build(_NodePtr __hint, + _Kt&& __k, _Arg&&, const _NodeGenerator& __node_gen) + { return __node_gen(__hint, std::forward<_Kt>(__k)); } }; template @@ -188,22 +191,23 @@ namespace __detail typename __hashtable_alloc::__node_alloc_traits; public: - using __node_type = typename __hashtable_alloc::__node_type; + using __node_ptr = typename __hashtable_alloc::__node_ptr; - _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h) + _ReuseOrAllocNode(__node_ptr __nodes, __hashtable_alloc& __h) : _M_nodes(__nodes), _M_h(__h) { } + _ReuseOrAllocNode(const _ReuseOrAllocNode&) = delete; ~_ReuseOrAllocNode() { _M_h._M_deallocate_nodes(_M_nodes); } template - __node_type* - operator()(_Args&&... __args) const + __node_ptr + operator()(__node_ptr __hint, _Args&&... __args) const { if (_M_nodes) { - __node_type* __node = _M_nodes; + __node_ptr __node = _M_nodes; _M_nodes = _M_nodes->_M_next(); __node->_M_nxt = nullptr; auto& __a = _M_h._M_node_allocator(); @@ -218,13 +222,15 @@ namespace __detail _M_h._M_deallocate_node_ptr(__node); __throw_exception_again; } + return __node; } - return _M_h._M_allocate_node(std::forward<_Args>(__args)...); + + return _M_h._M_allocate_node(__hint, std::forward<_Args>(__args)...); } private: - mutable __node_type* _M_nodes; + mutable __node_ptr _M_nodes; __hashtable_alloc& _M_h; }; @@ -237,15 +243,15 @@ namespace __detail using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; public: - using __node_type = typename __hashtable_alloc::__node_type; + using __node_ptr = typename __hashtable_alloc::__node_ptr; _AllocNode(__hashtable_alloc& __h) : _M_h(__h) { } template - __node_type* - operator()(_Args&&... __args) const - { return _M_h._M_allocate_node(std::forward<_Args>(__args)...); } + __node_ptr + operator()(__node_ptr __hint, _Args&&... __args) const + { return _M_h._M_allocate_node(__hint, std::forward<_Args>(__args)...); } private: __hashtable_alloc& _M_h; @@ -813,6 +819,7 @@ namespace __detail typename __hashtable::_Scoped_node __node { __h, + __h->_M_get_hint(__bkt), std::piecewise_construct, std::tuple(__k), std::tuple<>() @@ -840,6 +847,7 @@ namespace __detail typename __hashtable::_Scoped_node __node { __h, + __h->_M_get_hint(__bkt), std::piecewise_construct, std::forward_as_tuple(std::move(__k)), std::tuple<>() @@ -939,7 +947,7 @@ namespace __detail template std::pair - try_emplace(const_iterator, _KType&& __k, _Args&&... __args) + try_emplace(const_iterator __hint, _KType&& __k, _Args&&... __args) { __hashtable& __h = _M_conjure_hashtable(); auto __code = __h._M_hash_code(__k); @@ -948,7 +956,7 @@ namespace __detail return { iterator(__node), false }; typename __hashtable::_Scoped_node __node { - &__h, + &__h, __hint._M_cur, std::piecewise_construct, std::forward_as_tuple(std::forward<_KType>(__k)), std::forward_as_tuple(std::forward<_Args>(__args)...) @@ -1966,7 +1974,7 @@ namespace __detail // Allocate a node and construct an element within it. template __node_ptr - _M_allocate_node(_Args&&... __args); + _M_allocate_node(__node_ptr __hint, _Args&&... __args); // Destroy the element within a node and deallocate the node. void @@ -1993,22 +2001,32 @@ namespace __detail template template auto - _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args) + _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(__node_ptr __hint, + _Args&&... __args) -> __node_ptr { - auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1); + auto& __alloc = _M_node_allocator(); + typename __node_alloc_traits::pointer __nptr; + if (__hint) [[__unlikely__]] + { + typedef typename __node_alloc_traits::const_pointer _CPtr; + auto __hptr = std::pointer_traits<_CPtr>::pointer_to(*__hint); + __nptr = __node_alloc_traits::allocate(__alloc, 1, __hptr); + } + else + __nptr = __node_alloc_traits::allocate(__alloc, 1); + __node_ptr __n = std::__to_address(__nptr); __try { ::new ((void*)__n) __node_type; - __node_alloc_traits::construct(_M_node_allocator(), - __n->_M_valptr(), + __node_alloc_traits::construct(__alloc, __n->_M_valptr(), std::forward<_Args>(__args)...); return __n; } __catch(...) { - __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1); + __node_alloc_traits::deallocate(__alloc, __nptr, 1); __throw_exception_again; } } diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h index 5a3e6f61af2..f9e4504ecc7 100644 --- a/libstdc++-v3/include/bits/unordered_map.h +++ b/libstdc++-v3/include/bits/unordered_map.h @@ -441,12 +441,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Re-insert an extracted node. insert_return_type insert(node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)); } + { return _M_h._M_reinsert_node(cend(), std::move(__nh)); } /// Re-insert an extracted node. iterator - insert(const_iterator, node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)).position; } + insert(const_iterator __hint, node_type&& __nh) + { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; } #define __cpp_lib_unordered_map_try_emplace 201411L /** diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h index 740bbafd4c9..9731c9aa84c 100644 --- a/libstdc++-v3/include/bits/unordered_set.h +++ b/libstdc++-v3/include/bits/unordered_set.h @@ -502,12 +502,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER /// Re-insert an extracted node. insert_return_type insert(node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)); } + { return _M_h._M_reinsert_node(cend(), std::move(__nh)); } /// Re-insert an extracted node. iterator - insert(const_iterator, node_type&& __nh) - { return _M_h._M_reinsert_node(std::move(__nh)).position; } + insert(const_iterator __hint, node_type&& __nh) + { return _M_h._M_reinsert_node(__hint, std::move(__nh)).position; } #endif // C++17 ///@{ 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, From patchwork Mon Jun 20 16:58:07 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: 55203 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 BACB73851AB3 for ; Mon, 20 Jun 2022 17:02:38 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BACB73851AB3 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1655744558; bh=+Qhlmz6sGUoT/0AA0SISo8TFS4y4hFAC/IO94nnDRTU=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=jd96q+xK3dXaQfqTgr5o/ElGsZBxT+ZSYZd06MsdMUGxyymtjOVpsTuGxPiv+xujf mMioU/gsdiAA/EDnhG6Ixny6CX95EuOc2kJc3drX3XBnO9AgpRGCYEHt/lE4CGO6JY kZauaZFhecoSXy1yZJnQHWCBWWwgt5qDUql/sNhw= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ej1-x62d.google.com (mail-ej1-x62d.google.com [IPv6:2a00:1450:4864:20::62d]) by sourceware.org (Postfix) with ESMTPS id D2A343851ABC; Mon, 20 Jun 2022 16:58:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D2A343851ABC Received: by mail-ej1-x62d.google.com with SMTP id me5so22344340ejb.2; Mon, 20 Jun 2022 09:58:14 -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=+Qhlmz6sGUoT/0AA0SISo8TFS4y4hFAC/IO94nnDRTU=; b=2ZdXN+371rGMwWc8zydq/49m/jSLxomdZzIkLeg7uUBfnL28CLYVAT+777Gw/+DHD/ C/PFFv6oJbvwNaHfDLfWJ2uj3NZK3Xn9UJUXA188jYl+20eCEOE1KZ9UI9rnA9bYhfA3 sZVp4+LltfE8NJAoVRfkaaq7PROz4CYKEMsTusC9syC2gz0Hj4GNKJ6Y9YgRAD5g50/x GWGKWm5Zk+BPwwVUXb9HXGvirlZiPpQ/8T9T5f38+vLJyWDcfT7JNCtkyrzfm6UsM2zs LM8On0jRcaDGmquNNR0tMIGjf9nPmMqbe9wHkUN/wYpFqQE8Dopk+/l5Rf9+mV1fXnUb NV7A== X-Gm-Message-State: AJIora9NbQ+xX2gu+GNVpnj7zlJ7Sleq+tjWbWswuMdRQkUySWpiYg29 gHO/CYpBqQTzWbsp+YMfFp4N4EeemzI= X-Google-Smtp-Source: AGRyM1vy+2VdN+/DtYB3ycyVQhk3Q38K0zXdVBBS4mfBECN2VYoQ3aRLiAJvpCsCVAQ81RfT98FXOQ== X-Received: by 2002:a17:907:c24:b0:711:d4c6:9161 with SMTP id ga36-20020a1709070c2400b00711d4c69161mr22326368ejc.760.1655744293416; Mon, 20 Jun 2022 09:58:13 -0700 (PDT) Received: from [10.126.3.254] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id d5-20020a170906344500b006fed062c68esm6173555ejb.182.2022.06.20.09.58.11 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 20 Jun 2022 09:58:12 -0700 (PDT) Message-ID: Date: Mon, 20 Jun 2022 18:58:07 +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 3/5][_Hashtable] std::initializer_list insertion To: "libstdc++@gcc.gnu.org" Content-Language: fr X-Spam-Status: No, score=-9.8 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] Consider all initializer_list elements are inserted When instantiated using an initializer_list the container is pre-sized based on initializer_list size. libstdc++-v3/ChangeLog:     * include/bits/hashtable_policy.h (_Insert_base<>::insert(initializer_list<>)):     Use assignment operator if container is empty and has default bucket count.     * include/bits/hashtable.h (_Hashtable<>(initializer_list<>)): Use initializer_list     size as bucket count hint if user did not provide any value that is to say if it is     the default 0 value.     * testsuite/23_containers/unordered_set/init-list.cc (test02): New test case. Tested under Linux x86_64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index e53cbaf0644..b0d1bc1f08a 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -575,7 +575,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION const _Hash& __hf = _Hash(), const key_equal& __eql = key_equal(), const allocator_type& __a = allocator_type()) - : _Hashtable(__l.begin(), __l.end(), __bkt_count_hint, + : _Hashtable(__l.begin(), __l.end(), + __bkt_count_hint == 0 ? __l.size() : __bkt_count_hint, __hf, __eql, __a, __unique_keys{}) { } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index e848ba1d3f7..139d0ec27df 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -969,7 +969,16 @@ namespace __detail void insert(initializer_list __l) - { this->insert(__l.begin(), __l.end()); } + { + __hashtable& __h = _M_conjure_hashtable(); + if (__h.empty() && __h.bucket_count() == 1) + { + __h = __l; + return; + } + + this->insert(__l.begin(), __l.end()); + } template void diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/init-list.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/init-list.cc index fc11498c718..70789d03e63 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_set/init-list.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_set/init-list.cc @@ -48,8 +48,27 @@ void test01() VERIFY(m.count(1) == 0); } +void test02() +{ + unordered_set u({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }); + VERIFY( u.size() == 13 ); + VERIFY( u.count(0) == 1 ); + VERIFY( u.count(13) == 0 ); + + auto bkt_count = u.bucket_count(); + u.insert({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }); + VERIFY( u.size() == 13 ); + VERIFY( u.bucket_count() == bkt_count ); + + u.clear(); + u.insert({ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }); + VERIFY( u.size() == 13 ); + VERIFY( u.bucket_count() == bkt_count ); +} + int main() { __gnu_test::set_memory_limits(); test01(); + test02(); } From patchwork Mon Jun 20 16:58:20 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: 55204 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 53A4C3851AB0 for ; Mon, 20 Jun 2022 17:04:08 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 53A4C3851AB0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1655744648; bh=I8PrwAt9D4SFONYQL3fywScu2OrMeiuuBzb6Gre0lC0=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=W98kXCQ0UZOXhOi/+gTbz2pDmuDsj7IpVPowENiEr0unbVPl26H0d39MiQ/xNfmTm /cB13oQXESzOjfcKTPjJ+eTFQKfMr4OUWUw7rslMtdEzdTF0egYmB8hvF49vKIn4Jx /a51eR9JNDWpkC1opzMUgLDLcXOLfRBSNkn64ht4= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ed1-x529.google.com (mail-ed1-x529.google.com [IPv6:2a00:1450:4864:20::529]) by sourceware.org (Postfix) with ESMTPS id C8FA73858C2C; Mon, 20 Jun 2022 16:58:24 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org C8FA73858C2C Received: by mail-ed1-x529.google.com with SMTP id cf14so6192203edb.8; Mon, 20 Jun 2022 09:58:24 -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=I8PrwAt9D4SFONYQL3fywScu2OrMeiuuBzb6Gre0lC0=; b=Geb5NZIkABuIjSu1uOHUpYp4JrAtmuj6UbTkYIggEyzBMIDqF8bPLqFgx2eeBN9r7l tq3myohc+7XLnYD9lio/UOjDVfD49mYR0rmch5T6dwoIaC2VDO8kscNj8IHW6pdN17xx GsZclIJF9nYPYp2tx725GKbCxXLAuJU3PzX3Ww4vMjF1RYhykyZd4uxPxhQxnuRPPDpP Qptc3dypKm6HGTP1nYGJpYaawzfxXNuZ666sZcWUrmH70MspE/IVptiqPGl/w222e4Xb BwxuOZz8l+QdyWKr8T/0ArBA4xrWfML9aOHpclbtla+u9bsWOAgfK/r+FaOfl8bqgYrv tbDQ== X-Gm-Message-State: AJIora9owzQTzd0ec5iEJr33FJUzpSI/UkcGJFek9Q56sTEVZnqK8HH3 lDkJN33CK7SX71qONeCuNwIvOoIVKYU= X-Google-Smtp-Source: AGRyM1vj89Su0dNSSqx4ss+Ub4zj2zsllkCV7kOQVN1NMZ6FyJnDlvpUDbX3zoHhDCOU6taJLggkQQ== X-Received: by 2002:a05:6402:5211:b0:42e:2e1c:5bce with SMTP id s17-20020a056402521100b0042e2e1c5bcemr30991221edd.198.1655744303506; Mon, 20 Jun 2022 09:58:23 -0700 (PDT) Received: from [10.126.3.254] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id 9-20020a170906310900b0071cbc7487e1sm5631379ejx.69.2022.06.20.09.58.21 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 20 Jun 2022 09:58:23 -0700 (PDT) Message-ID: Date: Mon, 20 Jun 2022 18:58:20 +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 4/5][_Hashtable] Before begin cache policy To: "libstdc++@gcc.gnu.org" Content-Language: fr X-Spam-Status: No, score=-9.8 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] Add before begin bucket index cache on range insert Add a policy to maintain a cache of the before begin bucket index in the context of range insertion. libstdc++-v3/ChangeLog:     * include/bits/hashtable_policy.h (_CacheBbeginPolicy): New, maintain     a cache.     (_NoCacheBbeginPolicy): New, no cache.     (_ReuseOrAllocNode<>): Inherit _CacheBBeginPolicy.     (_AllocNode<>): Add cache policy template parameter.     (_Map_base<>::operator[]): Adapt, use _NoCacheBBeginPolicy.     (_Insert_base<>__node_gen_type): Replace by...     (_Insert_base<>::__alloc_node_gen_t<>): ...this. Use cache policy as a     template parameter.     (_Insert_base<>::insert): Adapt.     (_Insert_base<>::try_emplace): Adapt.     (_Insert<>::__node_gen_type): Replace by...     (_Insert<>::__alloc_node_gen_t): ...this, use _NoCacheBBeginPolicy.     (_Insert<>::insert): Adapt.     * include/bits/hashtable.h     (_Hashtable<>::__alloc_node_gen_t): Remove.     (_Hashtable<>::__alloc_node_gen_cache_bbegin_t): New.     (_Hashtable<>::__no_cache_bbegin_policy_t): New.     (_Hashtable<>::__cache_bbegin_policy_t): New.     (_Hashtable<>::_CacheBBeginPolicy): Add friend declaration.     (_Hashtable<>::_NoCacheBBeginPolicy): Add friend declaration.     (_Hashtable<>::_M_insert_bucket_begin): Add BBegin policy.     (_Hashtable<>::_M_insert_unique_node): Likewise.     (_Hashtable<>::_M_insert_multi_node): Likewise. Tested under Linux x64. François diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h index b0d1bc1f08a..011a707605f 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -288,10 +288,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION using __reuse_or_alloc_node_gen_t = __detail::_ReuseOrAllocNode<__node_alloc_type>; - using __alloc_node_gen_t = - __detail::_AllocNode<__node_alloc_type>; + using __alloc_node_gen_cache_bbegin_t = + __detail::_AllocNode<__node_alloc_type, __detail::_CacheBBeginPolicy>; using __node_builder_t = __detail::_NodeBuilder<_ExtractKey>; + using __no_cache_bbegin_policy_t = + __detail::_NoCacheBBeginPolicy; + using __cache_bbegin_policy_t = + __detail::_CacheBBeginPolicy; // Simple RAII type for managing a node containing an element struct _Scoped_node @@ -376,6 +380,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION bool _Unique_keysa> friend struct __detail::_Equality; + friend struct __detail::_CacheBBeginPolicy; + friend struct __detail::_NoCacheBBeginPolicy; + public: using size_type = typename __hashtable_base::size_type; using difference_type = typename __hashtable_base::difference_type; @@ -872,8 +879,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } // Insert a node at the beginning of a bucket. - void - _M_insert_bucket_begin(size_type, __node_ptr); + template + void + _M_insert_bucket_begin(size_type, __node_ptr, const _BBeginPolicy&); // Remove the bucket first node void @@ -890,15 +898,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION // Insert node __n with hash code __code, in bucket __bkt if no // rehash (assumes no element with same key already present). // Takes ownership of __n if insertion succeeds, throws otherwise. - iterator - _M_insert_unique_node(size_type __bkt, __hash_code, - __node_ptr __n, size_type __n_elt = 1); + template + iterator + _M_insert_unique_node(size_type __bkt, __hash_code, + __node_ptr __n, const _BBeginPolicy&, + size_type __n_elt = 1); // Insert node __n with key __k and hash code __code. // Takes ownership of __n if insertion succeeds, throws otherwise. - iterator - _M_insert_multi_node(__node_ptr __hint, - __hash_code __code, __node_ptr __n); + template + iterator + _M_insert_multi_node(__node_ptr __hint, __hash_code, + __node_ptr __n, const _BBeginPolicy&); template std::pair @@ -1087,8 +1098,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } else { + __no_cache_bbegin_policy_t __bbegin_policy; __ret.position - = _M_insert_unique_node(__bkt, __code, __nh._M_ptr); + = _M_insert_unique_node(__bkt, __code, __nh._M_ptr, + __bbegin_policy); __nh._M_ptr = nullptr; __ret.inserted = true; } @@ -1117,8 +1130,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __hint = cend(); } + __no_cache_bbegin_policy_t __bbegin_policy; auto __ret - = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr); + = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr, + __bbegin_policy); __nh._M_ptr = nullptr; return __ret; } @@ -1175,6 +1190,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); + __cache_bbegin_policy_t __bbegin_policy; auto __n_elt = __src.size(); for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) { @@ -1186,7 +1202,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION if (_M_find_node(__bkt, __k, __code) == nullptr) { auto __nh = __src.extract(__pos); - _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt); + _M_insert_unique_node(__bkt, __code, __nh._M_ptr, + __bbegin_policy, __n_elt); __nh._M_ptr = nullptr; __n_elt = 1; } @@ -1204,6 +1221,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION node_type>, "Node types are compatible"); __glibcxx_assert(get_allocator() == __src.get_allocator()); + __cache_bbegin_policy_t __bbegin_policy; __node_ptr __hint = nullptr; this->reserve(size() + __src.size()); for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;) @@ -1220,7 +1238,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } auto __nh = __src.extract(__pos); - __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur; + __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr, + __bbegin_policy)._M_cur; __nh._M_ptr = nullptr; } } @@ -1310,7 +1329,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count = __bkt_count; } - __alloc_node_gen_t __node_gen(*this); + __alloc_node_gen_cache_bbegin_t __node_gen(*this); for (; __f != __l; ++__f) _M_insert(*__f, __node_gen, __uks); } @@ -1345,10 +1364,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count = __ht._M_bucket_count; _M_element_count = __ht._M_element_count; _M_rehash_policy = __ht._M_rehash_policy; - __alloc_node_gen_t __alloc_node_gen(*this); + __alloc_node_gen_cache_bbegin_t __node_gen(*this); __try { - _M_assign(__ht, __alloc_node_gen); + _M_assign(__ht, __node_gen); } __catch(...) { @@ -1556,8 +1575,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_element_count(__ht._M_element_count), _M_rehash_policy(__ht._M_rehash_policy) { - __alloc_node_gen_t __alloc_node_gen(*this); - _M_assign(__ht, __alloc_node_gen); + __alloc_node_gen_cache_bbegin_t __node_gen(*this); + _M_assign(__ht, __node_gen); } template::value, const _Hashtable&, _Hashtable&&>; - _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen); + _M_assign(std::forward<_Fwd_Ht>(__ht), __node_gen); __ht.clear(); } } @@ -2079,34 +2097,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> - void - _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_bucket_begin(size_type __bkt, __node_ptr __node) - { - if (_M_buckets[__bkt]) - { - // Bucket is not empty, we just need to insert the new node - // after the bucket before begin. - __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; - _M_buckets[__bkt]->_M_nxt = __node; - } - else - { - // The bucket is empty, the new node is inserted at the - // beginning of the singly-linked list and the bucket will - // contain _M_before_begin pointer. - __node->_M_nxt = _M_before_begin._M_nxt; - _M_before_begin._M_nxt = __node; - - if (__node->_M_nxt) - // We must update former begin bucket that is pointing to - // _M_before_begin. - _M_buckets[_M_bucket_index(*__node->_M_next())] = __node; - - _M_buckets[__bkt] = &_M_before_begin; - } - } + template + void + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_insert_bucket_begin(size_type __bkt, __node_ptr __node, + const _BBeginPolicy& __bb_policy) + { + if (_M_buckets[__bkt]) + { + // Bucket is not empty, we just need to insert the new node + // after the bucket before begin. + __node->_M_nxt = _M_buckets[__bkt]->_M_nxt; + _M_buckets[__bkt]->_M_nxt = __node; + } + else + { + // The bucket is empty, the new node is inserted at the + // beginning of the singly-linked list and the bucket will + // contain _M_before_begin pointer. + __node->_M_nxt = _M_before_begin._M_nxt; + _M_before_begin._M_nxt = __node; + + if (__node->_M_nxt) + // We must update former begin bucket that is pointing to + // _M_before_begin. + _M_buckets[__bb_policy._M_get_bbegin_bkt(*this, __node->_M_next())] + = __node; + + __bb_policy._M_store_bbegin_bkt(__bkt); + _M_buckets[__bkt] = &_M_before_begin; + } + } template_M_v()); auto __res = this->_M_compute_hash_code(__hint, __k); + __no_cache_bbegin_policy_t __bbegin_policy; auto __pos = _M_insert_multi_node(__res.first._M_cur, __res.second, - __node._M_node); + __node._M_node, __bbegin_policy); __node._M_node = nullptr; return __pos; } @@ -2255,86 +2280,93 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _ExtractKey, typename _Equal, typename _Hash, typename _RangeHash, typename _Unused, typename _RehashPolicy, typename _Traits> - auto - _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_unique_node(size_type __bkt, __hash_code __code, - __node_ptr __node, size_type __n_elt) - -> iterator - { - const __rehash_state& __saved_state = _M_rehash_policy._M_state(); - std::pair __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, - __n_elt); + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_insert_unique_node(size_type __bkt, __hash_code __code, + __node_ptr __node, + const _BBeginPolicy& __bbegin_policy, + size_type __n_elt) + -> iterator + { + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, + __n_elt); - if (__do_rehash.first) - { - _M_rehash(__do_rehash.second, __saved_state); - __bkt = _M_bucket_index(__code); - } + if (__do_rehash.first) + { + _M_rehash(__do_rehash.second, __saved_state); + __bkt = _M_bucket_index(__code); + } - this->_M_store_code(*__node, __code); + this->_M_store_code(*__node, __code); - // Always insert at the beginning of the bucket. - _M_insert_bucket_begin(__bkt, __node); - ++_M_element_count; - return iterator(__node); - } + // Always insert at the beginning of the bucket. + _M_insert_bucket_begin(__bkt, __node, __bbegin_policy); + ++_M_element_count; + return iterator(__node); + } template - auto - _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, - _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: - _M_insert_multi_node(__node_ptr __hint, - __hash_code __code, __node_ptr __node) - -> iterator - { - const __rehash_state& __saved_state = _M_rehash_policy._M_state(); - std::pair __do_rehash - = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1); + template + auto + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_insert_multi_node(__node_ptr __hint, + __hash_code __code, __node_ptr __node, + const _BBeginPolicy& __bbegin_policy) + -> iterator + { + const __rehash_state& __saved_state = _M_rehash_policy._M_state(); + std::pair __do_rehash + = _M_rehash_policy._M_need_rehash(_M_bucket_count, + _M_element_count, 1); - if (__do_rehash.first) - _M_rehash(__do_rehash.second, __saved_state); + if (__do_rehash.first) + _M_rehash(__do_rehash.second, __saved_state); - this->_M_store_code(*__node, __code); - const key_type& __k = _ExtractKey{}(__node->_M_v()); - size_type __bkt = _M_bucket_index(__code); + this->_M_store_code(*__node, __code); + const key_type& __k = _ExtractKey{}(__node->_M_v()); + size_type __bkt = _M_bucket_index(__code); - // Find the node before an equivalent one or use hint if it exists and - // if it is equivalent. - __node_base_ptr __prev - = __builtin_expect(__hint != nullptr && - this->_M_equals(__k, __code, *__hint), false) - ? __hint - : _M_find_before_node(__bkt, __k, __code); + // Find the node before an equivalent one or use hint if it exists and + // if it is equivalent. + __node_base_ptr __prev + = __builtin_expect(__hint != nullptr && + this->_M_equals(__k, __code, *__hint), false) + ? __hint + : _M_find_before_node(__bkt, __k, __code); - if (__prev) - { - // Insert after the node before the equivalent one. - __node->_M_nxt = __prev->_M_nxt; - __prev->_M_nxt = __node; - if (__prev == __hint) [[__unlikely__]] - // hint might be the last bucket node, in this case we need to - // update next bucket. - if (__node->_M_nxt - && !this->_M_equals(__k, __code, *__node->_M_next())) - { - size_type __next_bkt = _M_bucket_index(*__node->_M_next()); - if (__next_bkt != __bkt) - _M_buckets[__next_bkt] = __node; - } - } - else - // The inserted node has no equivalent in the hashtable. We must - // insert the new node at the beginning of the bucket to preserve - // equivalent elements' relative positions. - _M_insert_bucket_begin(__bkt, __node); - ++_M_element_count; - return iterator(__node); - } + if (__prev) + { + // Insert after the node before the equivalent one. + __node->_M_nxt = __prev->_M_nxt; + __prev->_M_nxt = __node; + if (__prev == __hint) [[__unlikely__]] + // hint might be the last bucket node, in this case we need to + // update next bucket. + if (__node->_M_nxt + && !this->_M_equals(__k, __code, *__node->_M_next())) + { + size_type __next_bkt = _M_bucket_index(*__node->_M_next()); + if (__next_bkt != __bkt) + _M_buckets[__next_bkt] = __node; + } + } + else + // The inserted node has no equivalent in the hashtable. We must + // insert the new node at the beginning of the bucket to preserve + // equivalent elements' relative positions. + _M_insert_bucket_begin(__bkt, __node, __bbegin_policy); + ++_M_element_count; + return iterator(__node); + } // Insert v if no element with its key is already present. template_M_v())); auto __pos = _M_insert_multi_node(__res.first._M_cur, __res.second, - __node._M_node); + __node._M_node, __node_gen); __node._M_node = nullptr; return __pos; } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 139d0ec27df..ff206a6ed20 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -176,13 +176,47 @@ namespace __detail { return __node_gen(__hint, std::forward<_Kt>(__k)); } }; + struct _CacheBBeginPolicy + { + template + std::size_t + _M_get_bbegin_bkt(const _Ht& __ht, _NodePtr __n) const + { + if (!_M_initialized) + return __ht._M_bucket_index(*__n); + return _M_bbegin_index; + } + + void + _M_store_bbegin_bkt(std::size_t __bkt) const + { + _M_bbegin_index = __bkt; + _M_initialized = true; + } + + mutable bool _M_initialized = false; + mutable std::size_t _M_bbegin_index; + }; + + struct _NoCacheBBeginPolicy + { + template + std::size_t + _M_get_bbegin_bkt(const _Ht& __ht, _NodePtr __n) const + { return __ht._M_bucket_index(*__n); } + + void + _M_store_bbegin_bkt(std::size_t) const + { } + }; + template struct _Hashtable_alloc; // Functor recycling a pool of nodes and using allocation once the pool is // empty. template - struct _ReuseOrAllocNode + struct _ReuseOrAllocNode : _CacheBBeginPolicy { private: using __node_alloc_type = _NodeAlloc; @@ -236,8 +270,8 @@ namespace __detail // Functor similar to the previous one but without any pool of nodes to // recycle. - template - struct _AllocNode + template + struct _AllocNode : _BBeginPolicy { private: using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>; @@ -824,8 +858,10 @@ namespace __detail std::tuple(__k), std::tuple<>() }; + _NoCacheBBeginPolicy __bbegin_policy; auto __pos - = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); + = __h->_M_insert_unique_node(__bkt, __code, __node._M_node, + __bbegin_policy); __node._M_node = nullptr; return __pos->second; } @@ -852,8 +888,10 @@ namespace __detail std::forward_as_tuple(std::move(__k)), std::tuple<>() }; + _NoCacheBBeginPolicy __bbegin_policy; auto __pos - = __h->_M_insert_unique_node(__bkt, __code, __node._M_node); + = __h->_M_insert_unique_node(__bkt, __code, __node._M_node, + __bbegin_policy); __node._M_node = nullptr; return __pos->second; } @@ -901,7 +939,8 @@ namespace __detail using __unique_keys = typename _Traits::__unique_keys; using __node_alloc_type = typename __hashtable_alloc::__node_alloc_type; - using __node_gen_type = _AllocNode<__node_alloc_type>; + template + using __alloc_node_gen_t = _AllocNode<__node_alloc_type, _BBeginPolicy>; __hashtable& _M_conjure_hashtable() @@ -933,7 +972,7 @@ namespace __detail insert(const value_type& __v) { __hashtable& __h = _M_conjure_hashtable(); - __node_gen_type __node_gen(__h); + __alloc_node_gen_t<_NoCacheBBeginPolicy> __node_gen(__h); return __h._M_insert(__v, __node_gen, __unique_keys{}); } @@ -941,7 +980,7 @@ namespace __detail insert(const_iterator __hint, const value_type& __v) { __hashtable& __h = _M_conjure_hashtable(); - __node_gen_type __node_gen(__h); + __alloc_node_gen_t<_NoCacheBBeginPolicy> __node_gen(__h); return __h._M_insert(__hint, __v, __node_gen, __unique_keys{}); } @@ -961,8 +1000,10 @@ namespace __detail std::forward_as_tuple(std::forward<_KType>(__k)), std::forward_as_tuple(std::forward<_Args>(__args)...) }; + _NoCacheBBeginPolicy __bbegin_policy; auto __it - = __h._M_insert_unique_node(__bkt, __code, __node._M_node); + = __h._M_insert_unique_node(__bkt, __code, __node._M_node, + __bbegin_policy); __node._M_node = nullptr; return { __it, true }; } @@ -985,7 +1026,7 @@ namespace __detail insert(_InputIterator __first, _InputIterator __last) { __hashtable& __h = _M_conjure_hashtable(); - __node_gen_type __node_gen(__h); + __alloc_node_gen_t<_CacheBBeginPolicy> __node_gen(__h); return _M_insert_range(__first, __last, __node_gen, __unique_keys{}); } }; @@ -1076,15 +1117,15 @@ namespace __detail using __unique_keys = typename __base_type::__unique_keys; using __hashtable = typename __base_type::__hashtable; - using __node_gen_type = typename __base_type::__node_gen_type; - + using __alloc_node_gen_t + = typename __base_type::__alloc_node_gen_t<_NoCacheBBeginPolicy>; using __base_type::insert; __ireturn_type insert(value_type&& __v) { __hashtable& __h = this->_M_conjure_hashtable(); - __node_gen_type __node_gen(__h); + __alloc_node_gen_t __node_gen(__h); return __h._M_insert(std::move(__v), __node_gen, __unique_keys{}); } @@ -1092,7 +1133,7 @@ namespace __detail insert(const_iterator __hint, value_type&& __v) { __hashtable& __h = this->_M_conjure_hashtable(); - __node_gen_type __node_gen(__h); + __alloc_node_gen_t __node_gen(__h); return __h._M_insert(__hint, std::move(__v), __node_gen, __unique_keys{}); } From patchwork Mon Jun 20 16:58:31 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: 55205 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 B9A5F3851AB0 for ; Mon, 20 Jun 2022 17:06:25 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B9A5F3851AB0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1655744785; bh=6/gVPThlHo27RZdDl+Vg3TVUX5EDD9AuhhJ8SNY4rcE=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:Cc:From; b=UFTbj44Z8UPZlpY4Ce43Z4L4Hj6JSKgjBpdCs3cHwNIq9fQPvm/49Xu8kqaI/Dcko bYbiTBKP8YWnmKiLjWDQLMemuoH4GFmpplLe+FZOTvaYCJIkQ45V67LzWMdRtEIR6e Ulqo+P+IhfHtKFQ3/dxGxq+q6RAjSOmnbuU7FUqs= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ej1-x635.google.com (mail-ej1-x635.google.com [IPv6:2a00:1450:4864:20::635]) by sourceware.org (Postfix) with ESMTPS id 24D023851AB8; Mon, 20 Jun 2022 16:58:39 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 24D023851AB8 Received: by mail-ej1-x635.google.com with SMTP id ay16so2956526ejb.6; Mon, 20 Jun 2022 09:58:39 -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=6/gVPThlHo27RZdDl+Vg3TVUX5EDD9AuhhJ8SNY4rcE=; b=CeDN77avS9lLRBGOTK7li5pyf6Bu7wK8M2tRhxo1kWOjs3QJ8vP0JHk2zOOhB6NgoV MA47EH/qhPujWk/p/NeH+FxJLqpaNQNBgZatxw27MVYqyo4VyfFqhAv/Ss3be0SHcrKq bPnNiFSihc1xrgfJpPdC12xoqUlctR/d9Rxlw7CyBnXcMjoa4Ze+DhpRTz+/sI+lI3S4 +aY9q+TS87egZAevmmU/a21mrbwfGQo+4E1nkfdjHVvPEWg0ML1VIlITjufqq1Yes6jW 5Zp31i4O5OrGy4xMPYo8CVEpqpPW0mKNtcouuxPfjRBC8LE5QB6xixvupRD6wpmkqBaB 9M3Q== X-Gm-Message-State: AJIora87okxLTkaYr+fwL4sSpy5gLMB3PxzaVUS5aSdzbx2B6goA70vs DmCbcbpNsEvqsStnLaazOZ7bH5qZnwg= X-Google-Smtp-Source: AGRyM1sKnt7mg+fd5Bu14kBvu2jW2iY90T9ZzTO1mIJsuAH4wKojw+Hvmh5hN8gssm3ttUnuD9r79g== X-Received: by 2002:a17:907:8a17:b0:711:e3fe:7767 with SMTP id sc23-20020a1709078a1700b00711e3fe7767mr21226036ejc.380.1655744317769; Mon, 20 Jun 2022 09:58:37 -0700 (PDT) Received: from [10.126.3.254] ([109.190.253.11]) by smtp.googlemail.com with ESMTPSA id o16-20020a170906601000b0070662b3b792sm6233668ejj.222.2022.06.20.09.58.35 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 20 Jun 2022 09:58:37 -0700 (PDT) Message-ID: <524eabf5-179e-7432-3a6e-774609085680@gmail.com> Date: Mon, 20 Jun 2022 18:58:31 +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 5/5][_Hahtable] Prealloc nodes on copy To: "libstdc++@gcc.gnu.org" Content-Language: fr X-Spam-Status: No, score=-9.8 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] Prealloc nodes on _Hashtable copy Prealloc nodes on copy to reduce memory fragmentation of nodes. Create a new assignment method which copy hashtable instances respecting order of nodes in the bucket rather than order of node in the singly-linked list. libstdc++-v3/ChangeLog:     * include/bits/hashtable_policy.h: Include stl_tempbuf.h.     (_Hashtable_alloc<>::_M_allocate_node_ptr): New.     (_PreAllocHashtableNodes<>): New.     * include/bits/hashtable.h (_Hashtable<>::__prealloc_hashtable_nodes_gen_t): New.     (_Hashtable<>::_M_assign_stable):New.     (_Hashtable<>::operator=(const _Hashtable&)): Use latter.     (_Hashtable(const _Hashtable&)): Likewise.     (_Hashtable(const _Hashtable&, const allocator_type&)): Likewise.     (_Hashtable(_Hashtable&&, __node_alloc_type&&, false_type)): Likewise.     * testsuite/util/exception/safety.h (setup_base::compare): Compare containers     rather than compare iterators.     * testsuite/23_containers/unordered_multiset/cons/copy.cc (main): 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 011a707605f..b497f16d017 100644 --- a/libstdc++-v3/include/bits/hashtable.h +++ b/libstdc++-v3/include/bits/hashtable.h @@ -290,6 +290,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __detail::_ReuseOrAllocNode<__node_alloc_type>; using __alloc_node_gen_cache_bbegin_t = __detail::_AllocNode<__node_alloc_type, __detail::_CacheBBeginPolicy>; + using __prealloc_hashtable_nodes_gen_t = + __detail::_PreAllocHashtableNodes<__node_alloc_type>; + using __node_builder_t = __detail::_NodeBuilder<_ExtractKey>; using __no_cache_bbegin_policy_t = @@ -483,6 +486,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION void _M_assign(_Ht&&, const _NodeGenerator&); + template + void + _M_assign_stable(_Ht&&, const _NodeGenerator&); + void _M_move_assign(_Hashtable&&, true_type); @@ -1364,10 +1371,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _M_bucket_count = __ht._M_bucket_count; _M_element_count = __ht._M_element_count; _M_rehash_policy = __ht._M_rehash_policy; - __alloc_node_gen_cache_bbegin_t __node_gen(*this); __try { - _M_assign(__ht, __node_gen); + __prealloc_hashtable_nodes_gen_t __node_gen(__ht, *this); + _M_assign_stable(__ht, __node_gen); } __catch(...) { @@ -1487,6 +1494,72 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION } } + template + template + void + _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, + _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>:: + _M_assign_stable(_Ht&& __ht, const _NodeGenerator& __node_gen) + { + __buckets_ptr __buckets = nullptr; + if (!_M_buckets) + _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count); + + __try + { + if (!__ht._M_before_begin._M_nxt) + return; + + __node_ptr __prev_n = nullptr; + for (std::size_t __bkt = 0; __bkt != _M_bucket_count; ++__bkt) + { + if (__ht._M_buckets[__bkt] == nullptr) + continue; + + __node_ptr __ht_n = + static_cast<__node_ptr>(__ht._M_buckets[__bkt]->_M_nxt); + __node_ptr __prev_ht_n = __ht_n; + __node_base_ptr __nxt_bkt_n = __bkt < _M_bucket_count - 1 + ? __ht._M_buckets[__bkt + 1] : nullptr; + do + { + __node_ptr __this_n + = __node_gen(__prev_n, __bkt, + __fwd_value_for<_Ht>(__ht_n->_M_v())); + this->_M_copy_code(*__this_n, *__ht_n); + if (__prev_n) + { + if (!_M_buckets[__bkt]) + _M_buckets[__bkt] = __prev_n; + __prev_n->_M_nxt = __this_n; + } + else + { + _M_buckets[__bkt] = &_M_before_begin; + _M_before_begin._M_nxt = __this_n; + } + + __prev_n = __this_n; + __prev_ht_n = __ht_n; + __ht_n = __ht_n->_M_next(); + } + while (__ht_n + && __ht._M_is_nxt_in_bucket(__bkt, __prev_ht_n, + __nxt_bkt_n)); + } + } + __catch(...) + { + clear(); + if (__buckets) + _M_deallocate_buckets(); + __throw_exception_again; + } + } + template::value, const _Hashtable&, _Hashtable&&>; - _M_assign(std::forward<_Fwd_Ht>(__ht), __node_gen); + _M_assign_stable(std::forward<_Fwd_Ht>(__ht), __node_gen); __ht.clear(); } } diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index ff206a6ed20..becafcd3249 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -37,6 +37,7 @@ #include // for std::pair #include // for __gnu_cxx::__aligned_buffer #include // for std::__alloc_rebind +#include // for std::get_temporary_buffer. #include // for __gnu_cxx::__int_traits namespace std _GLIBCXX_VISIBILITY(default) @@ -291,6 +292,113 @@ namespace __detail __hashtable_alloc& _M_h; }; + template + struct _PreAllocHashtableNodes + { + private: + using __node_alloc_type = _NodeAlloc; + using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>; + using __node_alloc_traits = + typename __hashtable_alloc::__node_alloc_traits; + using __node_base = typename __hashtable_alloc::__node_base; + + public: + using __node_ptr = typename __hashtable_alloc::__node_ptr; + + template + _PreAllocHashtableNodes(_Ht& __ht, __hashtable_alloc& __ha) + : _M_h(__ha), _M_before_free_nodes() + , _M_buckets(std::get_temporary_buffer<__node_base*>(__ht.bucket_count())) + { + __builtin_memset(_M_buckets.first, 0, + _M_buckets.second * sizeof(__node_base*)); + __try + { + __node_ptr __hint = nullptr; + __node_base* __prev = std::__addressof(_M_before_free_nodes); + for (std::size_t __bkt = 0; __bkt != _M_buckets.second; ++__bkt) + for (auto __lit = __ht.begin(__bkt); __lit != __ht.end(__bkt); + ++__lit) + { + __node_ptr __tmp = _M_h._M_allocate_node_ptr(__hint); + if (!_M_buckets.first[__bkt]) + _M_buckets.first[__bkt] = __prev; + + __prev->_M_nxt = __tmp; + __prev = __hint = __tmp; + } + } + __catch(...) + { + _M_deallocate_nodes(); + __throw_exception_again; + } + } + + _PreAllocHashtableNodes(const _PreAllocHashtableNodes&) = delete; + + ~_PreAllocHashtableNodes() + { _M_deallocate_nodes(); } + + template + __node_ptr + operator()(__node_ptr __hint, std::size_t __bkt, _Args&&... __args) const + { + if (__bkt >= _M_buckets.second || _M_buckets.first[__bkt] == nullptr) + return _M_h._M_allocate_node(__hint, + std::forward<_Args>(__args)...); + + if (_M_buckets.first[__bkt] != std::__addressof(_M_before_free_nodes)) + { + _M_buckets.first[_M_last_access_bkt] = nullptr; + _M_buckets.first[__bkt] = std::__addressof(_M_before_free_nodes); + } + + _M_last_access_bkt = __bkt; + auto __prev = _M_buckets.first[__bkt]; + __node_ptr __node = static_cast<__node_ptr>(__prev->_M_nxt); + _M_before_free_nodes._M_nxt = __node->_M_nxt; + if (_M_before_free_nodes._M_nxt == nullptr) + _M_buckets.first[__bkt] = nullptr; + + __node->_M_nxt = nullptr; + auto& __a = _M_h._M_node_allocator(); + __try + { + __node_alloc_traits::construct(__a, __node->_M_valptr(), + std::forward<_Args>(__args)...); + } + __catch(...) + { + _M_h._M_deallocate_node_ptr(__node); + __throw_exception_again; + } + + return __node; + } + + private: + void + _M_deallocate_nodes() + { + __node_ptr __n + = static_cast<__node_ptr>(_M_before_free_nodes._M_nxt); + while (__n) + { + __node_ptr __tmp = __n; + __n = __n->_M_next(); + _M_h._M_deallocate_node_ptr(__tmp); + } + + std::return_temporary_buffer(_M_buckets.first); + } + + mutable __node_base _M_before_free_nodes; + mutable std::pair<__node_base**, std::ptrdiff_t> _M_buckets; + mutable std::size_t _M_last_access_bkt = 0; + __hashtable_alloc& _M_h; + }; + // Auxiliary types used for all instantiations of _Hashtable nodes // and iterators. @@ -2031,6 +2139,10 @@ namespace __detail _M_node_allocator() const { return __ebo_node_alloc::_M_cget(); } + // Allocate a node. + __node_ptr + _M_allocate_node_ptr(__node_ptr __hint); + // Allocate a node and construct an element within it. template __node_ptr @@ -2058,6 +2170,27 @@ namespace __detail // Definitions of class template _Hashtable_alloc's out-of-line member // functions. + template + auto + _Hashtable_alloc<_NodeAlloc>::_M_allocate_node_ptr(__node_ptr __hint) + -> __node_ptr + { + auto& __alloc = _M_node_allocator(); + typename __node_alloc_traits::pointer __nptr; + if (__hint) + { + typedef typename __node_alloc_traits::const_pointer _CPtr; + auto __hptr = std::pointer_traits<_CPtr>::pointer_to(*__hint); + __nptr = __node_alloc_traits::allocate(__alloc, 1, __hptr); + } + else + __nptr = __node_alloc_traits::allocate(__alloc, 1); + + __node_ptr __n = std::__to_address(__nptr); + ::new ((void*)__n) __node_type; + return __n; + } + template template auto diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/copy.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/copy.cc index 22bedb9065f..c4e521ab662 100644 --- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/copy.cc +++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/copy.cc @@ -38,6 +38,6 @@ int main() std::unordered_multiset copy(ref); VERIFY( copy.size() == ref.size() ); - VERIFY( std::equal(ref.begin(), ref.end(), copy.begin()) ); + VERIFY( copy == ref ); return 0; } diff --git a/libstdc++-v3/testsuite/util/exception/safety.h b/libstdc++-v3/testsuite/util/exception/safety.h index 8ef91648af6..ad55812be1a 100644 --- a/libstdc++-v3/testsuite/util/exception/safety.h +++ b/libstdc++-v3/testsuite/util/exception/safety.h @@ -235,12 +235,11 @@ namespace __gnu_test "setup_base::compare containers size not equal"); // Should test iterator validity before and after exception. - bool __equal_it = std::equal(__test.begin(), __test.end(), - __control.begin()); + bool __equal = __test == __control; - if (!__equal_it) + if (!__equal) throw std::logic_error( - "setup_base::compare containers iterators not equal"); + "setup_base::compare containers not equal"); return true; }