[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]

> was already what you were paying by using the amortized O(1) growable array type

As I said, I don't think growable array data structure is a good idea.

> Basically std::deque. Surely no more need be said ?

Ok now you're really out of your depth here. Pretty sure you haven't actually used it, it's a somewhat obscure data structure even though the more serious C++ programmers have heard of it, most have probably never used it.

From a web search, std::deque seems to be pretty universally thought of as a weird and very bad data structure. I've had to learn myself because I did actually try to use it myself recently. Beyond being unintuitive to use due to being "abstract" (had 2-3 serious bugs, e.g. unexpected iterator invalidations that happened only under load), apparently std::deque is not even specified as a chunk list. O(1) random access must be guaranteed. So it must be much more complicated than that, I don't know the details though.

And while actual implementations do use chunks in some way (just not in a simple chunk list), apparently "chunks" is not a part of the std::deque spec, and hence there isn't anything standardized about the size of these chunks either.

- On MSVC, chunk size is 16 elements so chunk size of std::deque char is 16 BYTES !!!!! I was thinking they can't be serious, but apprently it is the case

- On GCC, chunk size is 512 byte fixed.

- On Clang, chunk size is 4096 byte fixed.

It _is_ a shithole, surely no more need be said?

[tialaramex]

> As I said, I don't think growable array data structure is a good idea.

It is still quite hard for me to take this seriously as a belief.

> Ok now you're really out of your depth here.

I don't think so. As you found, the consensus is that this sort of thing is a terrible idea. The O(1) complexity looks good superficially but your actual performance is miserable.

> I don't know the details though.

Raymond Chen has a pretty good explanation of the three implementations of std::deque, like he did for their std::string but Raymond's goal is to help you do forensics, he's not here to tell us which data structures are a good idea. https://devblogs.microsoft.com/oldnewthing/20230810-00/?p=10... might work, or, given Microsoft, it might already be dead by the time you click it.

[jstimpfle]

> The O(1) complexity looks good superficially

Without knowing more about the details of the spec and of real world implementations [0], I'll boldly claim that the O(1) is the precise problem why this is a weird data structure (I never needed or expected that sort of constraint). It is not a chunk list, like many (including me) seem to have assumed.

I don't even have performance problems measured with this, also given that my std::deque is not currently in production, it is used as a simple streaming queue that only has a couple megabytes/second of bandwidth requirements, and it is not being built with MSVC (so chunks are going to be 512 or 4096 bytes). But it is a latent problem.

[0] Btw. I don't want to know the messy details of this right now, I need simple not complex. I've learned not to add more complexity in a futile attempt to fix things that are fundamentally broken. What use case is this going to be solved by std::deque, name me one such use case and tell me with a straight face that it's not a completely made up case or a super niche case that would likely also be better served by a different approach.

Or take it from someone else if you would, is Chandler Carruth high-profile enough and free enough of conflict of interest to be credible for saying that std::deque is dumb? https://news.ycombinator.com/item?id=22962980

[tialaramex]

> It is not a chunk list, like many (including me) seem to have assumed.

The thing C++ programmers tend to expect (though perhaps not you) is Rust's std::collections::VecDeque - the growable array type again but used as backing for a ring buffer.

This type has amortized O(1) push and pop at both ends, I assume since you didn't like the amortized growth of Vec / std::vector you'll feel the same way but that's what most programmers actually want from such a type - in use as a queue it won't repeatedly cycle allocations so long as the size is constrained, because it's a ring buffer. If you actually know the needed size up front the overhead from this structure, which can grow, versus a structure which can't grow, is a single integer for the capacity.

But as you saw, std::deque is... not that. STL wasn't able to explain what it's for when I asked him, so, if anybody knows it apparently doesn't include the people maintaining the C++ standard library implementations.

> Or take it from someone else if you would

I think the trouble here is that you've misconstrued this entire part of the conversation. I was gesturing at std::deque because it's terrible, and your response, that it's terrible, isn't a rebuttal as I think you're expecting. We agree on that, std::deque is terrible, our disagreement seems to be that you think a slightly different terrible data structure would be a good idea somehow and I do not.