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