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

Jonathan Wakely jwakely@redhat.com
Tue Jun 9 20:38:28 GMT 2020 

On 09/06/20 22:20 +0200, François Dumont via Libstdc++ wrote:
>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 ?

Well the question is redundant given my proposed patch, because it
doesn't use __lexicographical_compare_aux1 on the internal pointers. I
added a new function, so that __lexicographical_compare_aux1 doesn't
need to be changed.

>>
>>>+          __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.

Yes, but tag dispatching also selects the right overload for the right
iterator category.

>Isn't it making overload resolution better ?

No, SFINAE makes overload resolution very expensive.

>>
>>>+    __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.

Yes, I understand that part.

>But I still want only 2 implementations, one 
>when 1st range are deque iterators and another when 2nd range are 
>deque iterators.

But that's silly, the two cases are equivalent, you just need to flip
the result. You don't need two completely different implementations
for comparing deque+other and other+deque. And the two completely
different implementations are *completely* different, for no obvious
reason (one even has a bug that loops forever).

>I just chose that when I have 2 deque iterator ranges 
>I'll use the implementation where 1st range is such.

The case where you have two deque iterators can be handled by a
specialized function that unwraps both sets of deque iterators, and
the other two cases can share the same logic.



>>
>>>+  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.

Which works fine with the patch I proposed.

>>
>>
>>>+    }
>>>+
>>>_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.

I already sent a complete patch.

More information about the Libstdc++ mailing list