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