Re: [boost] Interest in StaticVector - fixed capacity vector
On 14 October 2011 05:32, Dave Abrahams <dave@boostpro.com> wrote:
Use-cases, please!
I worked on a messaging system that created messages via serialization (that took iterators) and delivered them via UDP. Most messages were small (<100 bytes) with occasional messages 1K-2K in size. To give ourselves breathing room, we allowed messages up to, say, 32K, as it would be a non-trivial effort to implement splitting/reassembly of messages.
How could it ever be a "drop-in replacement for vector"
For over a decade, the mental model for calling push_back, insert, resize, etc. is that it they have no preconditions to check. This is true *for every standard container* (which supports the corresponding operation, of course). You want to *silently* break that consistency. That will lead to buffer overrun bugs, which we know are hard to debug and I'm not saying we don't need the unchecked functionality. I'm saying it should never be spelled p-u-s-h-_-b-a-c-k, i-n-s-e-r-t, r-e-s-i-z-e, etc. (which is one of the reasons I'm arguing against making it policy based). I'm strongly opposed to any solution that uses the same function signatures as the standard containers that isn't as safe and easy to call as the ones in the standard containers. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
on Sat Oct 15 2011, Nevin Liber <nevin-AT-eviloverlord.com> wrote:
So... had you received a message > 32K, what would have been the response of your program?
You have a point, but you're exaggerating. It's not *silent* if it's a new class.
That will lead to buffer overrun bugs, which we know are hard to debug and
Yes, that's a good point. But that's why I proposed a secure mode.
I'm not convinced we can maintain that kind of consistency everywhere. You have to pay for the optimization of StaticVector with weaker guarantees. These containers may not be able to supply a nonthrowing or O(1) swap, either. But if we're going to check anyhow, let's move the storage to the heap. IMO-ly y'rs, -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 15 October 2011 17:58, Dave Abrahams <dave@boostpro.com> wrote:
Deserialization would have failed due to lack of data, thrown an exception (for stack unwinding) which the higher level interface would have caught and turned into an error code returned (getting developers to look at the error code was another story, as the original product wasn't networked and had 100% reliable message delivery of hard to use POD messages).
It's still silent, as it isn't the same interface even though the actual call looks the same. When looking for causes of buffer overrun bugs, I can ignore calls to push_back, insert, resize, etc., because they cannot be the direct cause since they have no preconditions. I don't have to go trouncing back to see what the actual container type is to see if the caller had to "be careful" (a euphemism for "be perfect") or not.
I'm not convinced we can maintain that kind of consistency everywhere.
Where are we currently breaking it? I still think it is a goal we should strive for.
These containers may not be able to supply a nonthrowing or O(1) swap, either.
In some sense it is O(1), since N is bounded, but I know what you mean. :-) swap is one of the places (the only one?) where we cannot meet the guarantees that std:vector makes. That just isn't true about push_back, etc. My turn to ask a question: why are you so adamant that the unsafe versions be spelled push_back, etc.? -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
on Sun Oct 16 2011, Nevin Liber <nevin-AT-eviloverlord.com> wrote:
Well, now we could pick nits over the meaning of "same interface." I still think it's an exaggeration. It's got to be legitimate to discover that the concepts you've been using all along refine some less-constrained concept, but whatever. My point is, you have a point. :-)
Having to be careful is evil, agreed.
See below.
There's also the nonthrowing part.
I'm not. If you think I am, you've misconstrued me. I'm just trying to understand the design space and represent a point-of-view about handling likely programmer errors that I think is important and overlooked. I do very much dislike the idea of having multiple interfaces for what is essentially the same semantics. There are certainly applications where it's knowable statically that the limit can never be violated where one might want to drop in a bounded vector in place of std::vector, and having to spell push_back some other way, as though it were essentially different, is ugly. That's one reason I'm being pushed toward "policies" (i.e. a CapacityHandler) for this case. It would still force the user not to ignore the boundary case without forcing him to accept an exception when it's not appropriate. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 16 October 2011 06:50, Dave Abrahams <dave@boostpro.com> wrote:
Are the "Requires" clauses in the Standard part of the interface or not? I see the answer to that question as something fundamental, not picking nits. In my point of view they are part of the interface, as they describe when it is legal for me to make a particular function call.
I agree. Then again, the only alternative is not providing swap at all.
When you mess with programmer's expectations, you get programmer errors.
I do very much dislike the idea of having multiple interfaces for what is essentially the same semantics.
Of course, I'm arguing they are different interfaces, but to address this point, we have multiple interfaces for the same semantics all the time. c.push_back(x) is just c.insert(c.end(), x), c.clear() is just c.erase(c.begin(), c.end()), etc. Just today I had to show someone the swap trick for releasing space in a vector because there is no obvious way to do it in C++03; I don't consider that a good thing.
I don't think we can resolve this. I see them as different interfaces; you may not. Subtle interface differences lead to subtle bugs. -- Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
on Wed Oct 19 2011, Nevin Liber <nevin-AT-eviloverlord.com> wrote:
Yes, absolutely. But that's just one function. I think I had in mind the total interface of the class, frankly I've forgotten at this point. I see a container that can never store more than N items, for some reasonably small N, as fundamentally, semantically different from one that is highly likely to be able to store any M items you have to deal with, and for which you can't determine a hard limit N ahead of time (no, max_size() doesn't count—that's typically just numeric_limits<size_t>::max()). I grant you that we don't have a very strict way of expressing this difference in a specification, but I think that's just missing. I wouldn't, except in very special circumstances, consider one of those containers to be a suitable replacement for the other, despite the similarity of the specification text. Would you?
Yes, but I think there's something else in the interface (abstractly) that you may not be accounting for, and that clearly makes these two push_backs different, even if you choose the throwing semantics.
Sure. I'm not arguing there's something wrong with the throwing swap in this case; I'm just saying the optimization of "no dynamic allocation, ever" has consequences that ripple through the interface.
A programmer who doesn't adjust his expectations when replacing something essentially unbounded with something essentially bounded is in for a rude surprise no matter what is done about this particular feature. Sounds like you just don't want to appreciate the point-of-view I'm representing. That's OK, but I don't think I'll follow up on this post in that case.
I believe you are misunderstanding. In fact, c.insert(c.end(),x) does not (or did not, in C++03) give the same exception-safety guarantees as c.push_back(x).
Sorry, I don't see the relevance.
OK. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
[Nathan Ridge] [Nevin Liber]
I don't have strong feelings about this, but I would be OK with changing the name of my proposed std::array-like version of static vector (which I had called capacity_array for lack of a better name)
[Sorry, e-mail client acting up, ignore my previous email] [Nathan Ridge]
[Nevin Liber]
I don't have any strong feeling about this, but I would be OK with changing the name of capacity_array's push_back() to something else for this reason (in which case it would not have a method named push_back at all). Regards, Nate
participants (3)
-
Dave Abrahams -
Nathan Ridge -
Nevin Liber