Deque rotate on current node

Message ID 2a947ca5-56ea-cd46-f4bb-c094fa980745@gmail.com
State New
Headers show
Series
  • Deque rotate on current node
Related show

Commit Message

François Dumont May 20, 2019, 5:39 a.m.
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

Comments

François Dumont Jan. 17, 2020, 5:52 a.m. | #1
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

>
Jonathan Wakely Jan. 17, 2020, 10:01 a.m. | #2
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()"));

Patch

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