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
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;
+}
