Improve relocation

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Improve relocation

Marc Glisse-6
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  <[hidden email]>

  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