The PR shows a fairly pathological case where ranges of InputIterators
are repeatedly inserted at the start of a vector. Each insertion from
an InputIterator moves every element after the insertion point by a
single position. So if we insert 1000 elements at the start we move
each existing element 1000 times to reach its final position.
This patch changes insertions that aren't at the end to use a
temporary vector, which starts empty so insertions are at the end, and
so fast. Then we do a range insert to copy everything from that vector
at once. That uses random access iterators, so we know how far to move
the existing elements and can just move them to their final position
in one step.
There are other possible strategies, such as inserting the input range
at the end of *this and then rotating them into place once we have
inserted them all. However, when the insertions trigger a reallocation
we need to transfer all the existing elements (not only those past the
insertion point). The patch I've committed only has to move the
existing elements if the final insertion from the temporary vector to
*this causes a reallocation.
PR libstdc++/81476
* include/bits/vector.tcc (vector::_M_range_insert<_InputIterator>):
Only insert elements one-by-one when inserting at the end.
* testsuite/performance/23_containers/insert/81476.cc: New.
Tested x86_64-linux, committed to trunk.
commit f3f49ca32aa56e2e417e611f1cd9f9deccb63bb5
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Wed Jul 19 20:06:24 2017 +0100
PR libstdc++/81476 Optimise vector insertion from input iterators
PR libstdc++/81476
* include/bits/vector.tcc (vector::_M_range_insert<_InputIterator>):
Only insert elements one-by-one when inserting at the end.
* testsuite/performance/23_containers/insert/81476.cc: New.
diff --git a/libstdc++-v3/include/bits/vector.tcc
b/libstdc++-v3/include/bits/vector.tcc
index 8d68866..da4a64c 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -617,10 +617,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
_M_range_insert(iterator __pos, _InputIterator __first,
_InputIterator __last, std::input_iterator_tag)
{
- for (; __first != __last; ++__first)
+ if (__pos == end())
{
- __pos = insert(__pos, *__first);
- ++__pos;
+ for (; __first != __last; ++__first)
+ insert(end(), *__first);
+ }
+ else if (__first != __last)
+ {
+ vector __tmp(__first, __last, _M_get_Tp_allocator());
+ insert(__pos,
+ _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
+ _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
}
}
diff --git a/libstdc++-v3/testsuite/performance/23_containers/insert/81476.cc
b/libstdc++-v3/testsuite/performance/23_containers/insert/81476.cc
new file mode 100644
index 0000000..2b76469
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/insert/81476.cc
@@ -0,0 +1,86 @@
+// Copyright (C) 2012-2017 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/>.
+
+// { dg-do run { target c++11 } }
+
+#include <random>
+#include <vector>
+#include <testsuite_hooks.h>
+#include <testsuite_performance.h>
+
+int main()
+{
+ using namespace __gnu_test;
+
+ std::default_random_engine eng;
+ std::uniform_int_distribution<unsigned> r(0, 127);
+
+ time_counter time;
+ resource_counter resource;
+
+ std::vector<std::vector<char>> vecs(10000);
+ for (auto& v : vecs)
+ {
+ v.resize(1000);
+ for (auto& c : v)
+ c = r(eng);
+ }
+
+ start_counters(time, resource);
+ std::vector<char> res;
+ for (auto& v : vecs)
+ res.insert(res.begin(), v.begin(), v.end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "insert pointers", time, resource);
+
+ struct input_iterator : std::vector<char>::iterator
+ {
+ using iterator_category = std::input_iterator_tag;
+ using base = std::vector<char>::iterator;
+
+ input_iterator(base it) : base(it) { }
+ };
+
+ start_counters(time, resource);
+ std::vector<char> res2;
+ for (auto& v : vecs)
+ {
+ auto begin = input_iterator(v.begin());
+ auto end = input_iterator(v.end());
+ res2.insert(res2.begin(), begin, end);
+ }
+ stop_counters(time, resource);
+ report_performance(__FILE__, "insert input iterators", time, resource);
+
+ start_counters(time, resource);
+ std::vector<char> res3;
+ for (auto rev = vecs.rbegin(); rev != vecs.rend(); ++rev)
+ res3.insert(res3.end(), rev->begin(), rev->end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "insert pointers end", time, resource);
+
+ start_counters(time, resource);
+ std::vector<char> res4;
+ for (auto rev = vecs.rbegin(); rev != vecs.rend(); ++rev)
+ res4.insert(res4.end(), rev->begin(), rev->end());
+ stop_counters(time, resource);
+ report_performance(__FILE__, "insert input iterators end", time, resource);
+
+ VERIFY(res2 == res);
+ VERIFY(res3 == res);
+ VERIFY(res4 == res);
+}
