Keep std::deque algos specializations in Debug mode

François Dumont frs.dumont@gmail.com
Fri Sep 7 16:30:00 GMT 2018 

I realized that I was not checking the Debug implementations.

Doing so also have the advantage to show clearly which overload of the 
algos is being used. If it is using the correct Debug overload I 
consider that there are chances that it is also using the correct normal 
overload. This is easier to check than using gdb.

This way I found out that I was not calling the expected std::fill 
because I pass 0 rather than '\0'. I wonder if we could have the correct 
behavior if we were simply using 0. It would be great if gcc was using 
the fill deque iterator overload even if warning in case the pass int 
value do not match the deque value type.

Ok to commit ?

François


On 09/06/2018 10:07 PM, François Dumont wrote:
> On 09/04/2018 02:59 PM, Jonathan Wakely wrote:
>
>>
>>>   template<typename _Tp>
>>>     void
>>> -    fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
>>> -     const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& 
>>> __value)
>>> +    fill(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& 
>>> __first,
>>> +     const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
>>> +     const _Tp& __value)
>>>     {
>>> -      typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self;
>>> -
>>> -      for (typename _Self::_Map_pointer __node = __first._M_node + 1;
>>> -           __node < __last._M_node; ++__node)
>>> -    std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
>>> +      typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, 
>>> _Tp*>::_Self
>>> +    _Self;
>>>
>>>       if (__first._M_node != __last._M_node)
>>>     {
>>>       std::fill(__first._M_cur, __first._M_last, __value);
>>> +
>>> +      for (typename _Self::_Map_pointer __node = __first._M_node + 1;
>>> +           __node != __last._M_node; ++__node)
>>
>> Is there any particular reason to change this from using < to != for
>> the comparison?
>
> I consider that the reason for having a < comparison was that this 
> loop was done before checking __first._M_node != __last._M_node. As I 
> moved it inside the block I also prefer to use a usual condition when 
> iterating other iterators/pointers.
>
> Isn't it a simpler operation ? Do you fear a compiler warning about it 
> like we used to have in vector implementation before introducing the 
> __builtin_unreachable calls ?
>
>>
>> (This change is part of the reason I asked for the ChangeLog, but you
>> didn't mention it in the ChangeLog).
> I had forgotten about it but I can add it in ChangeLog.
>>
>> Moving it inside the condition makes sense (not only does it avoid a
>> branch in the single-page case, but means we fill the elements in
>> order).
> Yes, it is the main reason I moved it, I should have signal it when I 
> submit the patch.
>>
>>
>>> +        std::fill(*__node, *__node + _Self::_S_buffer_size(), 
>>> __value);
>>> +
>>>       std::fill(__last._M_first, __last._M_cur, __value);
>>>     }
>>>       else
>>
>> The rest of the code changes look fine, I just wondered about that
>> bit.
>>
>> I do have some comments on the new tests though ...
>>
>>
>>> +
>>> +void test01()
>>> +{
>>> +  std::deque<char> d;
>>> +  for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
>>> +    d.push_back(c);
>>> +
>>> +  std::deque<char> dest(std::numeric_limits<char>::max(), '\0');
>>
>> These deques only have 127 or 255 elements (depending on
>> is_signed<char>) which will fit on a single page of a deque (the
>> default is 512 bytes per page).
>>
>> That means the tests don't exercise the logic for handling
>> non-contiguous blocks of memory.
>>
>> Ideally we'd want to test multiple cases:
>>
>> - a single page, with/without empty capacity at front/back
>> - multiple pages, with/without empty capacity at front/back
>>
>> That would be 8 cases. I think we want to test at least a single
>> page and multiple pages.
>>
> I think I started to create the fill.cc which require usage of char to 
> make sure it uses __builtin_memset and then extrapolated to other algos.
>
> But I had already reviewed those tests for a patch I'll submit after 
> this one so here is the revisited tests.
>
> In this new proposal I also introduce a template alias to simplify the 
> C++11 overloads. I define it in __gnu_debug to avoid polluting std 
> namespace with a non-Standard thing.
>
>     * include/bits/stl_deque.h
>     (fill, copy, copy_backward, move, move_backward): Move overloads for
>     std::deque iterators in std namespace.
>     * include/bits/deque.tcc: Likewise.
>     (fill): Move loop on nodes inside branch when first and last nodes 
> are
>     different. Replace for loop < condition on nodes with a !=.
>     * include/debug/deque
>     (__gnu_debug::_SDeque_iterator<>, 
> __gnu_debug::_SDeque_const_iterator):
>     New template aliases.
>     (fill, copy, copy_backward, move, move_backward):
>     New overloads for std::__debug::deque iterators. Forward to normal 
> and
>     optimized implementations after proper debug checks.
>     * testsuite/23_containers/deque/copy.cc: New.
>     * testsuite/23_containers/deque/copy_backward.cc: New.
>     * testsuite/23_containers/deque/fill.cc: New.
>     * testsuite/23_containers/deque/move.cc: New.
>     * testsuite/23_containers/deque/move_backward.cc: New.
>
> Tested under Linux x86_64.
>
> Ok to commit ?
>
> François


-------------- next part --------------
A non-text attachment was scrubbed...
Name: deque_debug_algos.patch
Type: text/x-patch
Size: 55284 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20180907/0a11e280/attachment.bin>

More information about the Libstdc++ mailing list