Deque rotate on current node

[François Dumont]

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()"));
>