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

[Jonathan Wakely <jwakely at redhat dot com>]

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