Deque rotate on current node

[François Dumont]

Hi

Any feedback regarding this patch ?

François


On 17/01/20 6:27 pm, François Dumont wrote:
> On 1/17/20 11:01 AM, Jonathan Wakely wrote:
>> On 20/05/19 07:39 +0200, François Dumont wrote:
>>> Hi
>>>
>>>   std::deque is supposed to be like a double-queue that you can 
>>> attack from front and back. But currrently its implementation makes 
>>> it behave differently when starting from a fresh deque. If push_back 
>>> then all goes well, it is copy/move to the current internal 'node'. 
>>> If push_front then a new 'node' is created and on next pop_back the 
>>> initial node will be deallocated without having ever be used.
>>>
>>>   This patch changes this behavior. As long as deque is empty we can 
>>> play with its state to make it push_back- or push_front-ready. It 
>>> will also benefit to the usage of deque in the std::stack.
>>>
>>>   More generally it could really improve scenario in which deque is 
>>> used as queue of elements exchanged between different threads. As 
>>> you need to make sure that consumers are faster than producers then 
>>> your deque should remain empty most of the time and so this proposed 
>>> patch should avoid nodes to be allocated/deallocated all the time.
>>
>> This benefits the case where you always push at the same end. But with
>> your patch if I do push_front then push_back,
>> we still allocate a second node even though the first one is nearly
>> empty.
>>
>> Would it be better to point into the middle of the node, not right at
>> the end or right at the beginning?
>
> That's purely empirical but I tend to think that when you need 
> push_back only you go with std::vector or std::deque, when you need 
> push_front only you go with std::deque and when you need both you go 
> with std::list. At least std::stack and std::queue are following this 
> axiom per default.
>
> The tradeoff you are describing is not worst than current situation 
> where you will eventually deallocate a node that you haven't used at all.
>
> Are you proposing to just init in the middle or also to always reset 
> when empty in the middle ? If we also reset in the middle those doing 
> always push_back or push_front will live with half a node unreachable.
>
> We could just init in the middle however. It would be a different 
> patch as this one is focus on just recycling the last empty node.
>
> I consider adding a flag keeping the info that the deque is 
> push_back|push_front|both-oriented updated based on its usage but I 
> doubt it would worth it. Moreover it would introduce an abi breakage.
>
>>
>>>     * include/bits/deque.tcc (deque<>::_M_push_back_aux):
>>>     Rotate on current node if deque is empty.
>>>     (deue<>::_M_push_front_aux): Likewise.
>>>
>>> Tested under Linux x86_64, ok to commit ?
>>>
>>> François
>>>
>>
>>> diff --git a/libstdc++-v3/include/bits/deque.tcc 
>>> b/libstdc++-v3/include/bits/deque.tcc
>>> index 2053afe1d69..245e3e712d8 100644
>>> --- a/libstdc++-v3/include/bits/deque.tcc
>>> +++ b/libstdc++-v3/include/bits/deque.tcc
>>> @@ -507,6 +507,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>>       _M_push_back_aux(const value_type& __t)
>>> #endif
>>>       {
>>> +    if (empty())
>>> +      {
>>> +        // Move iterators to point to the current node begin.
>>> +        this->_M_impl._M_start._M_cur = 
>>> this->_M_impl._M_start._M_first;
>>> +        this->_M_impl._M_finish._M_cur = 
>>> this->_M_impl._M_finish._M_first;
>>> +#if __cplusplus >= 201103L
>>> +        emplace_back(std::forward<_Args>(__args)...);
>>> +#else
>>> +        push_back(__t);
>>> +#endif
>>> +        return;
>>> +      }
>>> +
>>>     if (size() == max_size())
>>>       __throw_length_error(
>>>           __N("cannot create std::deque larger than max_size()"));
>>> @@ -546,6 +559,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>>       _M_push_front_aux(const value_type& __t)
>>> #endif
>>>       {
>>> +    if (empty())
>>> +      {
>>> +        // Move iterators to point to the current node end.
>>> +        this->_M_impl._M_finish._M_cur = 
>>> this->_M_impl._M_finish._M_last - 1;
>>> +        this->_M_impl._M_start._M_cur = 
>>> this->_M_impl._M_start._M_last - 1;
>>> +#if __cplusplus >= 201103L
>>> +        emplace_front(std::forward<_Args>(__args)...);
>>> +#else
>>> +        push_front(__t);
>>> +#endif
>>> +        return;
>>> +      }
>>> +
>>>     if (size() == max_size())
>>>       __throw_length_error(
>>>           __N("cannot create std::deque larger than max_size()"));
>>
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: deque_reuse_node.patch
Type: text/x-patch
Size: 1422 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200630/4413b19d/attachment.bin>