Deque::fill (was: Re: Deque...)

[Paolo Carlini <pcarlini at suse dot de>]

Hi Howard,

> *  We call std::copy a lot internally (with deque::iterators as the 
> output range, or both input and output).  We need to specialize 
> (overload) std::copy to work nicely with deque::iterator (the 
> segmented iterator optimization).    Same goes for the other 
> std::algorithms we call.

as you know already I'm working also on this nice suggestion of yours.

A low hanging fruit seems fill, which actually is used quite a bit, and
the below is what I currently have, how does it look? Of course, copy is
going to be more important, but is also much more tricky... ;)

Performance-wise, on simple stuff like

  deque<int> d(10000, 1);
  for (int j = 0; j < 100; ++j)
    for (deque<int>::size_type i = 0; i < 10000; ++i)
      d.assign(i, 3);

timings go down from ~7.3 secs -> ~5.4 secs on P4-2400. We improve much
more if the underlying fill on plain pointers uses memset (e.g, chars),
down to ~2.2 secs.

Paolo.

/////////////////

Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h	(revision 108409)
+++ include/bits/stl_algobase.h	(working copy)
@@ -688,6 +688,30 @@
     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
   }
 
+  template<typename _Tp, typename _Ref, typename _Ptr>
+    struct _Deque_iterator;
+
+  template<typename _Tp, typename _Ref, typename _Ptr>
+    void
+    fill(const _Deque_iterator<_Tp, _Ref, _Ptr>& __first,
+	 const _Deque_iterator<_Tp, _Ref, _Ptr>& __last, const _Tp& __value)
+    {
+      typedef typename _Deque_iterator<_Tp, _Ref, _Ptr>::_Self _Self;
+
+      for (typename _Self::_Map_pointer __node = __first._M_node + 1;
+           __node < __last._M_node; ++__node)
+	std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
+
+      if (__first._M_node != __last._M_node)
+	{
+	  std::fill(__first._M_cur, __first._M_last, __value);
+	  std::fill(__last._M_first, __last._M_cur, __value);
+	}
+      else
+	std::fill(__first._M_cur, __last._M_cur, __value);
+    }
+
+
   template<bool>
     struct __fill_n
     {
Index: testsuite/23_containers/deque/cons/assign/1.cc
===================================================================
--- testsuite/23_containers/deque/cons/assign/1.cc	(revision 0)
+++ testsuite/23_containers/deque/cons/assign/1.cc	(revision 0)
@@ -0,0 +1,51 @@
+// 2005-12-12  Paolo Carlini  <pcarlini@suse.de>
+//
+// Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// 23.2.1.1 deque constructors, copy, and assignment
+
+#include <deque>
+#include <testsuite_hooks.h>
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+  using namespace std;
+
+  int data3[10000];
+  fill(data3, data3 + 10000, 3);
+
+  int data5[10000];
+  fill(data5, data5 + 10000, 5);
+
+  for (deque<int>::size_type i = 0; i < 10000; ++i)
+    {
+      deque<int> d(rand() % 5000, 1);
+      d.assign(i, i % 2 ? 3 : 5);
+
+      VERIFY( d.size() == i );
+      VERIFY( equal(d.begin(), d.end(), i % 2 ? data3 : data5) );
+    }
+}
+
+int main()
+{
+  test01();
+  return 0;
+}