This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Improve safe iterator move semantic
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Thu, 9 Aug 2018 20:41:43 +0200
- Subject: Improve safe iterator move semantic
Here is a patch to improve Debug mode safe iterator move semantic.
To summarize where we used to have N mutex locks we now have N - 1.
For instance move constructor used to lock mutex twice, now it only does
it once. Note that move constructor or move assignment operator are
currently more expensive than their copy counterparts !
I did my best to avoid new symbols but I still require 1 to be
added: _Safe_local_iterator::_M_attach_single. We will now make use of
the already exported _Safe_iterator::_M_attach_single symbol.
Tested under Linux x86_64, Debug mode.
Ok to commit ?
François
diff --git a/libstdc++-v3/config/abi/pre/gnu.ver b/libstdc++-v3/config/abi/pre/gnu.ver
index 593783d..1143d9a 100644
--- a/libstdc++-v3/config/abi/pre/gnu.ver
+++ b/libstdc++-v3/config/abi/pre/gnu.ver
@@ -2046,6 +2046,7 @@ GLIBCXX_3.4.26 {
_ZNSt3pmr25monotonic_buffer_resource13_M_new_bufferE[jmy][jmy];
_ZNSt3pmr25monotonic_buffer_resource18_M_release_buffersEv;
+ _ZN11__gnu_debug25_Safe_local_iterator_base16_M_detach_singleEv;
} GLIBCXX_3.4.25;
# Symbols in the support library (libsupc++) have their own tag.
diff --git a/libstdc++-v3/include/debug/safe_base.h b/libstdc++-v3/include/debug/safe_base.h
index f58a78f..c276a18 100644
--- a/libstdc++-v3/include/debug/safe_base.h
+++ b/libstdc++-v3/include/debug/safe_base.h
@@ -97,6 +97,13 @@ namespace __gnu_debug
: _M_sequence(0), _M_version(0), _M_prior(0), _M_next(0)
{ this->_M_attach(__x._M_sequence, __constant); }
+#if __cplusplus >= 201103L
+ _Safe_iterator_base(_Safe_iterator_base&&) = default;
+
+ _Safe_iterator_base&
+ operator=(_Safe_iterator_base&&) = default;
+#endif
+
~_Safe_iterator_base() { this->_M_detach(); }
/** For use in _Safe_iterator. */
@@ -121,6 +128,12 @@ namespace __gnu_debug
void
_M_detach();
+#if __cplusplus >= 201103L
+ /** Attaches this iterator at __x place. */
+ void
+ _M_move_to(_Safe_iterator_base* __x, bool __constant);
+#endif
+
public:
/** Likewise, but not thread-safe. */
void
@@ -148,11 +161,12 @@ namespace __gnu_debug
/** Reset all member variables */
void
- _M_reset() throw ();
+ _M_reset() _GLIBCXX_USE_NOEXCEPT
+ { __builtin_memset(this, 0, sizeof(_Safe_iterator_base)); }
/** Unlink itself */
void
- _M_unlink() throw ()
+ _M_unlink() _GLIBCXX_USE_NOEXCEPT
{
if (_M_prior)
_M_prior->_M_next = _M_next;
@@ -273,6 +287,28 @@ namespace __gnu_debug
void
_M_detach_single(_Safe_iterator_base* __it) throw ();
};
+
+#if __cplusplus >= 201103L
+ inline void
+ _Safe_iterator_base::_M_move_to(_Safe_iterator_base* __x, bool __constant)
+ {
+ __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+ if (_M_prior)
+ _M_prior->_M_next = this;
+ else
+ {
+ // No prior, we are at the beginning of the linked list.
+ auto& __its = __constant
+ ? _M_sequence->_M_const_iterators : _M_sequence->_M_iterators;
+ if (__its == __x)
+ __its = this;
+ }
+
+ if (_M_next)
+ _M_next->_M_prior = this;
+ }
+#endif
+
} // namespace __gnu_debug
#endif
diff --git a/libstdc++-v3/include/debug/safe_iterator.h b/libstdc++-v3/include/debug/safe_iterator.h
index b8256fc..4b5773f 100644
--- a/libstdc++-v3/include/debug/safe_iterator.h
+++ b/libstdc++-v3/include/debug/safe_iterator.h
@@ -151,17 +151,20 @@ namespace __gnu_debug
* @post __x is singular and unattached
*/
_Safe_iterator(_Safe_iterator&& __x) noexcept
- : _Iter_base()
+ : _Iter_base(__x), _Safe_base(std::move(__x))
{
_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
|| __x.base() == _Iterator(),
_M_message(__msg_init_copy_singular)
._M_iterator(*this, "this")
._M_iterator(__x, "other"));
- _Safe_sequence_base* __seq = __x._M_sequence;
- __x._M_detach();
- std::swap(base(), __x.base());
- _M_attach(__seq);
+ if (__x._M_sequence)
+ {
+ _M_move_to(&__x, _S_constant());
+
+ __x._M_reset();
+ __x.base() = _Iter_base();
+ }
}
#endif
@@ -238,16 +241,22 @@ namespace __gnu_debug
{
__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
base() = __x.base();
- _M_version = __x._M_sequence->_M_version;
+ _M_version = __x._M_version;
+ __x._M_detach_single();
}
else
{
_M_detach();
base() = __x.base();
- _M_attach(__x._M_sequence);
+
+ if (__x._M_sequence)
+ {
+ _Safe_base::operator=(std::move(__x));
+ _M_move_to(&__x, _S_constant());
+ __x._M_reset();
+ }
}
- __x._M_detach();
__x.base() = _Iterator();
return *this;
}
diff --git a/libstdc++-v3/include/debug/safe_local_iterator.h b/libstdc++-v3/include/debug/safe_local_iterator.h
index f9597a6..2dd9a19 100644
--- a/libstdc++-v3/include/debug/safe_local_iterator.h
+++ b/libstdc++-v3/include/debug/safe_local_iterator.h
@@ -112,17 +112,20 @@ namespace __gnu_debug
* @post __x is singular and unattached
*/
_Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
- : _Iter_base()
+ : _Iter_base(__x), _Safe_base(std::move(__x))
{
_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
|| __x.base() == _Iterator(),
_M_message(__msg_init_copy_singular)
._M_iterator(*this, "this")
._M_iterator(__x, "other"));
- auto __cont = __x._M_sequence;
- __x._M_detach();
- std::swap(base(), __x.base());
- _M_attach(__cont);
+ if (__x._M_sequence)
+ {
+ _M_move_to(&__x, _S_constant());
+
+ __x._M_reset();
+ __x.base() = _Iter_base();
+ }
}
/**
@@ -198,16 +201,22 @@ namespace __gnu_debug
{
__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
base() = __x.base();
- _M_version = __x._M_sequence->_M_version;
+ _M_version = __x._M_version;
+ __x._M_detach_single();
}
else
{
_M_detach();
base() = __x.base();
- _M_attach(__x._M_sequence);
+
+ if (__x._M_sequence)
+ {
+ _Safe_base::operator=(std::move(__x));
+ _M_move_to(&__x, _S_constant());
+ __x._M_reset();
+ }
}
- __x._M_detach();
__x.base() = _Iterator();
return *this;
}
diff --git a/libstdc++-v3/include/debug/safe_unordered_base.h b/libstdc++-v3/include/debug/safe_unordered_base.h
index 5dd0e0e..340aea6 100644
--- a/libstdc++-v3/include/debug/safe_unordered_base.h
+++ b/libstdc++-v3/include/debug/safe_unordered_base.h
@@ -51,8 +51,9 @@ namespace __gnu_debug
{
protected:
/** Initializes the iterator and makes it singular. */
- _Safe_local_iterator_base()
- { }
+ _Safe_local_iterator_base() = default;
+
+ _Safe_local_iterator_base(_Safe_local_iterator_base&&) = default;
/** Initialize the iterator to reference the container pointed to
* by @p __seq. @p __constant is true when we are initializing a
@@ -62,17 +63,20 @@ namespace __gnu_debug
* be nonsingular.
*/
_Safe_local_iterator_base(const _Safe_sequence_base* __seq, bool __constant)
- { this->_M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); }
+ { _M_attach(const_cast<_Safe_sequence_base*>(__seq), __constant); }
/** Initializes the iterator to reference the same container that
@p __x does. @p __constant is true if this is a constant
iterator, and false if it is mutable. */
_Safe_local_iterator_base(const _Safe_local_iterator_base& __x,
bool __constant)
- { this->_M_attach(__x._M_sequence, __constant); }
+ { _M_attach(__x._M_sequence, __constant); }
~_Safe_local_iterator_base() { this->_M_detach(); }
+ _Safe_local_iterator_base&
+ operator=(_Safe_local_iterator_base&&) = default;
+
_Safe_unordered_container_base*
_M_get_container() const noexcept;
@@ -97,6 +101,10 @@ namespace __gnu_debug
/** Likewise, but not thread-safe. */
void
_M_detach_single() throw ();
+
+ /** Attaches this iterator at __x place. */
+ void
+ _M_move_to(_Safe_iterator_base* __x, bool __constant);
};
/**
@@ -180,6 +188,31 @@ namespace __gnu_debug
void
_M_detach_local_single(_Safe_iterator_base* __it) throw ();
};
+
+ inline _Safe_unordered_container_base*
+ _Safe_local_iterator_base::_M_get_container() const noexcept
+ { return static_cast<_Safe_unordered_container_base*>(_M_sequence); }
+
+ inline void
+ _Safe_local_iterator_base::_M_move_to(_Safe_iterator_base* __x,
+ bool __constant)
+ {
+ __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
+ if (_M_prior)
+ _M_prior->_M_next = this;
+ else
+ {
+ // No prior, we are at the beginning of the linked list.
+ auto& __its = __constant
+ ? _M_get_container()->_M_const_local_iterators
+ : _M_get_container()->_M_local_iterators;
+ if (__its == __x)
+ __its = this;
+ }
+
+ if (_M_next)
+ _M_next->_M_prior = this;
+ }
} // namespace __gnu_debug
#endif
diff --git a/libstdc++-v3/src/c++11/debug.cc b/libstdc++-v3/src/c++11/debug.cc
index 3cae3db..8edbfc0 100644
--- a/libstdc++-v3/src/c++11/debug.cc
+++ b/libstdc++-v3/src/c++11/debug.cc
@@ -401,16 +401,6 @@ namespace __gnu_debug
}
}
- void
- _Safe_iterator_base::
- _M_reset() throw ()
- {
- _M_sequence = 0;
- _M_version = 0;
- _M_prior = 0;
- _M_next = 0;
- }
-
bool
_Safe_iterator_base::
_M_singular() const throw ()
@@ -429,11 +419,6 @@ namespace __gnu_debug
_M_get_mutex() throw ()
{ return _M_sequence->_M_get_mutex(); }
- _Safe_unordered_container_base*
- _Safe_local_iterator_base::
- _M_get_container() const noexcept
- { return static_cast<_Safe_unordered_container_base*>(_M_sequence); }
-
void
_Safe_local_iterator_base::
_M_attach(_Safe_sequence_base* __cont, bool __constant)