libstdc++: Extend memcmp optimization in std::lexicographical_compare
Jonathan Wakely
jwakely@redhat.com
Mon Jun 8 23:02:22 GMT 2020
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
More information about the Libstdc++
mailing list