Re: libstdc++: Extend memcmp optimization in std::lexicographical_compare

["François Dumont" <frs.dumont@gmail.com>]

On 08/06/20 8:20 pm, Jonathan Wakely wrote:
> On 05/06/20 22:24 +0200, François Dumont via Libstdc++ wrote:
>> Hi
>>
>>     Here is the last of my algo patches this time to extend the 
>> memcmp optimization to std::deque iterators and _GLIBCXX_DEBUG mode.
>>
>>     To do so I had to return int in implementation details of 
>> lexicographical_compare to make sure we can treat a deque iterator 
>> range by chunk in a performant way.
>>
>> Tested under Linux x86_64 normal and debug modes.
>>
>>             * include/bits/stl_algobase.h
>>             (__lexicographical_compare_impl): Return int.
>>             (__lexicographical_compare::__lc): Likewise.
>>             (__lexicographical_compare_aux1(_II1, _II1, 
>> _II2, _II2)): New.
>> (__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>             _II2, _II2)): Declare.
>>             (__lexicographical_compare_aux1(_II1, _II1,
>>             _Deque_iterator<>, _Deque_iterator<>)): Declare.
>> (__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
>>             _Deque_iterator<>, _Deque_iterator<>)): Declare.
>>             (__lexicographical_compare_aux): Adapt, call 
>> later.
>
> Is this meant to say "latter"? That's still not correct grammar
> though. I think it would be better to name the function it calls
> explicitly: "Call __lexicographical_compare_aux1."

Ok.


>
>>            
>> (__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
>>             _II2, _II2)): Declare.
>>             (__lexicographical_compare_aux(_II1, _II1,
>>             _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>            
>> (__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
>>             _Safe_iterator<>, _Safe_iterator<>)): Declare.
>>             (std::lexicographical_compare): Adapt, call 
>> later without __niter_base
>>             usage.
>>             * include/bits/deque.tcc (__lex_cmp_dit): New.
>>             (__lexicographical_compare_aux1): New.
>>             * include/debug/safe_iterator.tcc
>>             (__lexicographical_compare_aux(const 
>> _Safe_iterator<>&,
>>             const _Safe_iterator<>&, _II2, _II2)): New.
>>             (__lexicographical_compare_aux(
>>             const _Safe_iterator<>&, const_Safe_iterator<>&,
>>             const _Safe_iterator<>&, const 
>> _Safe_iterator<>&)): New.
>>             * 
>> testsuite/25_algorithms/lexicographical_compare/1.cc (test6, test7):
>>             New.
>>             * 
>> testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
>>             New test.
>>
>> Ok to commit ?
>>
>> François
>>
>>
>
>> diff --git a/libstdc++-v3/include/bits/deque.tcc 
>> b/libstdc++-v3/include/bits/deque.tcc
>> index 1d32a1691c7..d7dbe64f3e1 100644
>> --- a/libstdc++-v3/include/bits/deque.tcc
>> +++ b/libstdc++-v3/include/bits/deque.tcc
>> @@ -1261,6 +1261,98 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>       return true;
>>     }
>>
>> +  template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
>
> _II is the wrong name here, it mean InputIterator. All callers of this
> function are constrained for random access iterators. This cannot be
> called with an input iterator. Please use _RAIter.
>
>> +    int
>> +    __lex_cmp_dit(
>> +    const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
>> +    const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
>> +    _II __first2, _II __last2)
>> +    {
>> +      typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
>> +      typedef typename _Iter::difference_type difference_type;
>> +
>> +      if (__first1._M_node != __last1._M_node)
>> +    {
>> +      difference_type __len = __last2 - __first2;
>> +      difference_type __flen
>
> What does "flen" mean? Why not use len2 for last2 - first2, as we do
> elsewhere? And then use len for min(len1, len2)?

short for 'first lenght' because it is the first iterator range. 
len1/len2 is better of course.

>
>
>> +        = std::min(__len, __first1._M_last - __first1._M_cur);
>> +      if (int __ret = std::__lexicographical_compare_aux1(
>
> This call (and the three later in this function) will do overload
> resolution again on the full set of __lexicographical_compare_aux1
> overloads, which includes the ones for deque iterators. But we know
> that __first1._M_cur and __first1._M_last are not deque iterators.
>
> __first2 could be a deque iterator, but I'm not sure if we really want
> one function that has to handle that case anyway.

Considering the performance results on the std::copy algo it appeared to 
me that just "unrolling" the deque iterator is already an enhancement. 
Looping on pointers is better than looping on deque iterators.

Is it what you wonder ?

>
>> +          __first1._M_cur, __first1._M_last, __first2, __first2 + 
>> __flen))
>> +        return __ret;
>> +
>> +      __first2 += __flen;
>> +      __len -= __flen;
>> +      __flen = std::min<size_t>(__len, _Iter::_S_buffer_size());
>> +      for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
>> +           __node != __last1._M_node;
>> +           __first2 += __flen, __len -= __flen,
>> +           __flen = std::min<size_t>(__len, _Iter::_S_buffer_size()),
>> +           ++__node)
>> +        if (int __ret = std::__lexicographical_compare_aux1(
>> +          *__node, *__node + _Iter::_S_buffer_size(),
>> +          __first2, __first2 + __flen))
>> +          return __ret;
>> +
>> +      return std::__lexicographical_compare_aux1(
>> +        __last1._M_first, __last1._M_cur, __first2, __last2);
>> +    }
>> +
>> +      return std::__lexicographical_compare_aux1(
>> +          __first1._M_cur, __last1._M_cur, __first2, __last2);
>> +    }
>> +
>> +  template<typename _Tp1, typename _Ref1, typename _Ptr1,
>> +       typename _II2>
>
> This is not an input iterator either.
>
>> +    typename __gnu_cxx::__enable_if<
>> +      __is_random_access_iter<_II2>::__value, int>::__type
>
> This should be inline.
>
> Also, I'm curious why these overloads use __enable_if rather than the
> conventional approach of tag dispatching using iterator_category.
> (The same question applies to th __equal_aux1 and __copy_move_a1
> overloads for deque iterators as well). It doesn't really matter
> though.

