This is the mail archive of the
mailing list for the libstdc++ project.
Re: [PATCH] Optimize inserting value_type into std::vector
- From: Jonathan Wakely <jwakely at redhat dot com>
- To: libstdc++ at gcc dot gnu dot org, gcc-patches at gcc dot gnu dot org
- Date: Wed, 15 Jun 2016 16:31:31 +0100
- Subject: Re: [PATCH] Optimize inserting value_type into std::vector
- Authentication-results: sourceware.org; auth=none
- References: <20160615101511 dot GN11538 at redhat dot com> <20160615103424 dot GO11538 at redhat dot com>
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
This improves our performance on Howard Hinnant's "insert vs emplace"
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:
insert(const_iterator pos, const value_type& x)
if (cpacity() == size())
// reallocate and insert ...
auto it = end() - 1;
*end() = std::move(*it);
const value_type* from = std::addressof(x);
for (; it != pos; --it)
auto prev = it - 1;
*it = std::move(*prev);
if (std::addressof(*prev) == from)
*pos = *from;