https://gcc.gnu.org/g:6ff4e7181c5f1748bc9aecc292369893a0fa790b
commit r16-7850-g6ff4e7181c5f1748bc9aecc292369893a0fa790b Author: François Dumont <[email protected]> Date: Tue Feb 17 16:11:49 2026 +0100 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 for invalidation purpose. 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 (_Safe_unordered_container::_M_invalidate_locals): Remove. (_Safe_unordered_container::_M_invalidate_all): Lock mutex while calling _M_invalidate_if and _M_invalidate_locals. (_Safe_unordered_container::_M_invalidate_all_if): New. (_Safe_unordered_container::_M_invalidate): New. (_Safe_unordered_container::_M_invalidate_if): Make private, add __scoped_lock argument. (_Safe_unordered_container::_M_invalidate_local_if): Likewise. * include/debug/safe_unordered_container.tcc (_Safe_unordered_container::_M_invalidate_if): Adapt and remove lock. (_Safe_unordered_container::_M_invalidate_local_if): Likewise. * include/debug/unordered_map (unordered_map::erase(const_iterator, const_iterator)): Lock before loop on iterators. Remove _M_check_rehashed call. (unordered_map::_M_self): New. (unordered_map::_M_invalidate): Remove. (unordered_map::_M_erase): Adapt and remove _M_check_rehashed call. (unordered_multimap::_M_erase(_Base_iterator, _Base_iterator)): New. (unordered_multimap::erase(_Kt&&)): Use latter. (unordered_multimap::erase(const key_type&)): Likewise. (unordered_multimap::erase(const_iterator, const_iterator)): Lock before loop on iterators. Remove _M_check_rehashed. (unordered_multimap::_M_self): New. (unordered_multimap::_M_invalidate): Remove. (unordered_multimap::_M_erase): Adapt. Remove _M_check_rehashed call. * include/debug/unordered_set (unordered_set::erase(const_iterator, const_iterator)): Add lock before loop for iterator invalidation. Remove _M_check_rehashed call. (unordered_set::_M_self): New. (unordered_set::_M_invalidate): Remove. (unordered_set::_M_erase): Adapt and remove _M_check_rehashed call. (unordered_multiset::_M_erase(_Base_iterator, _Base_iterator)): New. (unordered_multiset::erase(_Kt&&)): Use latter. (unordered_multiset::erase(const key_type&)): Likewise. (unordered_multiset::erase(const_iterator, const_iterator)): Lock before loop on iterators. Remove _M_check_rehashed. (unordered_multiset::_M_self): New. (unordered_multiset::_M_invalidate): Remove. (unordered_multiset::_M_erase): Adapt. Remove _M_check_rehashed call. Reviewed-by: Jonathan Wakely <[email protected]> Diff: --- .../include/debug/safe_unordered_container.h | 72 ++++++++---- .../include/debug/safe_unordered_container.tcc | 6 +- libstdc++-v3/include/debug/unordered_map | 126 +++++++++------------ libstdc++-v3/include/debug/unordered_set | 120 +++++++++----------- 4 files changed, 164 insertions(+), 160 deletions(-) diff --git a/libstdc++-v3/include/debug/safe_unordered_container.h b/libstdc++-v3/include/debug/safe_unordered_container.h index e76d60d2605b..3f8346acb3bd 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,8 @@ 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( - [__local_end](__decltype(__local_end) __it) - { return __it != __local_end; }); - } - #if __cplusplus > 201402L + protected: template<typename _ExtractKey, typename _Source> struct _UContInvalidatePred { @@ -130,10 +120,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,19 +156,63 @@ 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) - { return __it != __end; }); - _M_invalidate_locals(); + _M_invalidate_if( + [__end](decltype(__end) __it) + { return __it != __end; }, + sentry); + + auto __local_end = _M_cont()._M_base().cend(0); + _M_invalidate_local_if( + [__local_end](decltype(__local_end) __it) + { return __it != __local_end; }, + sentry); } + template<typename _Predicate> + void + _M_invalidate_all_if(_Predicate __pred) + { + __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex()); + _M_invalidate_if(__pred, sentry); + _M_invalidate_local_if(__pred, sentry); + } + + protected: + template<typename _VictimIt> + void + _M_invalidate(_VictimIt __victim) + { + __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex()); + _M_invalidate(__victim, sentry); + } + + template<typename _VictimIt> + void + _M_invalidate(_VictimIt __victim, const __gnu_cxx::__scoped_lock& __lock) + { + auto __end = _M_cont()._M_base().cend(); + _M_invalidate_if( + [__victim](decltype(__end) __it) + { return __it == __victim; }, + __lock); + + auto __local_end = _M_cont()._M_base().cend(0); + _M_invalidate_local_if( + [__victim](decltype(__local_end) __it) + { return __it == __victim; }, + __lock); + } + + 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 in the safe ones. */ template<typename _Predicate> void - _M_invalidate_if(_Predicate __pred); + _M_invalidate_if(_Predicate __pred, const __gnu_cxx::__scoped_lock&); /** Invalidates all local iterators @c x that reference this container, are not singular, and for which @c __pred(x) returns @c @@ -189,7 +220,8 @@ namespace __gnu_debug nested in the safe ones. */ template<typename _Predicate> void - _M_invalidate_local_if(_Predicate __pred); + _M_invalidate_local_if(_Predicate __pred, + const __gnu_cxx::__scoped_lock&); }; } // namespace __gnu_debug diff --git a/libstdc++-v3/include/debug/safe_unordered_container.tcc b/libstdc++-v3/include/debug/safe_unordered_container.tcc index f60761534c83..75860d6d0551 100644 --- a/libstdc++-v3/include/debug/safe_unordered_container.tcc +++ b/libstdc++-v3/include/debug/safe_unordered_container.tcc @@ -35,12 +35,11 @@ namespace __gnu_debug template<typename _Predicate> void _Safe_unordered_container<_Container>:: - _M_invalidate_if(_Predicate __pred) + _M_invalidate_if(_Predicate __pred, const __gnu_cxx::__scoped_lock&) { 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); @@ -67,12 +66,11 @@ namespace __gnu_debug template<typename _Predicate> void _Safe_unordered_container<_Container>:: - _M_invalidate_local_if(_Predicate __pred) + _M_invalidate_local_if(_Predicate __pred, const __gnu_cxx::__scoped_lock&) { 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 1ea480a4e8ba..75c55cca141c 100644 --- a/libstdc++-v3/include/debug/unordered_map +++ b/libstdc++-v3/include/debug/unordered_map @@ -762,18 +762,19 @@ namespace __debug erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); - 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); - } + { + __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")); + this->_M_invalidate(__tmp, sentry); + } + } - size_type __bucket_count = this->bucket_count(); auto __next = _Base::erase(__first.base(), __last.base()); - _M_check_rehashed(__bucket_count); return { __next, this }; } @@ -787,6 +788,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) { @@ -794,31 +799,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 @@ -1532,18 +1524,8 @@ namespace __debug size_type erase(const key_type& __key) { - size_type __ret(0); - size_type __bucket_count = this->bucket_count(); - auto __pair = _Base::equal_range(__key); - for (auto __victim = __pair.first; __victim != __pair.second;) - { - _M_invalidate(__victim); - __victim = _Base::erase(__victim); - ++__ret; - } - - _M_check_rehashed(__bucket_count); - return __ret; + auto __victims = _Base::equal_range(__key); + return _M_erase(__victims.first, __victims.second); } # ifdef __glibcxx_associative_heterogeneous_erasure @@ -1551,15 +1533,8 @@ namespace __debug size_type erase(_Kt&& __key) { - size_type __count(0); auto __victims = _Base::equal_range(__key); - for (auto __victim = __victims.first; __victim != __victims.second;) - { - _M_invalidate(__victim); - __victim = _Base::erase(__victim); - ++__count; - } - return __count; + return _M_erase(__victims.first, __victims.second); } #endif @@ -1588,18 +1563,19 @@ namespace __debug erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); - 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); - } + { + __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")); + this->_M_invalidate(__tmp, sentry); + } + } - size_type __bucket_count = this->bucket_count(); auto __next = _Base::erase(__first.base(), __last.base()); - _M_check_rehashed(__bucket_count); return { __next, this }; } @@ -1613,6 +1589,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) { @@ -1620,31 +1600,35 @@ namespace __debug this->_M_invalidate_all(); } - void - _M_invalidate(_Base_const_iterator __victim) + _Base_iterator + _M_erase(_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; }); + this->_M_invalidate(__victim); + return _Base::erase(__victim); } - _Base_iterator - _M_erase(_Base_const_iterator __victim) + size_type + _M_erase(_Base_iterator __first, _Base_iterator __last) { - _M_invalidate(__victim); - size_type __bucket_count = this->bucket_count(); - _Base_iterator __next = _Base::erase(__victim); - _M_check_rehashed(__bucket_count); - return __next; + size_type __ret(0); + { + __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex()); + for (auto __victim = __first; __victim != __last; ++__victim) + { + this->_M_invalidate(__victim, sentry); + ++__ret; + } + } + + _Base::erase(__first, __last); + return __ret; } #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 e26b52d70299..e0795f5bbc71 100644 --- a/libstdc++-v3/include/debug/unordered_set +++ b/libstdc++-v3/include/debug/unordered_set @@ -647,18 +647,19 @@ namespace __debug erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); - 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); - } + { + __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")); + this->_M_invalidate(__tmp, sentry); + } + } - size_type __bucket_count = this->bucket_count(); auto __next = _Base::erase(__first.base(), __last.base()); - _M_check_rehashed(__bucket_count); return { __next, this }; } @@ -669,6 +670,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) { @@ -676,31 +681,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 @@ -1353,15 +1345,8 @@ namespace __debug size_type erase(const key_type& __key) { - size_type __count(0); auto __victims = _Base::equal_range(__key); - for (auto __victim = __victims.first; __victim != __victims.second;) - { - _M_invalidate(__victim); - __victim = _Base::erase(__victim); - ++__count; - } - return __count; + return _M_erase(__victims.first, __victims.second); } # ifdef __glibcxx_associative_heterogeneous_erasure @@ -1369,15 +1354,8 @@ namespace __debug size_type erase(_Kt&& __key) { - size_type __count(0); auto __victims = _Base::equal_range(__key); - for (auto __victim = __victims.first; __victim != __victims.second;) - { - _M_invalidate(__victim); - __victim = _Base::erase(__victim); - ++__count; - } - return __count; + return _M_erase(__victims.first, __victims.second); } #endif @@ -1406,14 +1384,18 @@ namespace __debug erase(const_iterator __first, const_iterator __last) { __glibcxx_check_erase_range(__first, __last); - 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); - } + { + __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")); + this->_M_invalidate(__tmp, sentry); + } + } + return { _Base::erase(__first.base(), __last.base()), this }; } @@ -1424,6 +1406,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) { @@ -1431,31 +1417,35 @@ namespace __debug this->_M_invalidate_all(); } - void - _M_invalidate(_Base_const_iterator __victim) + _Base_iterator + _M_erase(_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; }); + this->_M_invalidate(__victim); + return _Base::erase(__victim); } - _Base_iterator - _M_erase(_Base_const_iterator __victim) + size_type + _M_erase(_Base_iterator __first, _Base_iterator __last) { - _M_invalidate(__victim); - size_type __bucket_count = this->bucket_count(); - _Base_iterator __next = _Base::erase(__victim); - _M_check_rehashed(__bucket_count); - return __next; + size_type __count(0); + { + __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex()); + for (auto __victim = __first; __victim != __last; ++__victim) + { + this->_M_invalidate(__victim, sentry); + ++__count; + } + } + + _Base::erase(__first, __last); + return __count; } #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
