On Sat, 21 Feb 2026 at 17:40 +0100, François Dumont wrote:
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
You can omit the "__gnu_debug::" here since everything in the file is
in that namespace anyway, so it's implied. Just referring to
_Safe_unordered_container is unambiguous.
It's a primary template not a specialization, so the "<>" doesn't add
any value.
And you can omit the "()" at the end, since that's also implied.
So just "_Safe_unordered_container::_M_invalidate_all"
while calling _M_invalidate_if and _M_invalidate_locals.
(_Safe_unordered_container<>::_M_invalidate_all_if<_Pred>()): New.
This is not the signature of the function, it takes a parameter, so
showing it as "()" is wrong, and the "<>" is unnecessary.
So just "_Safe_unordered_container::_M_invalidate_all_if"
(_Safe_unordered_container<>::_M_invalidate_all_single_if<_Pred>()): New.
Same here.
(_Safe_unordered_container<>::struct _InvalidatePred<>): New.
The "<>" and "struct " parts are not adding any value. You can say
"New class template" if you want to make it clear it's a template.
(_Safe_unordered_container<>::_M_invalidate<_It>(_It)): New.
_Safe_unordered_container::_M_invalidate
(_Safe_unordered_container<>::_M_invalidate_single<_It>(_It)): New.
_Safe_unordered_container::_M_invalidate_single
* 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)):
Same here.
Remove lock.
* include/debug/unordered_map
(unordered_map<>::erase(const_iterator, const_iterator)):
Here the "(const_iterator, const_iterator)" does add value, because
it's an overloaded function. But "<>" doesn't add value.
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)
Does this need to be a function template? Could its parameter just be
_Base_const_iterator instead?
And then _InvalidatePred::_M_victim could be the same type, and that
doesn't need to be a class template.
+ {
+ _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());
I find the changes in this file make the code more confusing. You've
added new member functions with "single" in the name to do the work without
locking the mutex, but then you've changed _M_invalidate_if and
_M_invalidate_local_if to not lock the mutex. But they don't have
"single" in the name. Without checking the code carefully, I would
assume that _M_invalidate_if acquires the lock, because that's what
the naming convention in safe_unordered_container.h seems to imply.
I think adding the new "single" functions is what causes this
confusion, because the names are not used consistently for all
non-locking functions. The names can also be misread so that
"invalidate single" looks like it invalidates a single iterator. We
have "invalidate all" to invalidate all iterators, and "invalidate
single" to invalidate a single iterator, right?! ... no, that's wrong.
And we also have "invalidate all single"!
I know we already use "_single" as a suffix in _Safe_base but I think
here it is confusing.
And one of those new "single" functions doesn't seem necessary at all:
_M_invalidate_all_single_if is just two lines, and is only used in two
places. You could just write those two lines inline where it's called.
That gets rid of _M_invalidate_all_single_if.
_M_invalidate_all_if is also only used in two places, so that can be
inlined into its callers too.
So now there are only two new member functions, _M_invalidate(victim)
and _M_invalidate_single(victim), one which acquires a lock and one
which assuems the caller has already acquired a lock. They could be
written like this:
void
_M_invalidate(_Base_const_iterator __victim)
{
__gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
_M_invalidate(__victim, sentry);
}
// Caller must hold lock
void
_M_invalidate(_Base_const_iterator __victim,
const __gnu_cxx::__scoped_lock&)
{
auto __pred = [__victim](_Base_const_iterator __it) {
return __it == __victim;
};
_M_invalidate_if(__pred);
_M_invalidate_local_if(__pred);
}
And then callers that have already taken the lock call the second
overload.
This also removes the need for _InvalidatePred.
So this avoids adding several new member functions and a new class
template, and avoids the naming inconsistency for when "single" is
used or not.
For the two function which no longer acquire the lock
(_M_invalidate_if and _M_invalidate_local_if) please add a similar
"Caller must hold lock" comment to their declarations in the header.
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
