Comment by jstimpfle
1 day ago
Vec::reserve() is the behaviour you get from C++ std::vector push_back() (implicit just-in-time reserve), so right now I can't see a situation where I'd want the explicit Rust version even if I didn't think the whole push realloc thing is mostly a bad idea.
Yes, Rust version allows you to maybe skip a reallocation step or two by doing explicit up front reallocation. But remember most allocation work is always from the last grow anyway. The Rust version seems like a microoptimization, giving a little bit more explicit control in a situation where you've already pretty much given up control and gone like, throw hands in the air, we're doing push_back()!
As with the likely/ unlikely branch hint the problem is that programmers are wrong much more often than they expect on both sides. They're too often wrong to think they know the final size - hence Bjarne's caution - but they're also too often wrong that they've got no idea how much capacity they need at all. So hence this API.
You're correct that this isn't a huge optimization. But it more than pulls its weight directly because it's a small boon when you're right and it doesn't have the terrible penalty that Vec::reserve_exact has when inevitably the programmer is sometimes wrong. It's very much about saving pennies, but the growable array type is so widely used that counting pennies makes sense.
I have a lot more thoughts about reservation, but these suffice for specifically the growable array type.
There are many many situations where I know exactly what is the common path and what is the uncommon path. And when I don't know, it's much harder to optimize!
If you're counting pennies, Vec::reserve() (inexact) is hardly what you want, because in the worst case you're wasting a factor of 1.5x or 2x of elements due up-front overallocation. Maybe chunk lists could be better, overhead is bounded by chunk size and all operations are constant-time. No pointer invalidation either. And you can pool those chunks, preventing memory fragmentation and improving memory utilization, since there aren't a million different sized allocations in your process.
> If you're counting pennies, Vec::reserve() (inexact) is hardly what you want, because in the worst case you're wasting a factor of 1.5x or 2x of elements due up-front overallocation.
I think this is "Trump math" but assuming we're actually looking at the same over-allocation this isn't new, what you're calling "wasting a factor of 2x" was already what you were paying by using the amortized O(1) growable array type, that's its central trade off, so yeah, the type with that property does still have that property.
> Maybe chunk lists could be better, overhead is bounded by chunk size and all operations are constant-time.
Basically std::deque. Surely no more need be said ?
1 reply →