6 ms·
This seems wrong to me: > Vec will never perform a "small optimization" where elements are actually stored on the stack [because] it would penalize the general
by mehrdadn 9y ago
This seems wrong to me:
> Vec will never perform a "small optimization" where elements are actually stored on the stack [because] it would penalize the general case, incurring an additional branch on every access.
I don't follow this. I can see appending to a vector requiring an extra branch, but why would every access (like, say , vec[i] = 0) need an extra branch?
- barrkel 9y agoif (vec.size < THRESHOLD) { vec.local[index] = value; } else { vec->heap[index] = value; }
- mehrdadn 9y agoDidn't they say Vec is a (pointer, capacity, length) triplet though? Wouldn't it just be vec.pointer[index] = value regardless of whether the pointer points to the stack or the heap?
- barrkel 9y agopointer would be pointing at internal structure memory, it would need to change on every copy then.
- mehrdadn 9y ago> pointer would be pointing at internal structure memory, it would need to change on every copy then. Sure, sounds fine to me. What's wrong with this? The pointer would need to change on every copy anyway, since it'd need to point to a new buffer even if it were pointing to the heap.
- barrkel 9y agoIt sounds fine from a C++ world of copy constructors. I think copy constructors aren't worth the exception safety downsides.
- mehrdadn 9y agoI don't understand. I asked why there is a mandatory branch, you said otherwise the pointer would need to change on every copy, I said that's fine, and now you rebutted that copying isn't even worth it? So what is the problem and where is the extra branch? I don't understand where the discussion is going.
- koverstreet 9y agoYeah, that is the normal way of doing that optimization.
- kam 9y agoIn the "small vector optimization", the storage on the stack would be in place of the `(pointer, capacity, length)` except for a tag byte, so keeping the pointer would waste nearly 1/3 of the potential space. Also, when a Rust object is moved, there's no move constructor; it's purely a memory copy, so there would be no way to update the pointer for the new location.
- mehrdadn 9y ago> so keeping the pointer would waste nearly 1/3 of the potential space. Sure, but that still doesn't mean you'd get an extra branch? > Also, when a Rust object is moved, there's no move constructor; it's purely a memory copy, so there would be no way to update the pointer for the new location. Ah, this would seem like a complete deal-breaker. But if this is the case then why didn't they mention this instead of the other reasons? It seems far more compelling and fundamental than the other two? [EDIT: Ignore this last part. I think I confused the issue here with something else when adding this final sentence.] A̶l̶s̶o̶,̶ ̶t̶h̶i̶s̶ ̶̶s̶t̶i̶l̶l̶̶ ̶d̶o̶e̶s̶n̶'̶t̶ ̶m̶e̶a̶n̶ ̶t̶h̶e̶r̶e̶ ̶w̶o̶u̶l̶d̶ ̶b̶e̶ ̶a̶ ̶b̶r̶a̶n̶c̶h̶ ̶o̶n̶ ̶e̶v̶e̶r̶y̶ ̶a̶c̶c̶e̶s̶s̶,̶ ̶r̶i̶g̶h̶t̶?̶
- Manishearth 9y ago> Also, this still doesn't mean there would be a branch on every access, right? Yes it does, without a move constructor the only way to do a small vector optimization is to detect when the vector has been packed in the indexing operation and do the pointer math internal to the stack part of the vector. With move constructors you keep the pointer up to date, without them you have to recalculate this information on any kind of access, and for this you need to know when stuff must be recalculated which leads to the extra branch.
- Manishearth 9y agoThis would be true in C++. However, Rust has no move constructor; so the small vector optimization can't be implemented as "make the pointer point to itself and fix it up every time you move things", it must be implemented by having some check and then changing how you refer to elements. Note that in C++ the move constructor has a similar cost whenever it gets moved around (and the cost can become problematic in cases like nested vectors where resizing is no longer a memcpy). (moves are also implicit and more common in Rust so the impact would be more even if Rust did have move constructors. Which isn't really a workable hypothetical, since Rust's model is not designed in a way that that would be consistent anyway)
- mehrdadn 9y agoWow, this seems like a very painful restriction coming from the C++ side. Thanks for the explanation.
- Manishearth 9y agoIt's actually not that painful. C++ has a bit of a different safety model that somewhat relies on move constructors to work. Rust builds this in, with some crucial changes. For one, all C++ values are forced to have a zero state; e.g. when you move out of a unique_ptr (in certain ways, not all of them) the old one must be zeroed, because the destructor will still be run on it. Use after move leads to unspecified but not necessarily undefined. Rust OTOH does not have null as a valid value for its pointers. In case of conditional moves Rust will use an extra bit on the stack called a "drop flag" to track whether or not the destructor needs to be run, but only when needed, and usually it isn't so this complexity is abstracted away and also doesn't impact the runtime for the majority of times it isn't necessary. 99% of the move constructors in C++ are focused on making this work correctly. It's not necessary in Rust. There are the 1% that do stuff like the small string optimization. Yes, you can't do this as neatly in Rust. But it's worth noting that move constructors have a significant cost, both in runtime (things like vectors need to deal with this correctly -- in particular vector<smart_object<_>> can't memcpy on resize anymore), and in compile time -- if you want to build good generic abstractions you have to guard against the fact that moves (and copies) can do anything. This would completely destroy Rust's ability to easily compartmentalize safety because now you have to worry about arbitrary code running every other line of your generic code. In C++ you don't care about this as much; since compartmentalizing safety is more of a best-effort thing and blame is harder to assign, whereas in Rust your generic datastructure must be safe when you throw any (safely implemented) type at it. So yeah, sounds painful, but not really, and from a Rust POV what C++ has in this space is really painful.
- dbrgn 9y agoIf you want opt-in small vector optimization you could also use this crate written by the Servo team: https://github.com/servo/rust-smallvec https://github.com/servo/rust-smallvec You can take a look at their implementation. If I'm reading this correctly, access by index goes through deref, which matches on the self.data type: https://github.com/servo/rust-smallvec/blob/5758c25663da2421792078dd05624e31eee71db1/lib.rs#L737-L744 https://github.com/servo/rust-smallvec/blob/5758c25663da2421...