Those functions are using Rai operations like operator- so I thought 
that they they should be enabled only on the right category of iterator. 
Maybe overload would have been fine too.

Isn't it making overload resolution better ?

>
>> +    __lexicographical_compare_aux1(
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>> +        _II2 __first2, _II2 __last2)
>> +    { return std::__lex_cmp_dit(__first1, __last1, __first2, 
>> __last2); }
>> +
>> +  template<typename _Tp1, typename _Ref1, typename _Ptr1,
>> +       typename _Tp2, typename _Ref2, typename _Ptr2>
>> +    int
>
> This should be inline.
>
>> +    __lexicographical_compare_aux1(
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>> +    { return std::__lex_cmp_dit(__first1, __last1, __first2, 
>> __last2); }
>
> I'm not convinced it's useful for this function and the one above it
> to share the same logic.
This overload is here just to disambiguate a call with 4 deque iterators 
cause in this case the compiler wouldn't know which of the 2 other 
overloads to call. But I still want only 2 implementations, one when 1st 
range are deque iterators and another when 2nd range are deque 
iterators. I just chose that when I have 2 deque iterator ranges I'll 
use the implementation where 1st range is such.
>
>> +  template<typename _II1,
>> +       typename _Tp2, typename _Ref2, typename _Ptr2>
>> +    typename __gnu_cxx::__enable_if<
>> +      __is_random_access_iter<_II1>::__value, int>::__type
>> +    __lexicographical_compare_aux1(
>> +        _II1 __first1, _II1 __last1,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2)
>> +    {
>> +      typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> 
>> _Iter;
>> +      typedef typename _Iter::difference_type difference_type;
>> +
>> +      difference_type __len = __last1 - __first1;
>> +      while (__len > 0)
>> +    {
>> +      const difference_type __flen = __first2._M_node == 
>> __last2._M_node
>> +        ? __last2._M_cur - __first2._M_cur
>> +        : __first2._M_last - __first2._M_cur;
>> +      const difference_type __clen = std::min(__len, __flen);
>
> "flen"? "clen"?
just 'c' for const I think
>> +      if (int __ret = std::__lexicographical_compare_aux1(
>> +                __first1, __first1 + __clen,
>> +                __first2._M_cur, __first2._M_cur + __flen))
>> +        return __ret;
>> +
>> +      __first1 += __clen;
>> +      __len -= __clen;
>> +      __first2 += __clen;
>> +    }
>> +
>> +      return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>
> Isn't this function doing basically the same as __lex_cmp_dit? Why
> does it not use the same logic?
>
> Can this whole function just negate the result of __lex_cmp_dit called
> with the arguments switched?
>
>   return -std::__lex_cmp_dit(__first2, __last2, __first1, __last1);
>
> That would also fix the bug that makes the following loop forever:
>
>   std::deque<int> d;
>   int i = 0;
>   std::lexicographical_compare(&i, &i + 1, d.begin(), d.end());
I have to consider this, I also wanted to cover comparison with raw 
pointer ranges or vector iterators that could be replaced with memcmp.
>
>
>> +    }
>> +
>> _GLIBCXX_END_NAMESPACE_VERSION
>> } // namespace std
>>
>> diff --git a/libstdc++-v3/include/bits/stl_algobase.h 
>> b/libstdc++-v3/include/bits/stl_algobase.h
>> index 0163d8f902d..ecc50a10c9d 100644
>> --- a/libstdc++-v3/include/bits/stl_algobase.h
>> +++ b/libstdc++-v3/include/bits/stl_algobase.h
>> @@ -1279,7 +1279,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>
>>   template<typename _II1, typename _II2, typename _Compare>
>>     _GLIBCXX20_CONSTEXPR
>> -    bool
>> +    int
>>     __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
>>                    _II2 __first2, _II2 __last2,
>>                    _Compare __comp)
>> @@ -1288,16 +1288,18 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>       typedef typename iterator_traits<_II2>::iterator_category 
>> _Category2;
>>       typedef std::__lc_rai<_Category1, _Category2> __rai_type;
>>
>> -      __last1 = __rai_type::__newlast1(__first1, __last1, __first2, 
>> __last2);
>> -      for (; __first1 != __last1 && __rai_type::__cnd2(__first2, 
>> __last2);
>> +      _II1 __new_last1
>> +    = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
>> +      for (; __first1 != __new_last1 && __rai_type::__cnd2(__first2, 
>> __last2);
>>        ++__first1, (void)++__first2)
>>     {
>>       if (__comp(__first1, __first2))
>> -        return true;
>> +        return -1;
>>       if (__comp(__first2, __first1))
>> -        return false;
>> +        return 1;
>>     }
>> -      return __first1 == __last1 && __first2 != __last2;
>> +
>> +      return __first1 == __last1 ? (__first2 != __last2 ? -1 : 0) : 1;
>
> This is going to produce worse code for the common (non-deque) case,
> isn't it?
>
>
>>     }
>>
>>   template<bool _BoolType>
>> @@ -1305,7 +1307,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>     {
>>       template<typename _II1, typename _II2>
>>     _GLIBCXX20_CONSTEXPR
>> -    static bool
>> +    static int
>>     __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
>>     {
>>       using __gnu_cxx::__ops::__iter_less_iter;
>> @@ -1320,7 +1322,7 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>     {
>>       template<typename _Tp, typename _Up>
>>     _GLIBCXX20_CONSTEXPR
>> -    static bool
>> +    static int
>>     __lc(const _Tp* __first1, const _Tp* __last1,
>>          const _Up* __first2, const _Up* __last2)
>>     {
>> @@ -1328,16 +1330,44 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>       const size_t __len2 = __last2 - __first2;
>>       if (const size_t __len = std::min(__len1, __len2))
>>         if (int __result = std::__memcmp(__first1, __first2, __len))
>> -          return __result < 0;
>> -      return __len1 < __len2;
>> +          return __result;
>> +
>> +      return __len1 < __len2 ? -1 : (__len2 < __len1 ? 1 : 0);
>
> Again, this will produce worse code.
>
> If you made it return ptrdiff_t instead of int you could just do:
>
>   return ptrdiff_t(__len1 - __len2);
>
> But I think we should just not change these __lc helpers, and not try
> to reuse them for deque iterators. We can define new helpers that
> return the 3-way result that is needed for comparing deque iterators.
>
Yes, it sounds promising.
>
>> +  template<typename _Tp1, typename _Ref1, typename _Ptr1,
>> +       typename _II2>
>> +    typename __gnu_cxx::__enable_if<
>> +      __is_random_access_iter<_II2>::__value, int>::__type
>> +    __lexicographical_compare_aux1(
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>> +        _II2, _II2);
>> +
>> +  template<typename _II1,
>> +       typename _Tp2, typename _Ref2, typename _Ptr2>
>> +    typename __gnu_cxx::__enable_if<
>> +      __is_random_access_iter<_II1>::__value, int>::__type
>> +    __lexicographical_compare_aux1(
>> +        _II1, _II1,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
>> +
>> +  template<typename _Tp1, typename _Ref1, typename _Ptr1,
>> +       typename _Tp2, typename _Ref2, typename _Ptr2>
>> +    int
>> +    __lexicographical_compare_aux1(
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
>> +        _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
>> +
>>   template<typename _II1, typename _II2>
>>     _GLIBCXX20_CONSTEXPR
>> -    inline bool
>> -    __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
>> -                  _II2 __first2, _II2 __last2)
>> +    inline int
>> +    __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
>> +                   _II2 __first2, _II2 __last2)
>
> If you rename this to __lexicographical_compare_aux2 instead and add
> a one-line forwarding function called __lexicographical_compare_aux1,
> then the code above for deque iterators can call the aux2 overload
> directly, to avoid doing overload resolution on aux1 again.
>
>>     {
>>       typedef typename iterator_traits<_II1>::value_type _ValueType1;
>>       typedef typename iterator_traits<_II2>::value_type _ValueType2;
>> @@ -1360,6 +1390,43 @@ _GLIBCXX_END_NAMESPACE_CONTAINER
>>                                 __first2, __last2);
>>     }
>>
>> +  template<typename _II1, typename _II2>
>> +    _GLIBCXX20_CONSTEXPR
>> +    inline int
>> +    __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
>> +                  _II2 __first2, _II2 __last2)
>> +    {
>> +      return 
>> std::__lexicographical_compare_aux1(std::__niter_base(__first1),
>> +                         std::__niter_base(__last1),
>> +                         std::__niter_base(__first2),
>> +                         std::__niter_base(__last2));
>> +    }
>> +
>> +  template<typename _Ite1, typename _Seq1, typename _Cat1,
>
> Please don't introduce any more "Ite" parameters, this should be _It1
> or _Iter1.
>
>> +       typename _II2>
>> +    int
>> +    __lexicographical_compare_aux(
>> +        const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>> +        const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>> +        _II2, _II2);
>> +
>> +  template<typename _II1,
>> +       typename _Ite2, typename _Seq2, typename _Cat2>
>> +    int
>> +    __lexicographical_compare_aux(
>> +        _II1, _II1,
>> +        const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
>> +        const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
>> +
>> +  template<typename _Ite1, typename _Seq1, typename _Cat1,
>> +       typename _Ite2, typename _Seq2, typename _Cat2>
>> +    int
>> +    __lexicographical_compare_aux(
>> +        const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>> +        const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>&,
>> +        const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&,
>> +        const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>&);
>> +
>>   template<typename _ForwardIterator, typename _Tp, typename _Compare>
>>     _GLIBCXX20_CONSTEXPR
>>     _ForwardIterator
>> @@ -1659,10 +1726,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
>>       __glibcxx_requires_valid_range(__first1, __last1);
>>       __glibcxx_requires_valid_range(__first2, __last2);
>>
>> -      return 
>> std::__lexicographical_compare_aux(std::__niter_base(__first1),
>> -                        std::__niter_base(__last1),
>> -                        std::__niter_base(__first2),
>> -                        std::__niter_base(__last2));
>> +      return std::__lexicographical_compare_aux(__first1, __last1,
>> +                        __first2, __last2) < 0;
>
> Why does __lexicographical_compare_aux need to change to return int?
>
> It looks like only __lexicographical_compare_aux1 gets called
> recursively for deque iterators, so only that needs to be able to
> return -1/0/+1 values.
>
Yes, I think I'll follow your idea based on your patch proposal.
>
>>     }
>>
>>   /**
>> @@ -1692,7 +1757,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
>>
>>       return std::__lexicographical_compare_impl
>>     (__first1, __last1, __first2, __last2,
>> -     __gnu_cxx::__ops::__iter_comp_iter(__comp));
>> +     __gnu_cxx::__ops::__iter_comp_iter(__comp)) < 0;
>>     }
>>
>> #if __cpp_lib_three_way_comparison
>> diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc 
>> b/libstdc++-v3/include/debug/safe_iterator.tcc
>> index 888ac803ae5..ca4e2d52d1d 100644
>> --- a/libstdc++-v3/include/debug/safe_iterator.tcc
>> +++ b/libstdc++-v3/include/debug/safe_iterator.tcc
>> @@ -470,6 +470,80 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>       return __equal_aux1(__first1, __last1, __first2);
>>     }
>>
>> +  template<typename _Ite1, typename _Seq1, typename _Cat1,
>> +       typename _II2>
>> +    int
>> +    __lexicographical_compare_aux(
>> +    const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>> +    const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>> +    _II2 __first2, _II2 __last2)
>> +    {
>> +      typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>> +      __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>> +      __glibcxx_check_valid_range(__first2, __last2);
>> +
>> +      if (__dist1.second > ::__gnu_debug::__dp_equality)
>> +    return std::__lexicographical_compare_aux(__first1.base(),
>> +                          __last1.base(),
>> +                          __first2, __last2);
>> +      return std::__lexicographical_compare_aux1(__first1, __last1,
>> +                         __first2, __last2);
>> +    }
>> +
>> +  template<typename _II1,
>> +       typename _Ite2, typename _Seq2, typename _Cat2>
>> +    int
>> +    __lexicographical_compare_aux(
>> +    _II1 __first1, _II1 __last1,
>> +    const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>> +    const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>> +    {
>> +      __glibcxx_check_valid_range(__first1, __last1);
>> +      typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2;
>> +      __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>> +
>> +      if (__dist2.second > ::__gnu_debug::__dp_equality)
>> +    return std::__lexicographical_compare_aux(__first1, __last1,
>> +                          __first2.base(),
>> +                          __last2.base());
>> +      return std::__lexicographical_compare_aux1(__first1, __last1,
>> +                         __first2, __last2);
>> +    }
>> +
>> +  template<typename _Ite1, typename _Seq1, typename _Cat1,
>> +       typename _Ite2, typename _Seq2, typename _Cat2>
>> +    int
>> +    __lexicographical_compare_aux(
>> +    const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1,
>> +    const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1,
>> +    const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2,
>> +    const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2)
>> +    {
>> +      typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1;
>> +      __glibcxx_check_valid_range2(__first1, __last1, __dist1);
>> +      typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2;
>> +      __glibcxx_check_valid_range2(__first2, __last2, __dist2);
>> +
>> +      if (__dist1.second > ::__gnu_debug::__dp_equality)
>> +    {
>> +      if (__dist2.second > ::__gnu_debug::__dp_equality)
>> +        return std::__lexicographical_compare_aux(__first1.base(),
>> +                              __last1.base(),
>> +                              __first2.base(),
>> +                              __last2.base());
>> +      return std::__lexicographical_compare_aux(__first1.base(),
>> +                            __last1.base(),
>> +                            __first2, __last2);
>> +    }
>> +
>> +      if (__dist2.second > ::__gnu_debug::__dp_equality)
>> +    return std::__lexicographical_compare_aux(__first1, __last1,
>> +                          __first2.base(),
>> +                          __last2.base());
>> +      return std::__lexicographical_compare_aux1(__first1, __last1,
>> +                        __first2, __last2);
>> +    }
>> +
>> _GLIBCXX_END_NAMESPACE_VERSION
>> } // namespace std
>>
>> diff --git 
>> a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc 
>> b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>> index 8c2f043f943..b8f92bacd85 100644
>> --- a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>> +++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/1.cc
>> @@ -74,6 +74,29 @@ test5()
>>                     con2.begin(), con2.end()) );
>> }
>>
>> +void
>> +test6()
>> +{
>> +  VERIFY( std::lexicographical_compare(array2, array2 + 2,
>> +                       array3, array3 + 3) );
>> +  VERIFY( !std::lexicographical_compare(array3, array3 + 3,
>> +                    array2, array2 + 2) );
>> +}
>> +
>> +using __gnu_test::random_access_iterator_wrapper;
>> +typedef test_container<int, random_access_iterator_wrapper> 
>> RaiContainer;
>
> Since last week you can use __gnu_test::random_access_container<int>
> for this.
>
>> +void
>> +test7()
>> +{
>> +  RaiContainer con2(array2, array2 + 2);
>> +  RaiContainer con3(array3, array3 + 3);
>> +  VERIFY( std::lexicographical_compare(con2.begin(), con2.end(),
>> +                       con3.begin(), con3.end()) );
>> +  VERIFY( !std::lexicographical_compare(con3.begin(), con3.end(),
>> +                    con2.begin(), con2.end()) );
>> +}
>> +
>> int main()
>> {
>> @@ -82,4 +105,6 @@ main()
>>   test3();
>>   test4();
>>   test5();
>> +  test6();
>> +  test7();
>> }
>> diff --git 
>> a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc 
>> b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc 
>>
>> new file mode 100644
>> index 00000000000..c686ad5677d
>> --- /dev/null
>> +++ 
>> b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc
>> @@ -0,0 +1,134 @@
>> +// Copyright (C) 2020 Free Software Foundation, Inc.
>> +//
>> +// This file is part of the GNU ISO C++ Library.  This library is free
>> +// software; you can redistribute it and/or modify it under the
>> +// terms of the GNU General Public License as published by the
>> +// Free Software Foundation; either version 3, or (at your option)
>> +// any later version.
>> +
>> +// This library is distributed in the hope that it will be useful,
>> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
>> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
>> +// GNU General Public License for more details.
>> +
>> +// You should have received a copy of the GNU General Public License 
>> along
>> +// with this library; see the file COPYING3.  If not see
>> +// <http://www.gnu.org/licenses/>.
>> +
>> +#include <algorithm>
>> +#include <vector>
>> +#include <deque>
>> +
>> +#include <ext/new_allocator.h>
>> +#include <ext/malloc_allocator.h>
>> +
>> +#include <testsuite_hooks.h>
>> +
>> +void test01()
>> +{
>> +  using namespace std;
>> +
>> +  deque<int> d;
>> +  for (int i = 0; i != 
>> _GLIBCXX_STD_C::__deque_buf_size(sizeof(int)); ++i)
>> +    d.push_back(i);
>> +
>> +  const deque<int>& cd = d;
>> +
>> +  VERIFY( !lexicographical_compare(cd.begin(), cd.end(), cd.begin(), 
>> cd.end()) );
>> +  VERIFY( !lexicographical_compare(cd.begin(), cd.end(), d.begin(), 
>> d.end()) );
>> +  VERIFY( !lexicographical_compare(d.begin(), d.end(), d.begin(), 
>> d.end()) );
>> +  VERIFY( !lexicographical_compare(d.begin(), d.end(), cd.begin(), 
>> cd.end()) );
>> +}
>> +
>> +void test02()
>> +{
>> +  using namespace std;
>> +
>> +  deque<int> d;
>> +  for (int i = 0; i != 1000; ++i)
>> +    d.push_back(i % 10);
>> +
>> +  VERIFY( !lexicographical_compare(d.begin(), d.begin() + 10,
>> +                   d.begin() + 20, d.begin() + 30) );
>> +  VERIFY( lexicographical_compare(d.begin(), d.begin() + 10,
>> +                  d.begin() + 20, d.begin() + 31) );
>> +  VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
>> +                   d.begin(), d.end() - 20) );
>> +
>> +  const deque<int>& cd = d;
>> +
>> +  VERIFY( !lexicographical_compare(cd.begin(), cd.begin() + 10,
>> +                   cd.begin() + 20, cd.begin() + 30) );
>> +  VERIFY( !lexicographical_compare(cd.begin() + 10, cd.end() - 10,
>> +                   d.begin(), d.end() - 20) );
>> +  VERIFY( !lexicographical_compare(d.begin() + 10, d.end() - 10,
>> +                   cd.begin(), cd.end() - 20) );
>> +}
>> +
>> +void test03()
>> +{
>> +  using namespace std;
>> +
>> +  deque<int> d1;
>> +  for (int i = 0; i != 1000; ++i)
>> +    d1.push_back(i % 10);
>> +
>> +  deque<int> d2(d1);
>> +  for (int i = 0; i != 10; ++i)
>> +    d2.pop_front();
>> +
>> +  VERIFY( !lexicographical_compare(d1.begin(), d1.begin() + 10,
>> +                   d2.begin(), d2.begin() + 10) );
>> +  VERIFY( !lexicographical_compare(d1.begin() + 10, d1.end() - 10,
>> +                   d2.begin(), d2.end() - 10) );
>> +
>> +  const deque<int>& cd1 = d1;
>> +  const deque<int>& cd2 = d2;
>> +
>> +  VERIFY( !lexicographical_compare(cd1.begin(), cd1.begin() + 10,
>> +                   cd2.begin() + 20, cd2.begin() + 30) );
>> +  VERIFY( !lexicographical_compare(cd1.begin() + 10, cd1.end() - 10,
>> +                   d2.begin(), d2.end() - 10) );
>> +  VERIFY( lexicographical_compare(cd2.begin() + 10, cd2.end() - 10,
>> +                  cd1.begin(), cd1.end() - 20) );
>> +}
>> +
>> +void test04()
>> +{
>> +  using namespace std;
>> +
>> +  deque<int> d;
>> +  for (int i = 0; i != 1024; ++i)
>> +    d.push_back(i);
>> +
>> +  vector<int> v(d.begin(), d.end());
>> +
>> +  VERIFY( lexicographical_compare(d.begin() + 5, d.end() - 1, 
>> v.begin() + 5, v.end()) );
>> +  VERIFY( !lexicographical_compare(v.begin(), v.end(), d.begin(), 
>> d.end()) );
>> +
>> +  const deque<int>& cd = d;
>> +
>> +  VERIFY( !lexicographical_compare(cd.begin(), cd.end(), v.begin(), 
>> v.end()) );
>> +  VERIFY( !lexicographical_compare(v.begin(), v.end(), cd.begin(), 
>> cd.end()) );
>> +}
>> +
>> +void test05()
>> +{
>> +  using namespace std;
>> +
>> +  int a[] = { 0, 1, 2, 3, 4 };
>> +  deque<int, __gnu_cxx::new_allocator<int> > d1(a, a + 5);
>> +  deque<int, __gnu_cxx::malloc_allocator<int> > d2(a, a + 5);
>> +
>> +  VERIFY( !lexicographical_compare(d1.begin(), d1.end(), d2.begin(), 
>> d2.end()) );
>> +}
>> +
>> +int main()
>> +{
>> +  test01();
>> +  test02();
>> +  test03();
>> +  test04();
>> +  test05();
>> +  return 0;
>> +}
>