Deque rotate on current node

Deque rotate on current node

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 1195 bytes --]

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.

     * 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


[-- Attachment #2: deque_rotate.patch --]
[-- Type: text/x-patch, Size: 1422 bytes --]

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

Re: Deque rotate on current node

[François Dumont]

After the recent optimization that went in despite in stage 4 I wonder 
why I never got any feedback for this one.

https://gcc.gnu.org/ml/libstdc++/2019-05/msg00166.html

I forgot to note that this is the simplest reply to an old Paolo's 
request to recycle std::deque's "nodes". And this one is abi compatible !

François

On 5/20/19 7:39 AM, 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.
>
>     * 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
>

Re: Deque rotate on current node

[Jonathan Wakely]

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?

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

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

Re: Deque rotate on current node

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 4661 bytes --]

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


[-- Attachment #2: deque_reuse_node.patch --]
[-- Type: text/x-patch, Size: 1422 bytes --]

diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 7d1ec86456a..e0fb7f07bc4 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -486,6 +486,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()"));
@@ -525,6 +538,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()"));

Re: Deque rotate on current node

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 4889 bytes --]

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


[-- Attachment #2: deque_reuse_node.patch --]
[-- Type: text/x-patch, Size: 1422 bytes --]

diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 7d1ec86456a..e0fb7f07bc4 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -486,6 +486,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()"));
@@ -525,6 +538,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()"));

Re: Deque rotate on current node

[Jonathan Wakely]

On 01/09/20 14:06 +0200, François Dumont wrote:
>Hi
>
>No chance to review this small patch ?

I did review it, and I wasn't convinced it was a good change. It only
helps a particular usage pattern, and might hurt in other cases.

I don't agree with your assertion that you use std::deque when you
only use push_front() and you use std::list if you need both
push_front() and push_back().

Ideally we'd keep the most recently reallocated node around for reuse,
and then in the situation you describe the first push_front would
allocate a new node, but if you immediately do pop_back() we wouldn't
deallocate the node. But I haven't figured out a way to do that
caching without an ABI break.

The patch also has no tests. Are our existing tests sufficient to
cover this case? Do we want a test that verifies that we don't
allocate a new node if doing push_front() into an empty deque?

I would like to see a test doing something like:

   std::deque<int, CustomAlloc<int>> d;
   const int count = CustomAlloc::number_of_allocations;
   d.push_front(1);
   VERIFY( CustomAlloc::number_of_allocations == count );
   d.pop_front();
   d.push_back(1);
   VERIFY( CustomAlloc::number_of_allocations == count );

Re: Deque rotate on current node

[François Dumont]

[-- Attachment #1: Type: text/plain, Size: 2406 bytes --]

On 01/09/20 3:25 pm, Jonathan Wakely wrote:
> On 01/09/20 14:06 +0200, François Dumont wrote:
>> Hi
>>
>> No chance to review this small patch ?
>
> I did review it, and I wasn't convinced it was a good change. It only
> helps a particular usage pattern, and might hurt in other cases.

     I shouldn't have illustrate the target of this patch with its 
impact on the use case of an initial push_front. It is clearly not its 
purpose and I agree that it doesn't really improve this use case, it 
doesn't make it worst neither however.


>
> I don't agree with your assertion that you use std::deque when you
> only use push_front() and you use std::list if you need both
> push_front() and push_back().
>
> Ideally we'd keep the most recently reallocated node around for reuse,
> and then in the situation you describe the first push_front would
> allocate a new node, but if you immediately do pop_back() we wouldn't
> deallocate the node. But I haven't figured out a way to do that
> caching without an ABI break.
AFAIR I looked at a solution too and couldn't find any ABI compatible. 
This is why I thought this patch could be a limited answer to this.
>
> The patch also has no tests. Are our existing tests sufficient to
> cover this case? Do we want a test that verifies that we don't
> allocate a new node if doing push_front() into an empty deque?

I initially thought that this patch didn't need any specific test but as 
this patch purpose is performance we could indeed add a performance 
test. This is what I've done in attachment. We can now clearly see the 
impact:

Before:

deque.cc                     push_back/pop_front          1167r 1167u    
0s      528mem    0pf

After:

deque.cc                     push_back/pop_front          1018r 1017u    
0s        0mem    0pf

Some CPU enhancements coming from the limitation on memory usage.

I'll do the same with push_front/pop_back if you eventually validate the 
patch.

But even if the results are great I agree that the conditions to benefit 
from it are limited. You need the deque to be empty when you push_back 
at node past-the-end position to benefit from it.

If you think that this kind of situation is too rare to deserve a 
special piece of code in deque implementation then ok, I won't bother 
you with this proposal anymore.

François



[-- Attachment #2: deque_reuse_node.patch --]
[-- Type: text/x-patch, Size: 3058 bytes --]

diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
index 7d1ec86456a..e0fb7f07bc4 100644
--- a/libstdc++-v3/include/bits/deque.tcc
+++ b/libstdc++-v3/include/bits/deque.tcc
@@ -486,6 +486,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()"));
@@ -525,6 +538,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()"));
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert_erase/deque.cc b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/deque.cc
new file mode 100644
index 00000000000..1eed79d1202
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert_erase/deque.cc
@@ -0,0 +1,45 @@
+// Copyright (C) 2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+
+#include <cassert>
+#include <deque>
+#include <testsuite_performance.h>
+
+int main()
+{
+  using namespace __gnu_test;
+
+  time_counter time;
+  resource_counter resource;
+
+  const int nb = 200000000;
+  std::deque<int> dq;
+
+  start_counters(time, resource);
+  for (int i = 0; i != nb; ++i)
+    {
+      dq.push_back(i);
+      int fval = dq.front();
+      dq.pop_front();
+      assert(fval == i);
+    }
+
+  stop_counters(time, resource);
+  report_performance(__FILE__, "push_back/pop_front", time, resource);
+  return 0;
+}