Keep std::deque algos specializations in Debug mode

François Dumont frs.dumont@gmail.com
Thu Sep 6 20:08:00 GMT 2018 

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: 29943 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20180906/195309d2/attachment.bin>

More information about the Libstdc++ mailing list