Improve relocation

[Marc Glisse <marc dot glisse at inria dot fr>]

Hello,

here are some tweaks so that I can usefully mark deque as trivially 
relocatable. It includes more noexcept(auto) madness. For __relocate_a_1, 
I should also test if copying, ++ and != are noexcept, but I wanted to ask 
first because there might be restrictions on what iterators are allowed to 
do, even if I didn't see them. Also, the current code already ignores 
those, so it may as well be fixed in another patch.

Allocators are complicated. I specialized only for the default allocator, 
because that's by far the one that is used the most, and I have much less 
risk of getting it wrong. Some allocator expert is welcome to make a 
better test. I do not know in details how deque is implemented. A quick 
look seemed to show that trivial relocation should be fine, but I would 
appreciate a confirmation.

The extra parameter for __is_trivially_relocatable is not used, but I 
expect it will be as soon as the specializations of 
__is_trivially_relocatable become more advanced.

If I use or specialize __is_trivially_relocatable in many places, this 
forces to #include bits/stl_uninitialized.h in many places. I wonder if I 
should move some of that stuff. Since I may use it in std::swap, 
bits/move.h looks like a sensible place for the core pieces 
(__is_trivially_relocatable, and __relocate_object if I ever create that). 
That or type_traits.

Regtested on gcc112. I manually checked that there was a speed-up for 
operations on vector<deque<int>>, although doing any kind of benchmarking 
on gcc112 is hard, I'll test locally next time.

2018-10-26  Marc Glisse  <marc.glisse@inria.fr>

	PR libstdc++/87106
	* include/bits/stl_algobase.h: Include <type_traits>.
	(__niter_base): Add noexcept specification.
	* include/bits/stl_deque.h: Include <bits/stl_uninitialized.h>.
	(__is_trivially_relocatable): Specialize for deque.
	* include/bits/stl_iterator.h: Include <type_traits>.
	(__niter_base): Add noexcept specification.
	* include/bits/stl_uninitialized.h (__is_trivially_relocatable):
	Add parameter for meta-programming.
	(__relocate_a_1, __relocate_a): Add noexcept specification.
	* include/bits/stl_vector.h (__use_relocate): Test __relocate_a.

--
Marc Glisse

Index: libstdc++-v3/include/bits/stl_algobase.h
===================================================================
--- libstdc++-v3/include/bits/stl_algobase.h	(revision 265522)
+++ libstdc++-v3/include/bits/stl_algobase.h	(working copy)
@@ -62,20 +62,23 @@
 #include <ext/type_traits.h>
 #include <ext/numeric_traits.h>
 #include <bits/stl_pair.h>
 #include <bits/stl_iterator_base_types.h>
 #include <bits/stl_iterator_base_funcs.h>
 #include <bits/stl_iterator.h>
 #include <bits/concept_check.h>
 #include <debug/debug.h>
 #include <bits/move.h> // For std::swap
 #include <bits/predefined_ops.h>
+#if __cplusplus >= 201103L
+# include <type_traits>
+#endif
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
 #if __cplusplus < 201103L
   // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a
   // nutshell, we are partially implementing the resolution of DR 187,
   // when it's safe, i.e., the value_types are equal.
   template<bool _BoolType>
@@ -268,20 +271,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       if (__comp(__a, __b))
 	return __b;
       return __a;
     }
 
   // Fallback implementation of the function in bits/stl_iterator.h used to
   // remove the __normal_iterator wrapper. See copy, fill, ...
   template<typename _Iterator>
     inline _Iterator
     __niter_base(_Iterator __it)
+    _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
     { return __it; }
 
   // Reverse the __niter_base transformation to get a
   // __normal_iterator back again (this assumes that __normal_iterator
   // is only used to wrap random access iterators, like pointers).
   template<typename _From, typename _To>
     inline _From
     __niter_wrap(_From __from, _To __res)
     { return __from + (__res - std::__niter_base(__from)); }
 
Index: libstdc++-v3/include/bits/stl_deque.h
===================================================================
--- libstdc++-v3/include/bits/stl_deque.h	(revision 265522)
+++ libstdc++-v3/include/bits/stl_deque.h	(working copy)
@@ -54,20 +54,21 @@
  */
 
 #ifndef _STL_DEQUE_H
 #define _STL_DEQUE_H 1
 
 #include <bits/concept_check.h>
 #include <bits/stl_iterator_base_types.h>
 #include <bits/stl_iterator_base_funcs.h>
 #if __cplusplus >= 201103L
 #include <initializer_list>
+#include <bits/stl_uninitialized.h> // for __is_trivially_relocatable
 #endif
 
 #include <debug/assertions.h>
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
   /**
@@ -2359,14 +2360,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// See std::deque::swap().
   template<typename _Tp, typename _Alloc>
     inline void
     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
     _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
     { __x.swap(__y); }
 
 #undef _GLIBCXX_DEQUE_BUF_SIZE
 
 _GLIBCXX_END_NAMESPACE_CONTAINER
+
+#if __cplusplus >= 201103L
+  // std::allocator is safe, but it is not the only allocator
+  // for which this is valid.
+  template<class _Tp>
+    struct __is_trivially_relocatable<_GLIBCXX_STD_C::deque<_Tp>>
+    : true_type { };
+#endif
+
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace std
 
 #endif /* _STL_DEQUE_H */
