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

[Jonathan Wakely]

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.