Comment by jstimpfle
7 hours ago
> 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
> 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.
I don't know the size up front because it goes up and down depending on load. I want to be able to buffer jitters/spikes but not hog memory when there is no data in the queue. I was assuming it's natural to want a simple linked list of chunks to represent this, maybe chunks can be partially full here. So chunk -> chunk -> chunk, and each chunk is actually a node with a buffer pointer + size + fill fields, or maybe the data comes directly after the size + fill fields so no buffer pointer needed.
That easily gives O(1) access to enqueue/dequeue, and the queue naturally grows and shrinks (even within configurable bounds) as part of reading and writing. Blocks can be taken and returned from/to some fixed size block pool. This design would be completely satisfactory. It's also very easy to code from scratch, so why should I settle for anything less, for example a growable vector where a reallocation would mean blocking other threads for extended time? But I was told to "not reinvent the wheel" and to "not overengineer it" so I tried to change my mind and make use of an STL container data structure.
> our disagreement seems to be that you think a slightly different terrible data structure would be a good idea
I don't know why you think that I would be thinking that, and I'm confused that you say you were gesturing at how std::deque is terrible, and not sure why I should be the one misconstruing something, when my premise from the beginning was "STL containers are terrible in many ways". And I don't get at all why you responded with "basically std::deque" to my "maybe chunk lists would better". It doesn't make the least bit of sense to me.
But let's settle this here, this is a pointless fight...