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: [PATCH] Optimize inserting value_type into std::vector


On 15/06/16 11:34 +0100, Jonathan Wakely wrote:
On 15/06/16 11:15 +0100, Jonathan Wakely wrote:
	* include/bits/stl_vector.h (vector::_S_insert_aux_assign): Define
	new overloaded functions.
	* include/bits/vector.tcc (vector::_M_insert_aux): Use new functions
	to avoid creating a redundant temporary.
	* testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc: New
	test.

Tested x86_64-linux.

This improves our performance on Howard Hinnant's "insert vs emplace"
experiment at
http://htmlpreview.github.io/?https://github.com/HowardHinnant/papers/blob/master/insert_vs_emplace.html

With this small change there is no difference between emplacing or
using the relevant insert / push_back function. That also means we
beat libc++ in some cases, making us the bestest, whoo!

We still lose to libc++ in one case. For the "lvalue no reallocation"
test our insert and emplace are equal to libc++'s emplace, but
libc++'s insert is even better.

Libc++'s insert(const_iterator, const value_type&) is *really* clever.
It notices when the object to insert is an element of the vector, and
then works out where its updated position would be after shifting the
existing elements along, and then copies from the new position. That
avoids the copy we make upfront to handle that case safely. Our
approach is inefficient for the common case where the object *isn't*
in the vector.

I guess it's something like:

 void
 insert(const_iterator pos, const value_type& x)
 {
   if (cpacity() == size())
     {
       // reallocate and insert ...
       return;
     }
   auto it = end() - 1;
   *end() = std::move(*it);
   ++this->_M_impl._M_finish;
   const value_type* from = std::addressof(x);
   for (; it != pos; --it)
   {
     auto prev = it - 1;
     *it = std::move(*prev);
     if (std::addressof(*prev) == from)
       ++from;
   }
   *pos = *from;
 }

Clever.



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