[Pannoniae]

They're just clearly inferior in pretty much any situation.

The map stuff the other posters summed up well but even std::vector is dogshit with pretty much all implementations having inlined grow code in push_back, a not too great API and missed optimisations e.g. no trivial relocation when growing the vector / moving it and no useful APIs such as "grow but don't initialise"...

[jstimpfle]

To be fair grow-but-don't-initialize is a pretty fundamental part of the API, the reserve() method.

But already the basic premise that you should push back without thinking is wrong. You will suffer reallocations and invalisations when you least expected them, and frankly you have to architect around that fact which is a terrible restriction. You can work around by pre reserving but at that point it's just a basic fixed heap allocated array but worse because the type gives you a weird look all the time, "I'll realloc as soon as you don't pay attention, harhar"!

[tialaramex]

std::vector lacks what I call the "bifurcated reservation API". It has Rust's Vec::reserve_exact but not Vec::reserve -- these APIs serve subtly different purposes, the former (which C++ calls just "reserve") says "Here's a hint for exactly how big this container will ever grow" while the latter says "Here's a hint for how big this container will get in my immediate future, but it might grow further later".

The implementation always tries to grow (if necessary) to the exact size chosen for Vec::reserve_exact, but for plain Vec::reserve if growth is needed it always grows exponentially, not to the exact size, preserving the O(1) push cost.

For a typical "doubling" growable array type, if we're pushing groups of ten items, reserve_exact or C++ grows like 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ... which is much worse than O(1) whereas the correct reserve grows 10, 20, 40, 80, 160 preserving O(1)

For trivial types you can work around this in C++ with a little work, and for the non-trivial types you can work around it with a bunch more extra code, but you probably won't.

Bjarne among other people teaching C++ recommend just not using the reservation API as a reservation API because of this problem†, and the resulting teaching definitely leaks into CS graduates and even into languages which have the correct API and so you have to un-teach the bad lesson.

In applications where you actually can't afford to pay for growth (or at least in some cases can't afford this) I also like Vec::push_within_capacity which I believe comes from Rust for Linux where the kernel legitimately needs this "If there's room push, otherwise I have a plan B" approach.

† To Bjarne this API is instead conceived of as a way to preserve reference validity. Since it won't grow, our references will still work.

[jstimpfle]

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()!

[tialaramex]

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.

[jstimpfle]

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.

[tialaramex]

> 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 ?

[jstimpfle]

Feels like typical improvement/perfection tunnel vision syndrome to me, though. That syndrome is engrained in C++ community and I think also Rust community, although it looks like the latter took the chance to do many things better from the start learning from C++'s mistakes.

Realloc is pretty much never the right way in whatever form, and I've never seen any need to include realloc in any of my own allocators (mostly blockallocators and linear allocators and pools/free lists, sometimes using malloc/free).