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

[François Dumont]

On 09/06/20 10:53 pm, Jonathan Wakely wrote:
> On 09/06/20 22:42 +0200, François Dumont via Libstdc++ wrote:
>> 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.
>
> It doesn't need to check that memcmp is actually called. The point is
> that a bug in the __lexicographical_compare<true>::__lc function won't
> get noticed if we never call that function.
Sure, I just thought this call was already tested as it isn't new code 
introduce by this patch.
>
> The attached patch adds tests for deque<unsigned char> which will use
> the memcmp code.
>
> This reminds me that I was going to extend the condition for using
> memcmp to also apply to unsigned integers with sizeof(T) > 1 on big
> endian targets.
>
This illustrates what I tried to avoid in my original patch, the code 
duplication. I was calling __lexicographical_compare_aux1 because I 
didn't want to duplicate the code to compute __simple.

Of course it can be expose as a template using.