vector::push_back() is inefficient, as every time it checks whether the vector has reached its full capacity and needs to allocate more memory. Such a check is often unnecessary, e.g. if reserve() was called, see the example below.
I can vouch that it makes a difference. For frequent enough insertions, the cost comes not from mispredicted branches but the integer instructions to fetch and compare the capacity pointer.
The workaround is to not use push_back, but IMHO it should be the right tool for the job.
vector (size_type n, const value_type& val,
const allocator_type& alloc = allocator_type());
Into:
template<typename Generator>
vector (size_type n, Generator gen,
const allocator_type& alloc = allocator_type());
If we then had a way to write the algorithm as a coroutine, the vector would determine its capacity only once and let the filling flow.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.
In principle it's a valid problem, such checks can adversely affect inner loops, but the solution is way too specialized and obtuse.How about a means to pass hints to the allocator, maybe a dispatch tag indicating to forward arguments from push_*, insert_*, emplace_*, and constructors to allocator::allocate? This would in general enable dumb allocators where the client can specify where allocations go, and when they are allowed. It would be a powerful interface.
Shouldn't this be a task of the compiler? (To inline push_back and optimize away the 'if (size == capacity)' check if it knows that 'size < capacity' because of a previous .reserve().)
You should refactor your loop into a range, and construct the vector directly from that. This would resolve the issue.
Well, if I don't want to resize the vector (and construct objects), I can't see what work-around would
allow avoiding push_back. A vector of optionals would allow the resize without constructing
the underlying objects, and then I could just use operator[].
Ok, point taken about the v[i] case, but the whole insertion in the
grow() case could be passed of to another method (grow(parameter)) since
that is a problem only when a reallocation happens so there still is no
reason this would prevent inlining of the non-growing case.
/MF
void push_back(value_type&& _Val)
{ // insert by moving into element at end
if (_Inside(_STD addressof(_Val)))
{ // push back an element
size_type _Idx = _STD addressof(_Val) - this->_Myfirst;
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
this->_Getal().construct(this->_Mylast,
_STD forward<value_type>(this->_Myfirst[_Idx]));
++this->_Mylast;
}
else
{ // push back a non-element
if (this->_Mylast == this->_Myend)
_Reserve(1);
_Orphan_range(this->_Mylast, this->_Mylast);
this->_Getal().construct(this->_Mylast,
_STD forward<value_type>(_Val));
++this->_Mylast;
}
}
Assuming that the Widgets in your original example are costly to construct and overwrite,
the optional<Widget>s are not costly to construct.
I think a elegant solution for this (and a lot of other similar)
problem would be
something like this:
void foo(std::vector<char>& v)
{
assume(v.reserve() > v.size());
v.push_back('a'); // the compiler would do dead-code elimination and
then inline
}
It would unfortunately be much easier because ranges are so irritating to construct. This, however, is immaterial to the fact that the other solutions are a disgusting hack which is only an approximation to the real solution.
Why is that check any cheaper than the check for push_back to see ifthe vector should grow?
That is a quality of implementation issue but I would measure ratherthan guess regarding optimizations of standard library functions sinceoptimizers can be surprisingly good.
If one looks at GCC instead the implementation is
If we're going to further increase the performance of vector, the next most effective step to take is to teach allocators how to expand existing allocations in place (realloc without the possibility of an address change), and teach containers how to use such allocators. Doing this can produce as much as a 2X performance improvement compared to an un-reserved push_back loop. However even this at-best-2X improvement was not sufficiently enticing for the committee in the past. I have no reason to think it will be in the future.
Howard
Howard
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.