From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x330.google.com (mail-wm1-x330.google.com [IPv6:2a00:1450:4864:20::330]) by sourceware.org (Postfix) with ESMTPS id E20A03858422; Thu, 18 Nov 2021 22:04:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E20A03858422 Received: by mail-wm1-x330.google.com with SMTP id j140-20020a1c2392000000b003399ae48f58so958135wmj.5; Thu, 18 Nov 2021 14:04:19 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:to:cc:from:subject:message-id:date:user-agent :mime-version:content-language; bh=bkQVjRJ/+W0XtLBYSv+mbpB1Ts0wzDKQhwyk/Ztrg7I=; b=EkeQ43xntPlr+IqFlJfKMlw86YGwq9KHSjMzXW28b/pRGlAKi7sBlhbW7/TdyBEkaE y8cV8udydi1NjoKKk3epoG3TlFtDTIU2ppz8IskzjesHkbjTntB5EXZxid9x7rki1MEv S2t3o1qwxB11BPbOFh1azEE+6/s06/anmXeBzb5V00zuVRvIJDlfwTpg+L5RsXninTBb 6j6TusRkPYqGdwhX++qVx16vu9g26gTid42DGRQxMmfHeqn3yPkod/lOHLwQJW/XAKS3 fh9OKWdBcAOzLSEOdWOcFJvkWP3bJi8FRbTQUGPhbBzywcioljd9w/0oI7Heejv/YyVJ Jzww== X-Gm-Message-State: AOAM531VB3a03hjtxvt6knDPE0FMoPYtRDugmUACRuKQ7MiTbVaprTzn K65Ad7FAizVqnaI0EGrOdOzX7XTmHT8= X-Google-Smtp-Source: ABdhPJxyPsrPZqu+3IbkcrBHUc3/A7MZPXCgEGY8snSoeeZWR2aloym1/J7Cat7GyDeLpK91QK9jAQ== X-Received: by 2002:a05:600c:1e27:: with SMTP id ay39mr565268wmb.84.1637273058125; Thu, 18 Nov 2021 14:04:18 -0800 (PST) Received: from ?IPv6:2a01:e0a:1dc:b1c0:a41f:e664:6fe4:d4c? ([2a01:e0a:1dc:b1c0:a41f:e664:6fe4:d4c]) by smtp.googlemail.com with ESMTPSA id d6sm1025638wrx.60.2021.11.18.14.04.17 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 18 Nov 2021 14:04:17 -0800 (PST) To: "libstdc++@gcc.gnu.org" Cc: gcc-patches From: =?UTF-8?Q?Fran=c3=a7ois_Dumont?= Subject: [PATCH][_GLIBCXX_DEBUG] Limit performance impact in __erase_nodes_if Message-ID: <5f218fb2-57ba-06c9-1821-86d3ded43bf7@gmail.com> Date: Thu, 18 Nov 2021 23:04:16 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.13.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------B632C36E4691D5F7BAB33A34" Content-Language: fr X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, BODY_8BITS, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, FREEMAIL_FROM, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 18 Nov 2021 22:04:23 -0000 This is a multi-part message in MIME format. --------------B632C36E4691D5F7BAB33A34 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Hi     Here is a proposal to limit performance impact of _GLIBCXX_DEBUG mode on __erase_nodes_if.     As you can see I am adding erase overloads on the Debug container to accept base iterators. So it exposes an additional non-Standard method, do you think it is any issue.     Note that I've started doing something similar for the vector/deque adding this time erase(_Base_const_iterator, _Base_const_iterator) overloads. But in this case it results in ambiguous erase calls, even if I remove the _Safe_iterator cast operator to the base iterator.     libstdc++: [_GLIBCXX_DEBUG] Reduce performance impact on std::erase_if     Bypass the _GLIBCXX_DEBUG additional checks in std::__detail::__erase_node_if used     by all implementations of std::erase_if for node based containers.     libstdc++-v3/ChangeLog:             * include/bits/erase_if.h (__erase_nodes_if): Add _UnsafeContainer template             parameter. Use it to get iterators to work with.             * include/debug/macros.h (__glibcxx_check_erase2): New.             * include/debug/map.h (map<>::erase(_Base_const_iterator)): New.             (map<>::erase(const_iterator)): Use latter.             * include/debug/multimap.h (multimap<>::erase(_Base_const_iterator)): New.             (multimap<>::erase(const_iterator)): Use latter.             * include/debug/multiset.h (multiset<>::erase(_Base_const_iterator)): New.             (multiset<>::erase(const_iterator)): Use latter.             * include/debug/set.h (set<>::erase(_Base_const_iterator)): New.             (set<>::erase(const_iterator)): Use latter.             * include/debug/unordered_map (unordered_map<>::erase(_Base_const_iterator)): New.             (unordered_multimap<>::erase(const_iterator)): New.             * include/debug/unordered_set (unordered_set<>::erase(_Base_const_iterator)): New.             (unordered_multiset<>::erase(const_iterator)): New.             * include/experimental/map (erase_if): Adapt.             * include/experimental/set (erase_if): Adapt.             * include/experimental/unordered_map (erase_if): Adapt.             * include/experimental/unordered_set (erase_if): Adapt.             * include/std/map (erase_if): Adapt.             * include/std/set (erase_if): Adapt.             * include/std/unordered_map (erase_if): Adapt.             * include/std/unordered_set (erase_if): Adapt. Tested under Linux x86_64, Ok to commit ? François --------------B632C36E4691D5F7BAB33A34 Content-Type: text/x-patch; charset=UTF-8; name="erase_node_if.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="erase_node_if.patch" diff --git a/libstdc++-v3/include/bits/erase_if.h b/libstdc++-v3/include/bits/erase_if.h index 8d1d23168fa..61f88e3cca3 100644 --- a/libstdc++-v3/include/bits/erase_if.h +++ b/libstdc++-v3/include/bits/erase_if.h @@ -46,12 +46,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace __detail { - template + template typename _Container::size_type - __erase_nodes_if(_Container& __cont, _Predicate __pred) + __erase_nodes_if(_Container& __cont, const _UnsafeContainer& __ucont, + _Predicate __pred) { typename _Container::size_type __num = 0; - for (auto __iter = __cont.begin(), __last = __cont.end(); + for (auto __iter = __ucont.begin(), __last = __ucont.end(); __iter != __last;) { if (__pred(*__iter)) diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h index 9e1288cf4d9..0183d2a8223 100644 --- a/libstdc++-v3/include/debug/macros.h +++ b/libstdc++-v3/include/debug/macros.h @@ -219,6 +219,14 @@ _GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ ._M_sequence(*this, "this") \ ._M_iterator(_Position, #_Position)) +#if __cplusplus >= 201103L +# define __glibcxx_check_erase2(_CPosition) \ +_GLIBCXX_DEBUG_VERIFY(_CPosition != _M_base().cend(), \ + _M_message(__gnu_debug::__msg_erase_bad) \ + ._M_sequence(*this, "this") \ + ._M_iterator(_CPosition, #_CPosition)); +#endif + /** Verify that we can erase the element after the iterator * _Position. We can erase the element if the _Position iterator is * before a dereferenceable one and references this sequence. diff --git a/libstdc++-v3/include/debug/map.h b/libstdc++-v3/include/debug/map.h index c62f0b574e6..f13a25d4701 100644 --- a/libstdc++-v3/include/debug/map.h +++ b/libstdc++-v3/include/debug/map.h @@ -480,8 +480,15 @@ namespace __debug erase(const_iterator __position) { __glibcxx_check_erase(__position); - this->_M_invalidate_if(_Equal(__position.base())); - return { _Base::erase(__position.base()), this }; + return { erase(__position.base()), this }; + } + + _Base_iterator + erase(_Base_const_iterator __position) + { + __glibcxx_check_erase2(__position); + this->_M_invalidate_if(_Equal(__position)); + return _Base::erase(__position); } _GLIBCXX_ABI_TAG_CXX11 diff --git a/libstdc++-v3/include/debug/multimap.h b/libstdc++-v3/include/debug/multimap.h index 5f0f1faa33e..b7c2388082b 100644 --- a/libstdc++-v3/include/debug/multimap.h +++ b/libstdc++-v3/include/debug/multimap.h @@ -360,8 +360,15 @@ namespace __debug erase(const_iterator __position) { __glibcxx_check_erase(__position); - this->_M_invalidate_if(_Equal(__position.base())); - return { _Base::erase(__position.base()), this }; + return { erase(__position.base()), this }; + } + + _Base_iterator + erase(_Base_const_iterator __position) + { + __glibcxx_check_erase2(__position); + this->_M_invalidate_if(_Equal(__position)); + return _Base::erase(__position); } _GLIBCXX_ABI_TAG_CXX11 diff --git a/libstdc++-v3/include/debug/multiset.h b/libstdc++-v3/include/debug/multiset.h index 7729fc19689..30e93e4f038 100644 --- a/libstdc++-v3/include/debug/multiset.h +++ b/libstdc++-v3/include/debug/multiset.h @@ -332,8 +332,15 @@ namespace __debug erase(const_iterator __position) { __glibcxx_check_erase(__position); - this->_M_invalidate_if(_Equal(__position.base())); - return { _Base::erase(__position.base()), this }; + return { erase(__position.base()), this }; + } + + _Base_iterator + erase(_Base_const_iterator __position) + { + __glibcxx_check_erase2(__position); + this->_M_invalidate_if(_Equal(__position)); + return _Base::erase(__position); } #else void diff --git a/libstdc++-v3/include/debug/set.h b/libstdc++-v3/include/debug/set.h index 39142aef60b..0eaabf47d34 100644 --- a/libstdc++-v3/include/debug/set.h +++ b/libstdc++-v3/include/debug/set.h @@ -345,8 +345,15 @@ namespace __debug erase(const_iterator __position) { __glibcxx_check_erase(__position); - this->_M_invalidate_if(_Equal(__position.base())); - return { _Base::erase(__position.base()), this }; + return { erase(__position.base()), this }; + } + + _Base_iterator + erase(_Base_const_iterator __position) + { + __glibcxx_check_erase2(__position); + this->_M_invalidate_if(_Equal(__position)); + return _Base::erase(__position); } #else void diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map index 64cc8bacabd..8ccb60c17db 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -679,6 +679,13 @@ namespace __debug return { _M_erase(__it.base()), this }; } + _Base_iterator + erase(_Base_const_iterator __it) + { + __glibcxx_check_erase2(__it); + return _M_erase(__it); + } + iterator erase(iterator __it) { @@ -1389,6 +1396,13 @@ namespace __debug return { _M_erase(__it.base()), this }; } + _Base_iterator + erase(_Base_const_iterator __it) + { + __glibcxx_check_erase2(__it); + return _M_erase(__it); + } + iterator erase(iterator __it) { diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set index 3516af4dc4e..716635fc20c 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -564,6 +564,13 @@ namespace __debug return { _M_erase(__it.base()), this }; } + _Base_iterator + erase(_Base_const_iterator __it) + { + __glibcxx_check_erase2(__it); + return _M_erase(__it); + } + iterator erase(iterator __it) { @@ -1234,6 +1241,13 @@ namespace __debug return { _M_erase(__it.base()), this }; } + _Base_iterator + erase(_Base_const_iterator __it) + { + __glibcxx_check_erase2(__it); + return _M_erase(__it); + } + iterator erase(iterator __it) { diff --git a/libstdc++-v3/include/experimental/map b/libstdc++-v3/include/experimental/map index 0c0f42222f5..13304320232 100644 --- a/libstdc++-v3/include/experimental/map +++ b/libstdc++-v3/include/experimental/map @@ -50,13 +50,21 @@ inline namespace fundamentals_v2 typename _Predicate> inline void erase_if(map<_Key, _Tp, _Compare, _Alloc>& __cont, _Predicate __pred) - { std::__detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Alloc>& + __ucont = __cont; + std::__detail::__erase_nodes_if(__cont, __ucont, __pred); + } template inline void erase_if(multimap<_Key, _Tp, _Compare, _Alloc>& __cont, _Predicate __pred) - { std::__detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Alloc>& + __ucont = __cont; + std::__detail::__erase_nodes_if(__cont, __ucont, __pred); + } namespace pmr { template> diff --git a/libstdc++-v3/include/experimental/set b/libstdc++-v3/include/experimental/set index c3f5433e995..2a56ede5cf1 100644 --- a/libstdc++-v3/include/experimental/set +++ b/libstdc++-v3/include/experimental/set @@ -50,13 +50,19 @@ inline namespace fundamentals_v2 typename _Predicate> inline void erase_if(set<_Key, _Compare, _Alloc>& __cont, _Predicate __pred) - { std::__detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::set<_Key, _Compare, _Alloc>& __ucont = __cont; + std::__detail::__erase_nodes_if(__cont, __ucont, __pred); + } template inline void erase_if(multiset<_Key, _Compare, _Alloc>& __cont, _Predicate __pred) - { std::__detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::multiset<_Key, _Compare, _Alloc>& __ucont = __cont; + std::__detail::__erase_nodes_if(__cont, __ucont, __pred); + } namespace pmr { template> diff --git a/libstdc++-v3/include/experimental/unordered_map b/libstdc++-v3/include/experimental/unordered_map index 0b915ab13e5..69f209d83e7 100644 --- a/libstdc++-v3/include/experimental/unordered_map +++ b/libstdc++-v3/include/experimental/unordered_map @@ -51,14 +51,22 @@ inline namespace fundamentals_v2 inline void erase_if(unordered_map<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont, _Predicate __pred) - { std::__detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _CPred, _Alloc>& + __ucont = __cont; + std::__detail::__erase_nodes_if(__cont, __ucont, __pred); + } template inline void erase_if(unordered_multimap<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont, _Predicate __pred) - { std::__detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _CPred, _Alloc>& + __ucont = __cont; + std::__detail::__erase_nodes_if(__cont, __ucont, __pred); + } namespace pmr { template, diff --git a/libstdc++-v3/include/experimental/unordered_set b/libstdc++-v3/include/experimental/unordered_set index 87db4464401..fbab7e7ddb5 100644 --- a/libstdc++-v3/include/experimental/unordered_set +++ b/libstdc++-v3/include/experimental/unordered_set @@ -51,14 +51,22 @@ inline namespace fundamentals_v2 inline void erase_if(unordered_set<_Key, _Hash, _CPred, _Alloc>& __cont, _Predicate __pred) - { std::__detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::unordered_set<_Key, _Hash, _CPred, _Alloc>& + __ucont = __cont; + std::__detail::__erase_nodes_if(__cont, __ucont, __pred); + } template inline void erase_if(unordered_multiset<_Key, _Hash, _CPred, _Alloc>& __cont, _Predicate __pred) - { std::__detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::unordered_multiset<_Key, _Hash, _CPred, _Alloc>& + __ucont = __cont; + std::__detail::__erase_nodes_if(__cont, __ucont, __pred); + } namespace pmr { template, diff --git a/libstdc++-v3/include/std/map b/libstdc++-v3/include/std/map index 44bd44b5922..d71fd047e82 100644 --- a/libstdc++-v3/include/std/map +++ b/libstdc++-v3/include/std/map @@ -95,13 +95,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Predicate> inline typename map<_Key, _Tp, _Compare, _Alloc>::size_type erase_if(map<_Key, _Tp, _Compare, _Alloc>& __cont, _Predicate __pred) - { return __detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Alloc>& __ucont = __cont; + return __detail::__erase_nodes_if(__cont, __ucont, __pred); + } template inline typename multimap<_Key, _Tp, _Compare, _Alloc>::size_type erase_if(multimap<_Key, _Tp, _Compare, _Alloc>& __cont, _Predicate __pred) - { return __detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Alloc>& __ucont = __cont; + return __detail::__erase_nodes_if(__cont, __ucont, __pred); + } _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // C++20 diff --git a/libstdc++-v3/include/std/set b/libstdc++-v3/include/std/set index f1e1864937a..10178b65785 100644 --- a/libstdc++-v3/include/std/set +++ b/libstdc++-v3/include/std/set @@ -91,13 +91,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION typename _Predicate> inline typename set<_Key, _Compare, _Alloc>::size_type erase_if(set<_Key, _Compare, _Alloc>& __cont, _Predicate __pred) - { return __detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::set<_Key, _Compare, _Alloc>& __ucont = __cont; + return __detail::__erase_nodes_if(__cont, __ucont, __pred); + } template inline typename multiset<_Key, _Compare, _Alloc>::size_type erase_if(multiset<_Key, _Compare, _Alloc>& __cont, _Predicate __pred) - { return __detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::multiset<_Key, _Compare, _Alloc>& __ucont = __cont; + return __detail::__erase_nodes_if(__cont, __ucont, __pred); + } _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // C++20 diff --git a/libstdc++-v3/include/std/unordered_map b/libstdc++-v3/include/std/unordered_map index e6715069362..0c8b076a1eb 100644 --- a/libstdc++-v3/include/std/unordered_map +++ b/libstdc++-v3/include/std/unordered_map @@ -83,7 +83,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline typename unordered_map<_Key, _Tp, _Hash, _CPred, _Alloc>::size_type erase_if(unordered_map<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont, _Predicate __pred) - { return __detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _CPred, _Alloc>& + __ucont = __cont; + return __detail::__erase_nodes_if(__cont, __ucont, __pred); + } template @@ -91,7 +95,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION size_type erase_if(unordered_multimap<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont, _Predicate __pred) - { return __detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _CPred, _Alloc>& + __ucont = __cont; + return __detail::__erase_nodes_if(__cont, __ucont, __pred); + } _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // C++20 diff --git a/libstdc++-v3/include/std/unordered_set b/libstdc++-v3/include/std/unordered_set index 1ad93d0031b..3a33f573499 100644 --- a/libstdc++-v3/include/std/unordered_set +++ b/libstdc++-v3/include/std/unordered_set @@ -83,14 +83,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION inline typename unordered_set<_Key, _Hash, _CPred, _Alloc>::size_type erase_if(unordered_set<_Key, _Hash, _CPred, _Alloc>& __cont, _Predicate __pred) - { return __detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::unordered_set<_Key, _Hash, _CPred, _Alloc>& + __ucont = __cont; + return __detail::__erase_nodes_if(__cont, __ucont, __pred); + } template inline typename unordered_multiset<_Key, _Hash, _CPred, _Alloc>::size_type erase_if(unordered_multiset<_Key, _Hash, _CPred, _Alloc>& __cont, _Predicate __pred) - { return __detail::__erase_nodes_if(__cont, __pred); } + { + const _GLIBCXX_STD_C::unordered_multiset<_Key, _Hash, _CPred, _Alloc>& + __ucont = __cont; + return __detail::__erase_nodes_if(__cont, __ucont, __pred); + } _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // C++20 --------------B632C36E4691D5F7BAB33A34--