From: "François Dumont" <frs.dumont@gmail.com>
To: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>
Cc: gcc-patches <gcc-patches@gcc.gnu.org>
Subject: [PATCH][_GLIBCXX_DEBUG] Limit performance impact in __erase_nodes_if
Date: Thu, 18 Nov 2021 23:04:16 +0100 [thread overview]
Message-ID: <5f218fb2-57ba-06c9-1821-86d3ded43bf7@gmail.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 2757 bytes --]
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
[-- Attachment #2: erase_node_if.patch --]
[-- Type: text/x-patch, Size: 15715 bytes --]
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<typename _Container, typename _Predicate>
+ template<typename _Container, typename _UnsafeContainer,
+ typename _Predicate>
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<typename _Key, typename _Tp, typename _Compare, typename _Alloc,
typename _Predicate>
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<typename _Key, typename _Tp, typename _Compare = less<_Key>>
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<typename _Key, typename _Compare, typename _Alloc,
typename _Predicate>
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<typename _Key, typename _Compare = less<_Key>>
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<typename _Key, typename _Tp, typename _Hash, typename _CPred,
typename _Alloc, typename _Predicate>
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<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
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<typename _Key, typename _Hash, typename _CPred, typename _Alloc,
typename _Predicate>
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<typename _Key, typename _Hash = hash<_Key>,
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<typename _Key, typename _Tp, typename _Compare, typename _Alloc,
typename _Predicate>
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<typename _Key, typename _Compare, typename _Alloc,
typename _Predicate>
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<typename _Key, typename _Tp, typename _Hash, typename _CPred,
typename _Alloc, typename _Predicate>
@@ -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<typename _Key, typename _Hash, typename _CPred, typename _Alloc,
typename _Predicate>
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
next reply other threads:[~2021-11-18 22:04 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-11-18 22:04 François Dumont [this message]
2021-11-19 10:43 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=5f218fb2-57ba-06c9-1821-86d3ded43bf7@gmail.com \
--to=frs.dumont@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).