Deque rotate on current node

François Dumont frs.dumont@gmail.com
Tue Sep 1 12:06:08 GMT 2020


Hi

No chance to review this small patch ?

François


On 30/06/20 10:33 pm, François Dumont wrote:
> 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/gcc-patches/attachments/20200901/f0ae4acc/attachment.bin>


More information about the Gcc-patches mailing list