std::list optimizations

[François Dumont <frs dot dumont at gmail dot com>]

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);