[patch] Optimize std::list when using new ABI

[Jonathan Wakely <jwakely at redhat dot com>]

This fixes some missed optimizations I should have made when adding
the new std::__cxx11::list, making use of the O(1) list::size() when
it saves work.

In the equality comparisons two lists can't be equal if their sizes
differ.

When resizing a list we don't need to walk the list to find whether
we're growing or shrinking, and when shrinking by less than 50% it is
faster to find the first element to erase by moving backwards from the
end rather than starting at the beginning.

Tested powerpc64-linux.

I plan to commit this to trunk and the gcc-5-branch.

commit 9d6539fec972296694c30b073dd068cfbcdae8a5
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Tue May 19 13:28:16 2015 +0100

    	* include/bits/stl_list.h (_M_resize_pos(size_type&)): Declare.
    	(operator==(const list&, const list&)): If size() is O(1) compare
    	sizes before comparing each element.
    	* include/bits/list.tcc (list::_M_resize_pos(size_type&)): Define.
    	(list::resize): Use _M_resize_pos.

diff --git a/libstdc++-v3/include/bits/list.tcc b/libstdc++-v3/include/bits/list.tcc
index a9c8a55..c5d2ab4 100644
--- a/libstdc++-v3/include/bits/list.tcc
+++ b/libstdc++-v3/include/bits/list.tcc
@@ -157,6 +157,52 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       return __ret;
     }
 
+  // Return a const_iterator indicating the position to start inserting or
+  // erasing elements (depending whether the list is growing or shrinking),
+  // and set __new_size to the number of new elements that must be appended.
+  // Equivalent to the following, but performed optimally:
+  // if (__new_size < size()) {
+  //   __new_size = 0;
+  //   return std::next(begin(), __new_size);
+  // } else {
+  //   __newsize -= size();
+  //   return end();
+  // }
+  template<typename _Tp, typename _Alloc>
+    typename list<_Tp, _Alloc>::const_iterator
+    list<_Tp, _Alloc>::
+    _M_resize_pos(size_type& __new_size) const
+    {
+      const_iterator __i;
+#if _GLIBCXX_USE_CXX11_ABI
+      const size_type __len = size();
+      if (__new_size < __len)
+	{
+	  if (__new_size <= __len / 2)
+	    {
+	      __i = begin();
+	      std::advance(__i, __new_size);
+	    }
+	  else
+	    {
+	      __i = end();
+	      ptrdiff_t __num_erase = __len - __new_size;
+	      std::advance(__i, -__num_erase);
+	    }
+	  __new_size = 0;
+	  return __i;
+	}
+      else
+	__i = end();
+#else
+      size_type __len = 0;
+      for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
+        ;
+#endif
+      __new_size -= __len;
+      return __i;
+    }
+
 #if __cplusplus >= 201103L
   template<typename _Tp, typename _Alloc>
     void
@@ -182,14 +228,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     list<_Tp, _Alloc>::
     resize(size_type __new_size)
     {
-      iterator __i = begin();
-      size_type __len = 0;
-      for (; __i != end() && __len < __new_size; ++__i, ++__len)
-        ;
-      if (__len == __new_size)
+      const_iterator __i = _M_resize_pos(__new_size);
+      if (__new_size)
+	_M_default_append(__new_size);
+      else
         erase(__i, end());
-      else                          // __i == end()
-	_M_default_append(__new_size - __len);
     }
 
   template<typename _Tp, typename _Alloc>
@@ -197,14 +240,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     list<_Tp, _Alloc>::
     resize(size_type __new_size, const value_type& __x)
     {
-      iterator __i = begin();
-      size_type __len = 0;
-      for (; __i != end() && __len < __new_size; ++__i, ++__len)
-        ;
-      if (__len == __new_size)
+      const_iterator __i = _M_resize_pos(__new_size);
+      if (__new_size)
+        insert(end(), __new_size, __x);
+      else
         erase(__i, end());
-      else                          // __i == end()
-        insert(end(), __new_size - __len, __x);
     }
 #else
   template<typename _Tp, typename _Alloc>
@@ -212,14 +252,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     list<_Tp, _Alloc>::
     resize(size_type __new_size, value_type __x)
     {
-      iterator __i = begin();
-      size_type __len = 0;
-      for (; __i != end() && __len < __new_size; ++__i, ++__len)
-        ;
-      if (__len == __new_size)
-        erase(__i, end());
-      else                          // __i == end()
-        insert(end(), __new_size - __len, __x);
+      const_iterator __i = _M_resize_pos(__new_size);
+      if (__new_size)
+        insert(end(), __new_size, __x);
+      else
+        erase(__i._M_const_cast(), end());
     }
 #endif
 
diff --git a/libstdc++-v3/include/bits/stl_list.h b/libstdc++-v3/include/bits/stl_list.h
index 3401e5b..a26859e 100644
--- a/libstdc++-v3/include/bits/stl_list.h
+++ b/libstdc++-v3/include/bits/stl_list.h
@@ -1789,6 +1789,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
 	    _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
 	  __builtin_abort();
       }
+
+      // Used to implement resize.
+      const_iterator
+      _M_resize_pos(size_type& __new_size) const;
     };
 _GLIBCXX_END_NAMESPACE_CXX11
 
@@ -1806,6 +1810,11 @@ _GLIBCXX_END_NAMESPACE_CXX11
     inline bool
     operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
     {
+#if _GLIBCXX_USE_CXX11_ABI
+      if (__x.size() != __y.size())
+	return false;
+#endif
+
       typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
       const_iterator __end1 = __x.end();
       const_iterator __end2 = __y.end();