Re: Deque rotate on current node

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2406 bytes --]

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



[-- Attachment #2: deque_reuse_node.patch --]
[-- Type: text/x-patch, Size: 3058 bytes --]

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