From: "François Dumont" <frs.dumont@gmail.com>
To: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>,
gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Deque rotate on current node
Date: Mon, 20 May 2019 05:39:00 -0000 [thread overview]
Message-ID: <2a947ca5-56ea-cd46-f4bb-c094fa980745@gmail.com> (raw)
[-- 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()"));
next reply other threads:[~2019-05-20 5:39 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-05-20 5:39 François Dumont [this message]
2020-01-17 10:02 ` François Dumont
2020-01-17 17:04 ` Jonathan Wakely
2020-01-18 12:54 ` François Dumont
2020-06-30 20:33 ` François Dumont
2020-09-01 12:06 ` François Dumont
2020-09-01 13:25 ` Jonathan Wakely
2020-09-02 17:40 ` François Dumont
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=2a947ca5-56ea-cd46-f4bb-c094fa980745@gmail.com \
--to=frs.dumont@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).