This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Improve insert/emplace robustness to self insertion


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:

     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.

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.


diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..4f43c8e 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -981,6 +981,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       }
 
 #if __cplusplus >= 201103L
+    private:
+      iterator
+      _M_emplace_aux(const_iterator __position, value_type&& __v)
+      { return insert(__position, std::move(__v)); }
+
+      template<typename... _Args>
+	iterator
+	_M_emplace_aux(const_iterator __position, _Args&&... __args)
+	{ return insert(__position, _Tp(std::forward<_Args>(__args)...)); }
+
+    public:
       /**
        *  @brief  Inserts an object in %vector before specified iterator.
        *  @param  __position  A const_iterator into the %vector.
@@ -995,7 +1006,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        */
       template<typename... _Args>
 	iterator
-	emplace(const_iterator __position, _Args&&... __args);
+	emplace(const_iterator __position, _Args&&... __args)
+	{ return _M_emplace_aux(__position, std::forward<_Args>(__args)...); }
 
       /**
        *  @brief  Inserts given value into %vector before specified iterator.
@@ -1039,8 +1051,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  used the user should consider using std::list.
        */
       iterator
-      insert(const_iterator __position, value_type&& __x)
-      { return emplace(__position, std::move(__x)); }
+      insert(const_iterator __position, value_type&& __x);
 
       /**
        *  @brief  Inserts an initializer_list into the %vector.
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 9cb5464..fbcab84 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -297,24 +297,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
 #if __cplusplus >= 201103L
   template<typename _Tp, typename _Alloc>
-    template<typename... _Args>
-      typename vector<_Tp, _Alloc>::iterator
-      vector<_Tp, _Alloc>::
-      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;
-	  }
-	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
-	return iterator(this->_M_impl._M_start + __n);
-      }
+    auto
+    vector<_Tp, _Alloc>::
+    insert(const_iterator __position, value_type&& __v) -> iterator
+    {
+      const auto __n = __position - cbegin();
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
+	  && __position == cend())
+	{
+	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				   std::move(__v));
+	  ++this->_M_impl._M_finish;
+	}
+      else
+	_M_insert_aux(begin() + __n, std::move(__v));
+      return iterator(this->_M_impl._M_start + __n);
+    }
 
   template<typename _Tp, typename _Alloc>
     template<typename... _Args>
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..1b46124 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
@@ -223,7 +223,8 @@ test03()
 void
 test04()
 {
-  const X::special expected{ 0, 3, 1, 0, 3, 0 };
+  const X::special expected_ins{ 0, 3, 1, 0, 3, 0 };
+  const X::special expected_emp{ 0, 4, 1, 0, 4, 0 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -253,8 +254,8 @@ test04()
     // std::cout << "----\n";
     emp = X::sp;
   }
-  VERIFY( ins == emp );
-  VERIFY( ins == expected );
+  VERIFY( ins == expected_ins );
+  VERIFY( emp == expected_emp );
 }
 
 // insert vs emplace xvalue reallocation

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]