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

[Jonathan Wakely]

On 09/06/20 17:11 +0100, 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.

*Really* attached this time.


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

>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.txt
Type: text/x-patch
Size: 22343 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200609/3f3812bf/attachment-0001.bin>