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

[François Dumont]

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.