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
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index cef94f7..aaff500 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -364,19 +364,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
rebind<_List_node<_Tp> >::other _Node_alloc_type;
typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
- static size_t
- _S_distance(const __detail::_List_node_base* __first,
- const __detail::_List_node_base* __last)
- {
- size_t __n = 0;
- while (__first != __last)
- {
- __first = __first->_M_next;
- ++__n;
- }
- return __n;
- }
-
struct _List_impl
: public _Node_alloc_type
{
@@ -393,6 +380,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
#if __cplusplus >= 201103L
_List_impl(_List_impl&&) = default;
+ _List_impl(_List_impl&& __x, _Node_alloc_type&& __a)
+ : _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))
{ }
@@ -409,28 +400,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
void _M_inc_size(size_t __n) { _M_impl._M_node._M_size += __n; }
void _M_dec_size(size_t __n) { _M_impl._M_node._M_size -= __n; }
-
- size_t
- _M_distance(const __detail::_List_node_base* __first,
- const __detail::_List_node_base* __last) const
- { return _S_distance(__first, __last); }
-
- // return the stored size
- size_t _M_node_count() const { return _M_get_size(); }
#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) { }
- size_t _M_distance(const void*, const void*) const { return 0; }
-
- // count the number of nodes
- size_t _M_node_count() const
- {
- return _S_distance(_M_impl._M_node._M_next,
- std::__addressof(_M_impl._M_node));
- }
#endif
typename _Node_alloc_traits::pointer
@@ -466,12 +441,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
_List_base(_List_base&&) = default;
_List_base(_List_base&& __x, _Node_alloc_type&& __a)
+ : _M_impl(std::move(__x), 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.
- }
+ { }
void
_M_move_nodes(_List_base&& __x)
@@ -616,6 +591,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
}
#endif
+#if _GLIBCXX_USE_CXX11_ABI
+ size_t
+ _M_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
+ size_t _M_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 +712,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())
+ private:
+ list(list&& __x, const allocator_type& __a, true_type) noexcept
: _Base(std::move(__x), _Node_alloc_type(__a))
+ { }
+
+ 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.
- insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()),
- std::__make_move_if_noexcept_iterator(__x.end()));
+ 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 +1006,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 +1584,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 = _M_distance(__first, __last);
this->_M_inc_size(__n);
__x._M_dec_size(__n);
