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

[Jonathan Wakely <jwakely@redhat.com>]

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.

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