Re: Improve insert/emplace robustness to self insertion

[FranÃois Dumont <frs dot dumont at gmail dot com>]

On 01/07/2016 11:54, Jonathan Wakely wrote:
> On 30/06/16 21:51 +0200, FranÃois Dumont wrote:
> > On 29/06/2016 23:30, Jonathan Wakely wrote:
> > >     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.
>
> No, I don't agree, because this is undefined behaviour:
>
>   vv.insert(vv.begin(), std::move(vv[0]));
>
> We don't need to support that case.

Ok but management of this kind of code is a nice consequence of using 
the smart insertion trick.

> 17.6.4.9 [res.on.arguments] says:
>
> â If a function argument binds to an rvalue reference parameter, the
>  implementation may assume that this parameter is a unique reference
>  to this argument.
>
> i.e. when passed an rvalue we can assume it is not a reference to
> something in the container.
>
> That's why we should not perform any more operations when inserting
> rvalues than we do now. Any increase in copies/moves for inserting
> rvalues is a regression, and should be avoided

Agree so in attached patch I have implemented the smart insertion trick 
to come back to optimal copies/moves. We don't need to do much to do 
better than Standard requirement and especially not additional copies/moves.

I haven't consider in this patch your remark about using allocator to 
build instance so don't hesitate to commit what you want and I will rebase.

FranÃois

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index c37880a..d7435cc 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -1432,17 +1432,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 
       // Called by insert(p,x)
+      void
+      _M_insert_aux(iterator __position, const value_type& __x)
+      { _M_insert_value_aux(__position, __x); }
+
 #if __cplusplus < 201103L
       void
-      _M_insert_aux(iterator __position, const value_type& __x);
+      _M_insert_value_aux(iterator __position, const value_type& __x);
 
       void
       _M_realloc_insert_aux(iterator __position, const value_type& __x);
 #else
+      template<typename _Val>
+        void
+        _M_insert_value_aux(iterator __position, _Val&& __x);
+
       template<typename... _Args>
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
+      void
+      _M_insert_aux(iterator __position, value_type& __x)
+      { _M_insert_value_aux(__position, __x); }
+
+      void
+      _M_insert_aux(iterator __position, value_type&& __x)
+      { _M_insert_value_aux(__position, std::move(__x)); }
+
       template<typename... _Args>
         void
         _M_realloc_insert_aux(iterator __position, _Args&&... __args);
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9061593..fe57db2 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -56,6 +56,8 @@
 #ifndef _VECTOR_TCC
 #define _VECTOR_TCC 1
 
+#include <bits/stl_function.h> // For std::less.
+
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
@@ -120,9 +122,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  }
 	else
 #if __cplusplus >= 201103L
-	  _M_insert_aux(begin() + (__position - cbegin()), __x);
+	  _M_insert_value_aux(begin() + (__position - cbegin()), __x);
 #else
-	  _M_insert_aux(__position, __x);
+	  _M_insert_value_aux(__position, __x);
 #endif
       else
 #if __cplusplus >= 201103L
@@ -323,28 +325,46 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       void
       vector<_Tp, _Alloc>::
       _M_insert_aux(iterator __position, _Args&&... __args)
+      {
+	_Tp __x_copy(std::forward<_Args>(__args)...);
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				 std::move(*(this->_M_impl._M_finish - 1)));
+	std::move_backward(__position.base(), this->_M_impl._M_finish - 1,
+			   this->_M_impl._M_finish);
+
+	++this->_M_impl._M_finish;
+
+	*__position = std::move(__x_copy);
+      }
+
+  template<typename _Tp, typename _Alloc>
+    template<typename _Val>
+      void
+      vector<_Tp, _Alloc>::
+      _M_insert_value_aux(iterator __position, _Val&& __x)
 #else
   template<typename _Tp, typename _Alloc>
     void
     vector<_Tp, _Alloc>::
-    _M_insert_aux(iterator __position, const _Tp& __x)
+    _M_insert_value_aux(iterator __position, const _Tp& __x)
 #endif
-      {
-#if __cplusplus >= 201103L
-	_Tp __x_copy(std::forward<_Args>(__args)...);
-#else
-	_Tp __x_copy(__x);
-#endif
-	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				 _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
-	++this->_M_impl._M_finish;
+    {
+      __decltype(std::__addressof(__x)) __ptr = std::__addressof(__x);
+      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+			       _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+      _GLIBCXX_MOVE_BACKWARD3(__position.base(), 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);
+      ++this->_M_impl._M_finish;
 
-	*__position = _GLIBCXX_MOVE(__x_copy);
-      }
+      typedef std::less<const _Tp*> _Less;
+      _GLIBCXX_USE_CONSTEXPR _Less __l{};
+      if (!__l(__ptr, _M_data_ptr(__position.base()))
+	  && !__l(_M_data_ptr(this->_M_impl._M_finish - 1), __ptr))
+	++__ptr;
+
+      *__position = _GLIBCXX_FORWARD(_Val, *__ptr);
+    }
 
 #if __cplusplus >= 201103L
   template<typename _Tp, typename _Alloc>
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
index d452b5b..196d1c0 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -63,6 +63,51 @@ test02()
   VERIFY( vv[0][1] == 3 );
 }
 
+void
+test03()
+{
+  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(), std::move(vv[0]));
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].empty() );
+}
+
+void
+test04()
+{
+  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(), std::move(vv[0]));
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].empty() );
+}
+
 struct A
 {
   A(int i) : _i(i)
@@ -99,7 +144,7 @@ struct A
 };
 
 void
-test03()
+test05()
 {
   std::vector<A> va =
     {
@@ -118,7 +163,7 @@ test03()
 }
 
 void
-test04()
+test06()
 {
   std::vector<A> va =
     {
@@ -141,4 +186,6 @@ int main()
   test02();
   test03();
   test04();
+  test05();
+  test06();
 }
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
index 7e2f9e2..a70d621 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -41,6 +41,8 @@ void test01()
   VERIFY( vv[0].size() == 2 );
   VERIFY( vv[0][0] == 2 );
   VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].size() == 2 );
 }
 
 void test02()
@@ -61,6 +63,8 @@ void test02()
   VERIFY( vv[0].size() == 2 );
   VERIFY( vv[0][0] == 2 );
   VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].size() == 2 );
 }
 
 
@@ -82,6 +86,8 @@ void test03()
   VERIFY( vv[0].size() == 2 );
   VERIFY( vv[0][0] == 2 );
   VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].empty() );
 }
 
 void test04()
@@ -102,6 +108,8 @@ void test04()
   VERIFY( vv[0].size() == 2 );
   VERIFY( vv[0][0] == 2 );
   VERIFY( vv[0][1] == 3 );
+
+  VERIFY( vv[1].empty() );
 }
 
 int main()
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 8bd72b7..4c9c57e 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
@@ -111,7 +111,7 @@ operator==(const X::special& lhs, const X::special& rhs)
 void
 test01()
 {
-  const X::special expected{ 0, 1, 1, 0, 1, 3 };
+  const X::special expected{ 0, 0, 0, 1, 1, 2 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -149,7 +149,7 @@ test01()
 void
 test02()
 {
-  const X::special expected{ 0, 1, 0, 0, 2, 3 };
+  const X::special expected{ 0, 0, 0, 0, 1, 3 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -187,7 +187,7 @@ test02()
 void
 test03()
 {
-  const X::special expected{ 1, 2, 0, 0, 2, 3 };
+  const X::special expected{ 1, 1, 0, 0, 1, 3 };
   X::special ins, emp;
   {
     std::vector<X> v;