Index: libstdc++-v3/include/bits/stl_iterator.h
===================================================================
--- libstdc++-v3/include/bits/stl_iterator.h	(revision 265522)
+++ libstdc++-v3/include/bits/stl_iterator.h	(working copy)
@@ -59,20 +59,24 @@
 
 #ifndef _STL_ITERATOR_H
 #define _STL_ITERATOR_H 1
 
 #include <bits/cpp_type_traits.h>
 #include <ext/type_traits.h>
 #include <bits/move.h>
 #include <bits/ptr_traits.h>
 
 #if __cplusplus > 201402L
+# include <type_traits>
+#endif
+
+#if __cplusplus > 201402L
 # define __cpp_lib_array_constexpr 201603
 #endif
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   /**
    * @addtogroup iterators
    * @{
@@ -997,20 +1001,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _Iterator, typename _Container>
     _Iterator
     __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
+    _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
     { return __it.base(); }
 
 #if __cplusplus >= 201103L
 
   /**
    * @addtogroup iterators
    * @{
    */
 
   // 24.4.3  Move iterators
Index: libstdc++-v3/include/bits/stl_uninitialized.h
===================================================================
--- libstdc++-v3/include/bits/stl_uninitialized.h	(revision 265522)
+++ libstdc++-v3/include/bits/stl_uninitialized.h	(working copy)
@@ -887,60 +887,63 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 			 __dest, std::move(*__orig)))
 	     && noexcept(std::allocator_traits<_Allocator>::destroy(
 			    __alloc, std::__addressof(*__orig))))
     {
       typedef std::allocator_traits<_Allocator> __traits;
       __traits::construct(__alloc, __dest, std::move(*__orig));
       __traits::destroy(__alloc, std::__addressof(*__orig));
     }
 
   // This class may be specialized for specific types.
-  template<typename _Tp>
+  template<typename _Tp, typename = void>
     struct __is_trivially_relocatable
     : is_trivial<_Tp> { };
 
   template <typename _Tp, typename _Up>
     inline __enable_if_t<std::__is_trivially_relocatable<_Tp>::value, _Tp*>
     __relocate_a_1(_Tp* __first, _Tp* __last,
-		   _Tp* __result, allocator<_Up>& __alloc)
+		   _Tp* __result, allocator<_Up>& __alloc) noexcept
     {
       ptrdiff_t __count = __last - __first;
       __builtin_memmove(__result, __first, __count * sizeof(_Tp));
       return __result + __count;
     }
 
   template <typename _InputIterator, typename _ForwardIterator,
 	    typename _Allocator>
     inline _ForwardIterator
     __relocate_a_1(_InputIterator __first, _InputIterator __last,
 		   _ForwardIterator __result, _Allocator& __alloc)
+    noexcept(noexcept(std::__relocate_object_a(std::addressof(*__result),
+					       std::addressof(*__first),
+					       __alloc)))
     {
       typedef typename iterator_traits<_InputIterator>::value_type
 	_ValueType;
       typedef typename iterator_traits<_ForwardIterator>::value_type
 	_ValueType2;
       static_assert(std::is_same<_ValueType, _ValueType2>::value);
-      static_assert(noexcept(std::__relocate_object_a(std::addressof(*__result),
-						      std::addressof(*__first),
-						      __alloc)));
       _ForwardIterator __cur = __result;
       for (; __first != __last; ++__first, (void)++__cur)
 	std::__relocate_object_a(std::__addressof(*__cur),
 				 std::__addressof(*__first), __alloc);
       return __cur;
     }
 
   template <typename _InputIterator, typename _ForwardIterator,
 	    typename _Allocator>
     inline _ForwardIterator
     __relocate_a(_InputIterator __first, _InputIterator __last,
 		 _ForwardIterator __result, _Allocator& __alloc)
+    noexcept(noexcept(__relocate_a_1(std::__niter_base(__first),
+				     std::__niter_base(__last),
+				     std::__niter_base(__result), __alloc)))
     {
       return __relocate_a_1(std::__niter_base(__first),
 			    std::__niter_base(__last),
 			    std::__niter_base(__result), __alloc);
     }
 #endif
 
 _GLIBCXX_END_NAMESPACE_VERSION
 } // namespace
 
Index: libstdc++-v3/include/bits/stl_vector.h
===================================================================
--- libstdc++-v3/include/bits/stl_vector.h	(revision 265522)
+++ libstdc++-v3/include/bits/stl_vector.h	(working copy)
@@ -417,24 +417,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       const_iterator;
       typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
       typedef std::reverse_iterator<iterator>		reverse_iterator;
       typedef size_t					size_type;
       typedef ptrdiff_t					difference_type;
       typedef _Alloc					allocator_type;
 
     private:
 #if __cplusplus >= 201103L
       static constexpr bool __use_relocate =
-	noexcept(std::__relocate_object_a(
-			std::addressof(*std::declval<pointer>()),
-			std::addressof(*std::declval<pointer>()),
-			std::declval<_Tp_alloc_type&>()));
+	noexcept(std::__relocate_a(std::declval<pointer>(),
+				   std::declval<pointer>(),
+				   std::declval<pointer>(),
+				   std::declval<_Tp_alloc_type&>()));
 #endif
 
     protected:
       using _Base::_M_allocate;
       using _Base::_M_deallocate;
       using _Base::_M_impl;
       using _Base::_M_get_Tp_allocator;
 
     public:
       // [23.2.4.1] construct/copy/destroy