Keep std::deque algos specializations in Debug mode

[Jonathan Wakely]

On 25/08/18 22:44 +0200, François Dumont wrote:
>The last optimizations that get disabled when Debug mode is enable are 
>the algo specializations for std::deque iterators.
>
>This patch move those algos in std namespace as they should even when 
>Debug mode is enable so that they get considered even when calls are 
>made with the namespace qualification. And it adds all the algos Debug 
>implementations which forward to normal implementations to benefit 
>from optimizations.
>
>Note that I try to use typename deque<>::iterator or typename 
>deque<>::const_iterator to define Debug algos but it didn't work, gcc 
>was just not considering those overloads. I wonder why ?
>
>I added test and manually checked that behavior was correct. Do you 
>see a way to automate this validation ?
>
>François
>

>diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
>index 125bcffb0c3..2a3f23a8588 100644
>--- a/libstdc++-v3/include/bits/deque.tcc
>+++ b/libstdc++-v3/include/bits/deque.tcc
>@@ -980,22 +980,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
>     }
> 
>+_GLIBCXX_END_NAMESPACE_CONTAINER
>+
>   // Overload for deque::iterators, exploiting the "segmented-iterator
>   // optimization".
>   template<typename _Tp>
>     void
>-    fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
>-	 const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value)
>+    fill(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
>+	 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
>+	 const _Tp& __value)
>     {
>-      typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_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);
>+      typedef typename _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>::_Self
>+	_Self;
> 
>       if (__first._M_node != __last._M_node)
> 	{
> 	  std::fill(__first._M_cur, __first._M_last, __value);
>+
>+	  for (typename _Self::_Map_pointer __node = __first._M_node + 1;
>+	       __node != __last._M_node; ++__node)

Is there any particular reason to change this from using < to != for
the comparison?

(This change is part of the reason I asked for the ChangeLog, but you
didn't mention it in the ChangeLog).

Moving it inside the condition makes sense (not only does it avoid a
branch in the single-page case, but means we fill the elements in
order).


>+	    std::fill(*__node, *__node + _Self::_S_buffer_size(), __value);
>+
> 	  std::fill(__last._M_first, __last._M_cur, __value);
> 	}
>       else

The rest of the code changes look fine, I just wondered about that
bit.

I do have some comments on the new tests though ...



>diff --git a/libstdc++-v3/testsuite/23_containers/deque/copy.cc b/libstdc++-v3/testsuite/23_containers/deque/copy.cc
>new file mode 100644
>index 00000000000..9171200bc20
>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/deque/copy.cc
>@@ -0,0 +1,56 @@
>+// Copyright (C) 2018 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 <limits>
>+#include <algorithm>
>+#include <deque>
>+
>+#include <testsuite_hooks.h>
>+
>+void test01()
>+{
>+  std::deque<char> d;
>+  for (char c = 0; c != std::numeric_limits<char>::max(); ++c)
>+    d.push_back(c);
>+
>+  std::deque<char> dest(std::numeric_limits<char>::max(), '\0');

These deques only have 127 or 255 elements (depending on
is_signed<char>) which will fit on a single page of a deque (the
default is 512 bytes per page).

That means the tests don't exercise the logic for handling
non-contiguous blocks of memory.

Ideally we'd want to test multiple cases:

- a single page, with/without empty capacity at front/back
- multiple pages, with/without empty capacity at front/back

That would be 8 cases. I think we want to test at least a single
page and multiple pages.

>--- /dev/null
>+++ b/libstdc++-v3/testsuite/23_containers/deque/fill.cc
>@@ -0,0 +1,35 @@
>+// Copyright (C) 2018 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 <limits>
>+#include <algorithm>
>+#include <deque>
>+
>+#include <testsuite_hooks.h>
>+
>+int main()
>+{
>+  std::deque<char> d;
>+  for (char c = 1; c != std::numeric_limits<char>::max(); ++c)
>+    d.push_back(c);
>+
>+  std::fill(d.begin(), d.end(), '\0');
>+
>+  VERIFY( d.front() == '\0' );
>+  VERIFY( d.back() == '\0' );

That doesn't check that the middle of the deque was filled, which
would matter if it had multiple pages. How about checking there are no
non-zero elements?

VERIFY( std::find_if(d.begin(), d.end(),
                     std::bind1st(std::equal_to<bool>(), true)) == d.end() )

(That would be easier in C++11, but we want these tests to be able to
run for C++98 too.)