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