On 29/06/2016 23:30, Jonathan Wakely wrote:
On 29/06/16 21:36 +0100, Jonathan Wakely wrote:
On 29/06/16 21:43 +0200, François Dumont wrote:
As asked here is now a patch to only fix the robustness issue. The
consequence is that it is reverting the latest optimization as,
without smart algo, we always need to do a copy to protect against
insertion of values contained in the vector as shown by new tests.
I don't understand. There is no problem with insert(), only with
emplace(), so why do both get worse?
Also, the problem is with emplacing from an lvalue, so why do the
number of operations change for test02 and test03, which are for
xvalues and rvalues?
I haven't analyzed your patch, but the results seem wrong. We should
not have to do any more work to insert rvalues.
What am I missing?
It seems to me that the minimal fix would be:
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -312,7 +312,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
else
_M_insert_aux(begin() + (__position - cbegin()),
- std::forward<_Args>(__args)...);
+ _Tp(std::forward<_Args>(__args)...));
return iterator(this->_M_impl._M_start + __n);
}
This causes regressions in the insert_vs_emplace.cc test because we
insert rvalues using emplace:
This is also why my patch is impacting insert from xvalue or rvalue.
iterator
insert(const_iterator __position, value_type&& __x)
{ return emplace(__position, std::move(__x)); }
That's suboptimal, since in the general case we need an extra
construction for emplacing, but we know that we don't need to do that
when inserting rvalues.
Why not ? I realized with your remarks that I was missing some
tests in the new self_insert.cc. The ones to insert an rvalue coming
from the vector itself. In the attached patch there is those 2 tests, do
you agree with expected behavior ? For the moment it doesn't check that
the source value has been indeed moved cause it doesn't, I will update
it once it does.
My patch also reorganize a little bit code to avoid redundant
checks to find out if reallocation is necessary or not. I was also
thinking about reusing _M_realloc_insert_aux within _M_fill_insert when
reallocation is needed.
So the correct fix would be to implement inserting rvalues without
using emplace.
The attached patch is a smaller change, and doesn't change the number
of operations for insertions, only for emplacing lvalues.
Ok, go ahead, I will try to rebase mine from yours.
François
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..c37880a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#if __cplusplus >= 201103L
_M_emplace_back_aux(__x);
#else
- _M_insert_aux(end(), __x);
+ _M_realloc_insert_aux(end(), __x);
#endif
}
@@ -1435,21 +1435,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#if __cplusplus < 201103L
void
_M_insert_aux(iterator __position, const value_type& __x);
-#else
- template<typename... _Args>
- static void
- _S_insert_aux_assign(iterator __pos, _Args&&... __args)
- { *__pos = _Tp(std::forward<_Args>(__args)...); }
-
- static void
- _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
- { *__pos = std::move(__arg); }
+ void
+ _M_realloc_insert_aux(iterator __position, const value_type& __x);
+#else
template<typename... _Args>
void
_M_insert_aux(iterator __position, _Args&&... __args);
template<typename... _Args>
+ void
+ _M_realloc_insert_aux(iterator __position, _Args&&... __args);
+
+ template<typename... _Args>
void
_M_emplace_back_aux(_Args&&... __args);
#endif
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 604be7b..9061593 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -112,27 +112,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#endif
{
const size_type __n = __position - begin();
- if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
- && __position == end())
- {
- _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
- ++this->_M_impl._M_finish;
- }
+ if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+ if (__position == end())
+ {
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+ ++this->_M_impl._M_finish;
+ }
+ else
+#if __cplusplus >= 201103L
+ _M_insert_aux(begin() + (__position - cbegin()), __x);
+#else
+ _M_insert_aux(__position, __x);
+#endif
else
- {
#if __cplusplus >= 201103L
- const auto __pos = begin() + (__position - cbegin());
- if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
- {
- _Tp __x_copy = __x;
- _M_insert_aux(__pos, std::move(__x_copy));
- }
- else
- _M_insert_aux(__pos, __x);
+ _M_realloc_insert_aux(begin() + (__position - cbegin()), __x);
#else
- _M_insert_aux(__position, __x);
+ _M_realloc_insert_aux(__position, __x);
#endif
- }
+
return iterator(this->_M_impl._M_start + __n);
}
@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
emplace(const_iterator __position, _Args&&... __args)
{
const size_type __n = __position - begin();
- if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
- && __position == end())
- {
- _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
- std::forward<_Args>(__args)...);
- ++this->_M_impl._M_finish;
- }
+ if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+ if (__position == end())
+ {
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ std::forward<_Args>(__args)...);
+ ++this->_M_impl._M_finish;
+ }
+ else
+ _M_insert_aux(begin() + (__position - cbegin()),
+ std::forward<_Args>(__args)...);
else
- _M_insert_aux(begin() + (__position - cbegin()),
- std::forward<_Args>(__args)...);
+ _M_realloc_insert_aux(begin() + (__position - cbegin()),
+ std::forward<_Args>(__args)...);
+
return iterator(this->_M_impl._M_start + __n);
}
@@ -327,78 +329,86 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
vector<_Tp, _Alloc>::
_M_insert_aux(iterator __position, const _Tp& __x)
#endif
- {
- if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
- {
- _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
- _GLIBCXX_MOVE(*(this->_M_impl._M_finish
- - 1)));
- ++this->_M_impl._M_finish;
-#if __cplusplus < 201103L
- _Tp __x_copy = __x;
+ {
+#if __cplusplus >= 201103L
+ _Tp __x_copy(std::forward<_Args>(__args)...);
+#else
+ _Tp __x_copy(__x);
#endif
- _GLIBCXX_MOVE_BACKWARD3(__position.base(),
- this->_M_impl._M_finish - 2,
- this->_M_impl._M_finish - 1);
-#if __cplusplus < 201103L
- *__position = __x_copy;
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+ ++this->_M_impl._M_finish;
+
+ _GLIBCXX_MOVE_BACKWARD3(__position.base(),
+ this->_M_impl._M_finish - 2,
+ this->_M_impl._M_finish - 1);
+
+ *__position = _GLIBCXX_MOVE(__x_copy);
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _Alloc>
+ template<typename... _Args>
+ void
+ vector<_Tp, _Alloc>::
+ _M_realloc_insert_aux(iterator __position, _Args&&... __args)
#else
- _S_insert_aux_assign(__position, std::forward<_Args>(__args)...);
+ template<typename _Tp, typename _Alloc>
+ void
+ vector<_Tp, _Alloc>::
+ _M_realloc_insert_aux(iterator __position, const _Tp& __x)
#endif
- }
- else
+ {
+ const size_type __len =
+ _M_check_len(size_type(1), "vector::_M_realloc_insert_aux");
+ const size_type __elems_before = __position - begin();
+ pointer __new_start(this->_M_allocate(__len));
+ pointer __new_finish(__new_start);
+ __try
{
- const size_type __len =
- _M_check_len(size_type(1), "vector::_M_insert_aux");
- const size_type __elems_before = __position - begin();
- pointer __new_start(this->_M_allocate(__len));
- pointer __new_finish(__new_start);
- __try
- {
- // The order of the three operations is dictated by the C++0x
- // case, where the moves could alter a new element belonging
- // to the existing vector. This is an issue only for callers
- // taking the element by const lvalue ref (see 23.1/13).
- _Alloc_traits::construct(this->_M_impl,
- __new_start + __elems_before,
+ // The order of the three operations is dictated by the C++0x
+ // case, where the moves could alter a new element belonging
+ // to the existing vector. This is an issue only for callers
+ // taking the element by const lvalue ref (see 23.1/13).
+ _Alloc_traits::construct(this->_M_impl,
+ __new_start + __elems_before,
#if __cplusplus >= 201103L
- std::forward<_Args>(__args)...);
+ std::forward<_Args>(__args)...);
#else
- __x);
+ __x);
#endif
- __new_finish = pointer();
+ __new_finish = pointer();
- __new_finish
- = std::__uninitialized_move_if_noexcept_a
- (this->_M_impl._M_start, __position.base(),
- __new_start, _M_get_Tp_allocator());
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (this->_M_impl._M_start, __position.base(),
+ __new_start, _M_get_Tp_allocator());
- ++__new_finish;
+ ++__new_finish;
- __new_finish
- = std::__uninitialized_move_if_noexcept_a
- (__position.base(), this->_M_impl._M_finish,
- __new_finish, _M_get_Tp_allocator());
- }
- __catch(...)
- {
- if (!__new_finish)
- _Alloc_traits::destroy(this->_M_impl,
- __new_start + __elems_before);
- else
- std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
- _M_deallocate(__new_start, __len);
- __throw_exception_again;
- }
- std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
- _M_get_Tp_allocator());
- _M_deallocate(this->_M_impl._M_start,
- this->_M_impl._M_end_of_storage
- - this->_M_impl._M_start);
- this->_M_impl._M_start = __new_start;
- this->_M_impl._M_finish = __new_finish;
- this->_M_impl._M_end_of_storage = __new_start + __len;
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (__position.base(), this->_M_impl._M_finish,
+ __new_finish, _M_get_Tp_allocator());
+ }
+ __catch(...)
+ {
+ if (!__new_finish)
+ _Alloc_traits::destroy(this->_M_impl,
+ __new_start + __elems_before);
+ else
+ std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
+ _M_deallocate(__new_start, __len);
+ __throw_exception_again;
}
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __new_start;
+ this->_M_impl._M_finish = __new_finish;
+ this->_M_impl._M_end_of_storage = __new_start + __len;
}
#if __cplusplus >= 201103L
@@ -493,7 +503,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
pointer __new_finish(__new_start);
__try
{
- // See _M_insert_aux above.
+ // See _M_realloc_insert_aux above.
std::__uninitialized_fill_n_a(__new_start + __elems_before,
__n, __x,
_M_get_Tp_allocator());
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 0000000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 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 <vector>
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+ std::vector<std::vector<int>> vv =
+ {
+ { 2, 3 },
+ { 4, 5 },
+ { 0, 1 }
+ };
+
+ // Make sure emplace will imply reallocation.
+ VERIFY( vv.capacity() == 3 );
+
+ vv.emplace(vv.begin(), vv[0]);
+
+ VERIFY( vv.size() == 4 );
+ VERIFY( vv[0].size() == 2 );
+ VERIFY( vv[0][0] == 2 );
+ VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+ std::vector<std::vector<int>> vv =
+ {
+ { 2, 3 },
+ { 4, 5 },
+ { 0, 1 }
+ };
+
+ // Make sure emplace won't reallocate.
+ vv.reserve(4);
+ vv.emplace(vv.begin(), vv[0]);
+
+ VERIFY( vv.size() == 4 );
+ VERIFY( vv[0].size() == 2 );
+ VERIFY( vv[0][0] == 2 );
+ VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+ A(int i) : _i(i)
+ { }
+
+ A(const A& other) : _i(other._i)
+ {
+ VERIFY( other._i >= 0 );
+ }
+
+ A(A&& other) : _i(other._i)
+ {
+ VERIFY( other._i >= 0 );
+
+ other._i = -1;
+ }
+
+ A(std::vector<A>::iterator it) : _i(it->_i)
+ {
+ VERIFY( it->_i >= 0 );
+ }
+
+ A& operator=(const A&) = default;
+ A& operator=(A&& other)
+ {
+ VERIFY(other._i >= 0 );
+
+ _i = other._i;
+ other._i = -1;
+ return *this;
+ }
+
+ int _i;
+};
+
+void
+test03()
+{
+ std::vector<A> va =
+ {
+ { A(1) },
+ { A(2) },
+ { A(3) }
+ };
+
+ // Make sure emplace will imply reallocation.
+ VERIFY( va.capacity() == 3 );
+
+ va.emplace(va.begin(), va.begin());
+
+ VERIFY( va.size() == 4 );
+ VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+ std::vector<A> va =
+ {
+ { A(1) },
+ { A(2) },
+ { A(3) }
+ };
+
+ // Make sure emplace won't reallocate.
+ va.reserve(4);
+ va.emplace(va.begin(), va.begin());
+
+ VERIFY( va.size() == 4 );
+ VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
new file mode 100644
index 0000000..7e2f9e2
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -0,0 +1,113 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 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 <vector>
+
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+ std::vector<std::vector<int>> vv =
+ {
+ { 2, 3 },
+ { 4, 5 },
+ { 0, 1 }
+ };
+
+ // Make sure it doesn't reallocate during insertion.
+ vv.reserve(4);
+
+ vv.insert(vv.begin(), vv[0]);
+
+ VERIFY( vv.size() == 4 );
+ VERIFY( vv[0].size() == 2 );
+ VERIFY( vv[0][0] == 2 );
+ VERIFY( vv[0][1] == 3 );
+}
+
+void test02()
+{
+ std::vector<std::vector<int>> vv =
+ {
+ { 2, 3 },
+ { 4, 5 },
+ { 0, 1 }
+ };
+
+ // Make sure we will reallocate for insertion.
+ VERIFY( vv.capacity() == 3 );
+
+ vv.insert(vv.begin(), vv[0]);
+
+ VERIFY( vv.size() == 4 );
+ VERIFY( vv[0].size() == 2 );
+ VERIFY( vv[0][0] == 2 );
+ VERIFY( vv[0][1] == 3 );
+}
+
+
+void test03()
+{
+ std::vector<std::vector<int>> vv =
+ {
+ { 2, 3 },
+ { 4, 5 },
+ { 0, 1 }
+ };
+
+ // Make sure it doesn't reallocate during insertion.
+ vv.reserve(4);
+
+ vv.insert(vv.begin(), std::move(vv[0]));
+
+ VERIFY( vv.size() == 4 );
+ VERIFY( vv[0].size() == 2 );
+ VERIFY( vv[0][0] == 2 );
+ VERIFY( vv[0][1] == 3 );
+}
+
+void test04()
+{
+ std::vector<std::vector<int>> vv =
+ {
+ { 2, 3 },
+ { 4, 5 },
+ { 0, 1 }
+ };
+
+ // Make sure we will reallocate for insertion.
+ VERIFY( vv.capacity() == 3 );
+
+ vv.insert(vv.begin(), std::move(vv[0]));
+
+ VERIFY( vv.size() == 4 );
+ VERIFY( vv[0].size() == 2 );
+ VERIFY( vv[0][0] == 2 );
+ VERIFY( vv[0][1] == 3 );
+}
+
+int main()
+{
+ test01();
+ test02();
+ test03();
+ test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..8bd72b7 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -149,7 +149,7 @@ test01()
void
test02()
{
- const X::special expected{ 0, 0, 0, 0, 1, 3 };
+ const X::special expected{ 0, 1, 0, 0, 2, 3 };
X::special ins, emp;
{
std::vector<X> v;
@@ -187,7 +187,7 @@ test02()
void
test03()
{
- const X::special expected{ 1, 1, 0, 0, 1, 3 };
+ const X::special expected{ 1, 2, 0, 0, 2, 3 };
X::special ins, emp;
{
std::vector<X> v;
