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

[François Dumont via Gcc-patches]

On 09/06/20 10:53 pm, Jonathan Wakely wrote:
On 09/06/20 22:42 +0200, François Dumont via Libstdc++ wrote:
On 09/06/20 6:11 pm, Jonathan Wakely wrote:
On 09/06/20 00:02 +0100, Jonathan Wakely wrote:
On 08/06/20 22:08 +0100, Jonathan Wakely wrote:
On 08/06/20 19:20 +0100, 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.

Here's a simpler version, which doesn't alter anything for the
existing code (i.e. all iterators that aren't deque iterators) and
also fixes the infinite loop bug.

This seems simpler and less invasive.

Please take a look.

I've actually tested it in debug mode now, and ...

diff --git a/libstdc++-v3/include/debug/safe_iterator.tcc 
b/libstdc++-v3/include/debug/safe_iterator.tcc
index 888ac803ae5..db6a301655f 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

This should return bool here.

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

And here.

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

And here.

And I've also enhanced the tests so they catch the bug I created where
the __lexicographical_compare_aux1 overload taking two ranges of deque
iterators was still trying to return a three-way result, rather than
bool.

Corrected patch attached.

But, the 25_algorithms/lexicographical_compare/deque_iterators/1.cc
test doesn't actually test the new code properly, because it only uses
deque<int> which means memcmp isn't even used. We need better tests.


.

I didn't consider adding one cause I didn't need it to challenge the 
new code dedicated to deque iterators. I don't remember if I really 
check but for me there are already checks involving memcmp.

Also I haven't found how to write a test checking that memcmp is 
indeed call, I haven't try hard neither.

It doesn't need to check that memcmp is actually called. The point is
that a bug in the __lexicographical_compare<true>::__lc function won't
get noticed if we never call that function.
Sure, I just thought this call was already tested as it isn't new code 
introduce by this patch.

The attached patch adds tests for deque<unsigned char> which will use
the memcmp code.

This reminds me that I was going to extend the condition for using
memcmp to also apply to unsigned integers with sizeof(T) > 1 on big
endian targets.

This illustrates what I tried to avoid in my original patch, the code 
duplication. I was calling __lexicographical_compare_aux1 because I 
didn't want to duplicate the code to compute __simple.

Of course it can be expose as a template using.