On 18/08/2017 22:04, Jonathan Wakely wrote:
On 28/07/17 18:42 +0200, François Dumont wrote:
Hi
Completing execution of the testsuite revealed a bug. So here is
the correct version of this patch.
François
On 21/07/2017 19:14, François Dumont wrote:
Hi
Here is a proposal for 2 optimizations in the std::list
implementation.
Optimization on the move constructor taking an allocator for
always equal allocators. Compare to the version in my previous
std::list patch I am now doing it at std::list level rather than at
_List_base level. This way we won't instantiate the insert call and
we won't check for empty list when the allocator always compare equal.
2nd optimization, I replace the _S_distance method by the
std::distance algo which benefit from the nice [begin(), end())
range optimization when cxx11 abi is being used.
Note that I am proposing the 2 change in 1 patch to save some
review time but I can commit those separately.
Tested under x86_64 Linux normal mode.
* include/bits/stl_list.h
(_List_base<>::_S_distance): Remove.
(_List_impl(_List_impl&&, _Node_alloc_type&&)): New.
(_List_base(_List_base&&, _Node_alloc_type&&)): Use latter.
(_List_base(_Node_alloc_type&&)): New.
(_List_base<>::_M_distance, _List_base<>::_M_node_count): Move...
(list<>::_M_distance, list<>::_M_node_count): ...here. Replace
calls to
_S_distance with calls to std::distance.
(list(list&&, const allocator_type&, true_type)): New.
(list(list&&, const allocator_type&, false_type)): New.
(list(list&&, const allocator_type&)): Adapt to call latters.
Ok to commit ?
François
_List_base(_List_base&&) = default;
_List_base(_List_base&& __x, _Node_alloc_type&& __a)
+ : _M_impl(std::move(__x._M_impl), std::move(__a))
+ { }
+
+ _List_base(_Node_alloc_type&& __a)
: _M_impl(std::move(__a))
- {
- if (__x._M_get_Node_allocator() == _M_get_Node_allocator())
- _M_move_nodes(std::move(__x));
- // else caller must move individual elements.
- }
+ { }
I like this change in principle, but it alters the behaviour of an
existing constructor. Existing code might use the constructor and get
broken by this.
You can avoid that by leaving the existing constructor alone and
adding two new ones for new code to use. Reordering the parameters
will make the new one distinct from the old one:
// Used when is_always_equal
_List_base(_Node_alloc_type&& __a, _List_base&& __x))
: _M_impl(std::move(__x._M_impl), std::move(__a))
{ }
I have chosen this approach and also adapt the _List_impl class to have
same signature which moreover correspond to order of members so maybe
not so bad.
_M_distance could be static though, neither version uses the 'this'
pointer, so it would be called _S_distance.
Applied.
Do those suggestions make sense? The idea is to ensure that a given
function signature continues to have the same effects. To introduce
new effects, use a new signature.
Sure, I didn't consider the explicit instantiation use case, makes sens.
So here is a new version. I propose to "mark" code kept for backward abi
compatibility with the _GLIBCXX_INLINE_VERSION. Next time we decide to
break abi we will just need to look for this macro to know what code can
be removed.
Ok to commit if tests are successful ?
François
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index cef94f7..e545996 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -364,6 +364,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
rebind<_List_node<_Tp> >::other _Node_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
+#if !_GLIBCXX_INLINE_VERSION
static size_t
_S_distance(const __detail::_List_node_base* __first,
const __detail::_List_node_base* __last)
@@ -376,6 +377,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
}
return __n;
}
+#endif
struct _List_impl
: public _Node_alloc_type
@@ -393,6 +395,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
#if __cplusplus >= 201103L
_List_impl(_List_impl&&) = default;
+ _List_impl(_Node_alloc_type&& __a, _List_impl&& __x)
+ : _Node_alloc_type(std::move(__a)), _M_node(std::move(__x._M_node))
+ { }
+
_List_impl(_Node_alloc_type&& __a) noexcept
: _Node_alloc_type(std::move(__a))
{ }
@@ -410,6 +416,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; }
+# if !_GLIBCXX_INLINE_VERSION
size_t
_M_distance(const __detail::_List_node_base* __first,
const __detail::_List_node_base* __last) const
@@ -417,12 +424,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
// return the stored size
size_t _M_node_count() const { return _M_get_size(); }
+# endif
#else
// dummy implementations used when the size is not stored
size_t _M_get_size() const { return 0; }
void _M_set_size(size_t) { }
void _M_inc_size(size_t) { }
void _M_dec_size(size_t) { }
+
+# if !_GLIBCXX_INLINE_VERSION
size_t _M_distance(const void*, const void*) const { return 0; }
// count the number of nodes
@@ -432,6 +442,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
std::__addressof(_M_impl._M_node));
}
# endif
+#endif
typename _Node_alloc_traits::pointer
_M_get_node()
@@ -465,6 +476,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
#if __cplusplus >= 201103L
_List_base(_List_base&&) = default;
+# if !_GLIBCXX_INLINE_VERSION
_List_base(_List_base&& __x, _Node_alloc_type&& __a)
: _M_impl(std::move(__a))
{
@@ -472,6 +484,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
_M_move_nodes(std::move(__x));
// else caller must move individual elements.
}
+# endif
+
+ // Used when allocator is_always_equal.
+ _List_base(_Node_alloc_type&& __a, _List_base&& __x)
+ : _M_impl(std::move(__a), std::move(__x._M_impl))
+ { }
+
+ // Used when allocator !is_always_equal.
+ _List_base(_Node_alloc_type&& __a)
+ : _M_impl(std::move(__a))
+ { }
void
_M_move_nodes(_List_base&& __x)
@@ -616,6 +639,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
}
#endif
+#if _GLIBCXX_USE_CXX11_ABI
+ static size_t
+ _S_distance(const_iterator __first, const_iterator __last) const
+ { return std::distance(__first, __last); }
+
+ // return the stored size
+ size_t
+ _M_node_count() const
+ { return this->_M_get_size(); }
+#else
+ // dummy implementations used when the size is not stored
+ static size_t
+ _S_distance(const_iterator, const_iterator) const
+ { return 0; }
+
+ // count the number of nodes
+ size_t
+ _M_node_count() const
+ { return std::distance(begin(), end()); }
+#endif
+
public:
// [23.2.2.1] construct/copy/destroy
// (assign() and get_allocator() are also listed in this section)
@@ -718,15 +762,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
: _Base(_Node_alloc_type(__a))
{ _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); }
- list(list&& __x, const allocator_type& __a)
- noexcept(_Node_alloc_traits::_S_always_equal())
- : _Base(std::move(__x), _Node_alloc_type(__a))
+ private:
+ list(list&& __x, const allocator_type& __a, true_type) noexcept
+ : _Base(_Node_alloc_type(__a), std::move(__x))
+ { }
+
+ list(list&& __x, const allocator_type& __a, false_type)
+ : _Base(_Node_alloc_type(__a))
{
- // If __x is not empty it means its allocator is not equal to __a,
- // so we need to move from each element individually.
+ if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator())
+ this->_M_move_nodes(std::move(__x));
+ else
insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()),
std::__make_move_if_noexcept_iterator(__x.end()));
}
+
+ public:
+ list(list&& __x, const allocator_type& __a)
+ noexcept(_Node_alloc_traits::_S_always_equal())
+ : list(std::move(__x), __a,
+ typename _Node_alloc_traits::is_always_equal{})
+ { }
#endif
/**
@@ -1000,7 +1056,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
/** Returns the number of elements in the %list. */
size_type
size() const _GLIBCXX_NOEXCEPT
- { return this->_M_node_count(); }
+ { return _M_node_count(); }
/** Returns the size() of the largest possible %list. */
size_type
@@ -1578,7 +1634,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
if (this != std::__addressof(__x))
_M_check_equal_allocators(__x);
- size_t __n = this->_M_distance(__first._M_node, __last._M_node);
+ size_t __n = _S_distance(__first, __last);
this->_M_inc_size(__n);
__x._M_dec_size(__n);
