PR 90409 Deque fiil/copy/move/copy_backward/move_backward/equal overloads

[Jonathan Wakely]

On 26/07/19 07:06 +0200, François Dumont wrote:
>A new version with tests added at the right place, in 25_algorithms, 
>next to the existing basic ones.
>
>Ok to commit ?

Are there any benchmarks showing the performance improvements?

It *should* be faster, but it's a lot of complicated code to add (and
maintain) so it'd better be worth it.

More comments inline below ...


>François
>
>On 6/19/19 7:32 PM, François Dumont wrote:
>>I wanted to implement Debug overloads for those already existing 
>>overloads but then realized that those algos could be generalized. 
>>This way we will benefit from the memmove replacement when operating 
>>with C array or std::array or std::vector iterators.
>>
>>I might do the same for lexicographical_compare one day.
>>
>>The ChangeLog below is quite huge so I attached it. I wonder if I 
>>could use deque::iterator and deque::const_iterator in place of the 
>>_Deque_iterator<> to reduce it ?
>>
>>Tested under Linux x86_64 normal and debug modes, ok to commit ?
>>
>>François
>>
>

>diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
>index 3f77b4f079c..9db869fb666 100644
>--- a/libstdc++-v3/include/bits/deque.tcc
>+++ b/libstdc++-v3/include/bits/deque.tcc
>@@ -967,155 +967,507 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
>     }
> 
>+_GLIBCXX_END_NAMESPACE_CONTAINER
>+
>   // Overload for deque::iterators, exploiting the "segmented-iterator
>   // optimization".
>   template<typename _Tp>
>     void
>-    fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
>-	 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
>+    fill(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
>+	 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
>+	 const _Tp& __value)
>     {
>-      typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
>-
>-      for (typename _Self::_Map_pointer __node = __first._M_node + 1;
>-           __node < __last._M_node; ++__node)
>-	std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
>+      typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
>+	_Self;

I know it was already there, but this is a terrible name. Using
"_Self" inside a class to refer to the class type itself is OK, but
using it outside the class doesn't make sense.

And anyway, isn't _Deque_iterator<T, T&, T*>::_Self just the same type as
_Deque_iterator<T, T&, T*> ? It should be something like:

      typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;

>+  template<typename _II, typename _Tp>
>+    typename enable_if<
>+      is_same<typename std::iterator_traits<_II>::iterator_category,
>+	      std::random_access_iterator_tag>::value,

Use is_base_of<random_access_iterator_tag, ...::iterator_category> so
it works for types derived from random_access_iterator_tag too.


>+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type
>+    move(_II __first, _II __last,
>+	 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
>+    {
>+      __glibcxx_requires_can_increment_range(__first, __last, __result);
> 
>-	  if (!__llen)
>-	    {
>-	      __llen = _Self::_S_buffer_size();
>-	      __lend = *(__last._M_node - 1) + __llen;
>-	    }
>-	  if (!__rlen)
>-	    {
>-	      __rlen = _Self::_S_buffer_size();
>-	      __rend = *(__result._M_node - 1) + __rlen;
>-	    }
>+      return __detail::__move_to_dit(__first, __last, __result);
>+    }
> 
>-	  const difference_type __clen = std::min(__len,
>-						  std::min(__llen, __rlen));
>-	  std::move_backward(__lend - __clen, __lend, __rend);
>-	  __last -= __clen;
>-	  __result -= __clen;
>-	  __len -= __clen;
>-	}
>-      return __result;
>+  template<typename _Tp, typename _OI>
>+    _OI
>+    move_backward(
>+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
>+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
>+      _OI __result)
>+    {
>+      __glibcxx_requires_can_decrement_range(__first, __last, __result);
>+
>+      return __detail::__move_backward_from_dit(__first, __last, __result);
>+    }
>+
>+  template<typename _Tp>
>+    _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>
>+    move_backward(
>+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first,
>+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*> __last,
>+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
>+    {
>+      __glibcxx_requires_can_decrement_range(__first, __last, __result);
>+
>+      return __detail::__move_backward_from_dit(__first, __last, __result);
>+    }
>+
>+  template<typename _II, typename _Tp>
>+    typename enable_if<
>+      is_same<typename std::iterator_traits<_II>::iterator_category,
>+	      std::random_access_iterator_tag>::value,

Here as well.

>+      _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::type
>+    move_backward(_II __first, _II __last,
>+		  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
>+    {
>+      __glibcxx_requires_can_decrement_range(__first, __last, __result);
>+
>+      return __detail::__move_backward_to_dit(__first, __last, __result);
>     }
> #endif

Please add "// C++11" after the #endif that corresponds to a
__cplusplus check. In general every #endif should have a ocmment,
unless the distance between the #if and the #endif is only a few
lines.


>+  template<typename _Tp, typename _OI>
>+    inline _OI
>+    copy(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
>+	 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __last,
>+	 _OI __result)
>+    {
>+      return std::copy(
>+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
>+	_GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
>+	__result);

I think this would be easier to read as:

    {
      typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, const _Tp&, const _Tp*>
        _Citer;
      return std::copy(_Citer(__first), _Citer(__last), __result);


>+  template<typename _II, typename _Tp>
>+    typename __gnu_cxx::__enable_if<
>+      __are_same<typename std::iterator_traits<_II>::iterator_category,
>+		 std::random_access_iterator_tag>::__value,

This won't work for iterator categories derived from
random_access_iterator_tag. Tag dispatching would work.


>+#endif

Please add "// C++11" after the #endif