Hi
libstdc++: [_GLIBCXX_DEBUG] Reduce unordered containers mutex
locks/unlocks
The unordered containers have 2 types of iterators, the usual ones
and the
local_iterator to iterate through a given bucket. In _GLIBCXX_DEBUG
mode there
are then 4 lists of iterators, 2 for iterator/const_iterator and 2 for
local_iterator/const_local_iterator.
This patch is making sure that the unordered container's mutex is
only lock/unlock
1 time when those lists of iterators needed to be iterate to
invalidate some of
them.
Also remove calls to _M_check_rehashed after erase operations.
Standard do not permit
to rehash on erase operation so we will never implement it.
libstdc++-v3/ChangeLog
* include/debug/safe_unordered_container.h
(__gnu_debug::_Safe_unordered_container<>::_M_invalidate_all()): Lock mutex
while calling _M_invalidate_if and _M_invalidate_locals.
(_Safe_unordered_container<>::_M_invalidate_all_if<_Pred>()): New.
(_Safe_unordered_container<>::_M_invalidate_all_single_if<_Pred>()): New.
(_Safe_unordered_container<>::struct _InvalidatePred<>): New.
(_Safe_unordered_container<>::_M_invalidate<_It>(_It)): New.
(_Safe_unordered_container<>::_M_invalidate_single<_It>(_It)): New.
* include/debug/safe_unordered_container.tcc
(_Safe_unordered_container<>::_M_invalidate_if<_Pred>(_Pred)): Remove lock.
(_Safe_unordered_container<>::_M_invalidate_local_if<_Pred>(_Pred)):
Remove lock.
* include/debug/unordered_map
(unordered_map<>::erase(const_iterator, const_iterator)):
Add lock before loop
for iterator invalidation. Use _M_invalidate_single for
invalidation. Remove
_M_check_rehashed call.
(unordered_map<>::_M_self()): New.
(unordered_map<>::_M_invalidate(_Base_const_iterator)): Remove.
(unordered_map<>::_M_erase(_Base_const_iterator)): Adapt. Remove
_M_check_rehashed
call.
(unordered_multimap<>::erase(const key_type&)): Add lock
before loop for iterator
invalidation. Use _M_invalidate_single for invalidation.
Remove _M_check_rehashed
call.
(unordered_multimap<>::erase(const_iterator,
const_iterator)): Likewise.
(unordered_multimap<>::_M_self()): New.
(unordered_multimap<>::_M_invalidate(_Base_const_iterator)): Remove.
(unordered_multimap<>::_M_erase(_Base_const_iterator)): Adapt. Remove
_M_check_rehashed
call.
* include/debug/unordered_set
(unordered_set<>::erase(const_iterator, const_iterator)):
Add lock before loop
for iterator invalidation. Use _M_invalidate_single for
invalidation. Remove
_M_check_rehashed call.
(unordered_set<>::_M_self()): New.
(unordered_set<>::_M_invalidate(_Base_const_iterator)): Remove.
(unordered_set<>::_M_erase(_Base_const_iterator)): Adapt. Remove
_M_check_rehashed
call.
(unordered_multiset<>::erase(const key_type&)): Add lock
before loop for iterator
invalidation. Use _M_invalidate_single for invalidation.
Remove _M_check_rehashed
call.
(unordered_multiset<>::erase(const_iterator,
const_iterator)): Likewise.
(unordered_multiset<>::_M_self()): New.
(unordered_multiset<>::_M_invalidate(_Base_const_iterator)): Remove.
(unordered_multiset<>::_M_erase(_Base_const_iterator)): Adapt. Remove
_M_check_rehashed
call.
All 23_containers/unordered_* tests run under Linux x64_86 in
_GLIBCXX_DEBUG mode.
Note that patch was generated with a git diff -b option.
Ok to commit ?
François
diff --git a/libstdc++-v3/include/debug/safe_unordered_container.h
b/libstdc++-v3/include/debug/safe_unordered_container.h
index e76d60d2605..0571efaba49 100644
--- a/libstdc++-v3/include/debug/safe_unordered_container.h
+++ b/libstdc++-v3/include/debug/safe_unordered_container.h
@@ -57,7 +57,6 @@ namespace __gnu_debug
template<typename _Container>
class _Safe_unordered_container : public _Safe_unordered_container_base
{
- private:
_Container&
_M_cont() noexcept
{ return *static_cast<_Container*>(this); }
@@ -66,17 +65,17 @@ namespace __gnu_debug
_M_self() const
{ return this; }
- protected:
void
_M_invalidate_locals()
{
auto __local_end = _M_cont()._M_base().cend(0);
- this->_M_invalidate_local_if(
+ _M_invalidate_local_if(
[__local_end](__decltype(__local_end) __it)
{ return __it != __local_end; });
}
#if __cplusplus > 201402L
+ protected:
template<typename _ExtractKey, typename _Source>
struct _UContInvalidatePred
{
@@ -130,10 +129,7 @@ namespace __gnu_debug
if (__size == 0)
_M_source._M_invalidate_all();
else
- {
- _M_source._M_invalidate_if(_M_pred);
- _M_source._M_invalidate_local_if(_M_pred);
- }
+ _M_source._M_invalidate_all_if(_M_pred);
}
__catch(...)
{
@@ -169,12 +165,61 @@ namespace __gnu_debug
void
_M_invalidate_all()
{
+ __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
auto __end = _M_cont()._M_base().cend();
- this->_M_invalidate_if([__end](__decltype(__end) __it)
+ _M_invalidate_if([__end](__decltype(__end) __it)
{ return __it != __end; });
_M_invalidate_locals();
}
+ template<typename _Predicate>
+ void
+ _M_invalidate_all_if(_Predicate __pred)
+ {
+ __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
+ _M_invalidate_all_single_if(__pred);
+ }
+
+ protected:
+ template<typename _Predicate>
+ void
+ _M_invalidate_all_single_if(_Predicate __pred)
+ {
+ _M_invalidate_if(__pred);
+ _M_invalidate_local_if(__pred);
+ }
+
+ template<typename _VictimIt>
+ struct _InvalidatePred
+ {
+ _InvalidatePred(_VictimIt __victim)
+ : _M_victim(__victim) { }
+
+ template<typename _Iterator>
+ bool
+ operator()(_Iterator __it) const
+ { return __it == _M_victim; }
+
+ _VictimIt _M_victim;
+ };
+
+ template<typename _VictimIt>
+ void
+ _M_invalidate(_VictimIt __victim)
+ {
+ _InvalidatePred<_VictimIt> __pred(__victim);
+ _M_invalidate_all_if(__pred);
+ }
+
+ template<typename _VictimIt>
+ void
+ _M_invalidate_single(_VictimIt __victim)
+ {
+ _InvalidatePred<_VictimIt> __pred(__victim);
+ _M_invalidate_all_single_if(__pred);
+ }
+
+ private:
/** Invalidates all iterators @c x that reference this container,
are not singular, and for which @c __pred(x) returns @c
true. @c __pred will be invoked with the normal iterators nested
diff --git a/libstdc++-v3/include/debug/safe_unordered_container.tcc
b/libstdc++-v3/include/debug/safe_unordered_container.tcc
index f60761534c8..6f2975116c7 100644
--- a/libstdc++-v3/include/debug/safe_unordered_container.tcc
+++ b/libstdc++-v3/include/debug/safe_unordered_container.tcc
@@ -40,7 +40,6 @@ namespace __gnu_debug
typedef typename _Container::iterator iterator;
typedef typename _Container::const_iterator const_iterator;
- __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
for (_Safe_iterator_base* __iter = _M_iterators; __iter;)
{
iterator* __victim = static_cast<iterator*>(__iter);
@@ -72,7 +71,6 @@ namespace __gnu_debug
typedef typename _Container::local_iterator local_iterator;
typedef typename _Container::const_local_iterator const_local_iterator;
- __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
for (_Safe_iterator_base* __iter = _M_local_iterators; __iter;)
{
local_iterator* __victim = static_cast<local_iterator*>(__iter);
diff --git a/libstdc++-v3/include/debug/unordered_map
b/libstdc++-v3/include/debug/unordered_map
index 4bde18c917b..30953417edc 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -738,18 +738,19 @@ namespace __debug
erase(const_iterator __first, const_iterator __last)
{
__glibcxx_check_erase_range(__first, __last);
+ {
+ __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
{
_GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
_M_message(__gnu_debug::__msg_valid_range)
._M_iterator(__first, "first")
._M_iterator(__last, "last"));
- _M_invalidate(__tmp);
+ this->_M_invalidate_single(__tmp);
+ }
}
- size_type __bucket_count = this->bucket_count();
auto __next = _Base::erase(__first.base(), __last.base());
- _M_check_rehashed(__bucket_count);
return { __next, this };
}
@@ -763,6 +764,10 @@ namespace __debug
_M_base() const noexcept { return *this; }
private:
+ const unordered_map*
+ _M_self() const noexcept
+ { return this; }
+
void
_M_check_rehashed(size_type __prev_count)
{
@@ -770,31 +775,18 @@ namespace __debug
this->_M_invalidate_all();
}
- void
- _M_invalidate(_Base_const_iterator __victim)
- {
- this->_M_invalidate_if(
- [__victim](_Base_const_iterator __it) { return __it == __victim; });
- this->_M_invalidate_local_if(
- [__victim](_Base_const_local_iterator __it)
- { return __it == __victim; });
- }
-
_Base_iterator
_M_erase(_Base_const_iterator __victim)
{
- _M_invalidate(__victim);
- size_type __bucket_count = this->bucket_count();
- _Base_iterator __next = _Base::erase(__victim);
- _M_check_rehashed(__bucket_count);
- return __next;
+ this->_M_invalidate(__victim);
+ return _Base::erase(__victim);
}
#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
node_type
_M_extract(_Base_const_iterator __victim)
{
- _M_invalidate(__victim);
+ this->_M_invalidate(__victim);
return _Base::extract(__victim);
}
#endif
@@ -1497,16 +1489,15 @@ namespace __debug
erase(const key_type& __key)
{
size_type __ret(0);
- size_type __bucket_count = this->bucket_count();
auto __pair = _Base::equal_range(__key);
+ __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
for (auto __victim = __pair.first; __victim != __pair.second;)
{
- _M_invalidate(__victim);
+ this->_M_invalidate_single(__victim);
__victim = _Base::erase(__victim);
++__ret;
}
- _M_check_rehashed(__bucket_count);
return __ret;
}
@@ -1535,18 +1526,19 @@ namespace __debug
erase(const_iterator __first, const_iterator __last)
{
__glibcxx_check_erase_range(__first, __last);
+ {
+ __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
{
_GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
_M_message(__gnu_debug::__msg_valid_range)
._M_iterator(__first, "first")
._M_iterator(__last, "last"));
- _M_invalidate(__tmp);
+ this->_M_invalidate_single(__tmp);
+ }
}
- size_type __bucket_count = this->bucket_count();
auto __next = _Base::erase(__first.base(), __last.base());
- _M_check_rehashed(__bucket_count);
return { __next, this };
}
@@ -1560,6 +1552,10 @@ namespace __debug
_M_base() const noexcept { return *this; }
private:
+ const unordered_multimap*
+ _M_self() const noexcept
+ { return this; }
+
void
_M_check_rehashed(size_type __prev_count)
{
@@ -1567,31 +1563,18 @@ namespace __debug
this->_M_invalidate_all();
}
- void
- _M_invalidate(_Base_const_iterator __victim)
- {
- this->_M_invalidate_if(
- [__victim](_Base_const_iterator __it) { return __it == __victim; });
- this->_M_invalidate_local_if(
- [__victim](_Base_const_local_iterator __it)
- { return __it == __victim; });
- }
-
_Base_iterator
_M_erase(_Base_const_iterator __victim)
{
- _M_invalidate(__victim);
- size_type __bucket_count = this->bucket_count();
- _Base_iterator __next = _Base::erase(__victim);
- _M_check_rehashed(__bucket_count);
- return __next;
+ this->_M_invalidate(__victim);
+ return _Base::erase(__victim);
}
#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
node_type
_M_extract(_Base_const_iterator __victim)
{
- _M_invalidate(__victim);
+ this->_M_invalidate(__victim);
return _Base::extract(__victim);
}
#endif
diff --git a/libstdc++-v3/include/debug/unordered_set
b/libstdc++-v3/include/debug/unordered_set
index de999a76890..cc55d15f7be 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -623,18 +623,19 @@ namespace __debug
erase(const_iterator __first, const_iterator __last)
{
__glibcxx_check_erase_range(__first, __last);
+ {
+ __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
{
_GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
_M_message(__gnu_debug::__msg_valid_range)
._M_iterator(__first, "first")
._M_iterator(__last, "last"));
- _M_invalidate(__tmp);
+ this->_M_invalidate_single(__tmp);
+ }
}
- size_type __bucket_count = this->bucket_count();
auto __next = _Base::erase(__first.base(), __last.base());
- _M_check_rehashed(__bucket_count);
return { __next, this };
}
@@ -645,6 +646,10 @@ namespace __debug
_M_base() const noexcept { return *this; }
private:
+ const unordered_set*
+ _M_self() const noexcept
+ { return this; }
+
void
_M_check_rehashed(size_type __prev_count)
{
@@ -652,31 +657,18 @@ namespace __debug
this->_M_invalidate_all();
}
- void
- _M_invalidate(_Base_const_iterator __victim)
- {
- this->_M_invalidate_if(
- [__victim](_Base_const_iterator __it) { return __it == __victim; });
- this->_M_invalidate_local_if(
- [__victim](_Base_const_local_iterator __it)
- { return __it == __victim; });
- }
-
_Base_iterator
_M_erase(_Base_const_iterator __victim)
{
- _M_invalidate(__victim);
- size_type __bucket_count = this->bucket_count();
- _Base_iterator __next = _Base::erase(__victim);
- _M_check_rehashed(__bucket_count);
- return __next;
+ this->_M_invalidate(__victim);
+ return _Base::erase(__victim);
}
#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
node_type
_M_extract(_Base_const_iterator __victim)
{
- _M_invalidate(__victim);
+ this->_M_invalidate(__victim);
return _Base::extract(__victim);
}
#endif
@@ -1320,9 +1312,10 @@ namespace __debug
{
size_type __ret(0);
auto __pair = _Base::equal_range(__key);
+ __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
for (auto __victim = __pair.first; __victim != __pair.second;)
{
- _M_invalidate(__victim);
+ this->_M_invalidate_single(__victim);
__victim = _Base::erase(__victim);
++__ret;
}
@@ -1355,14 +1348,18 @@ namespace __debug
erase(const_iterator __first, const_iterator __last)
{
__glibcxx_check_erase_range(__first, __last);
+ {
+ __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
{
_GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
_M_message(__gnu_debug::__msg_valid_range)
._M_iterator(__first, "first")
._M_iterator(__last, "last"));
- _M_invalidate(__tmp);
+ this->_M_invalidate_single(__tmp);
+ }
}
+
return { _Base::erase(__first.base(), __last.base()), this };
}
@@ -1373,6 +1370,10 @@ namespace __debug
_M_base() const noexcept { return *this; }
private:
+ const unordered_multiset*
+ _M_self() const noexcept
+ { return this; }
+
void
_M_check_rehashed(size_type __prev_count)
{
@@ -1380,31 +1381,18 @@ namespace __debug
this->_M_invalidate_all();
}
- void
- _M_invalidate(_Base_const_iterator __victim)
- {
- this->_M_invalidate_if(
- [__victim](_Base_const_iterator __it) { return __it == __victim; });
- this->_M_invalidate_local_if(
- [__victim](_Base_const_local_iterator __it)
- { return __it == __victim; });
- }
-
_Base_iterator
_M_erase(_Base_const_iterator __victim)
{
- _M_invalidate(__victim);
- size_type __bucket_count = this->bucket_count();
- _Base_iterator __next = _Base::erase(__victim);
- _M_check_rehashed(__bucket_count);
- return __next;
+ this->_M_invalidate(__victim);
+ return _Base::erase(__victim);
}
#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
node_type
_M_extract(_Base_const_iterator __victim)
{
- _M_invalidate(__victim);
+ this->_M_invalidate(__victim);
return _Base::extract(__victim);
}
#endif
