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.)
