> 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?
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)
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.
Hm, so let's say had this binary tree in C++:
template<class T>
class Node {
Node(Node const &) = delete; // don't worry about copying for now
Node &operator =(Node const &) = delete;
unique_ptr<Node> a, b;
Node *parent;
T value;
public:
Node(Node &&other) : a(move(other.a)), b(move(other.b)), parent(move(other.parent)), value(move(other.value)) {
if (parent) {
if (parent->a == &other) { parent->a = this; }
if (parent->b == &other) { parent->b = this; }
}
other.parent = NULL;
}
}
you can't implement it _this_ way, but you can still implement a binary search tree (Btreemap is a b-tree, which is a generalization of a binary tree).
Normally in Rust for a tree like structure with parent pointers you'd either use unsafe code or use Rc/Weak, depending on what you need.
As far as binary search trees are concerned IIRC you can implement them without parent pointers, you'd move your relocation method to something called on the parent node.
Note that this isn't just limited to trees. Even doubly-linked lists would have this issue, as would other more-complex data structures.
I guess my larger point is, it seems like the repercussions aren't just limited to missing low-level optimizations like small-string optimization like you claim, but they extend to your entire global object model as well as to what operations & time complexities you can support without the compiler yelling at you. That seems quite painful to me. Who wants to constantly argue with the compiler as to whether or not he should be allowed to have parent/sibling/other pointers?
People who value "I'm sure this can't explode", over "I'm pretty sure it won't explode, but at least it's a fast template that can stack-allocate" ;-)
But seriously - you can still do a lot of that if you really need to for some reason. Either use an external library in C++ or write some unsafe code which won't restrict your pointers.
How would unsafe code help here? The problem we were talking about was the lack of move constructors, and I just gave an example of their usefulness with parent pointers. How would unsafe code help? Unsafe code doesn't suddenly give you move constructors does it?
(As for writing external C++ code and linking to it... I mean yeah, but if the entire object model you have to interact with has to be in C++, then you might as well write the whole code in C++ at that point...)
Unsafe code lets you store parent pointers as raw pointers and update them manually when you move things. You don't actually _want_ a move constructor here; your btree values are on the heap anyway; what you want is a .move() method that chains correctly, and you can write this in Rust. In C++ the move constructor is a convenient way of doing this but not the only way.
Move constructors are how you organize the code in C++. Rust will not support the same code organization. This does not mean it's not doable in Rust, just that you have to design it differently. Rust is not C++; this is ok.
You learn to structure your code in a certain way. Design patterns from C++ will not necessarily carry over.
It certainly is painful to program in Rust if you design your code as if it were C++. In practice, the stuff you talk of doesn't end up being a problem; Rust still lets you do all that just that it's different.
> You learn to structure your code in a certain way. Design patterns from C++ will not necessarily carry over.
Er... data structures with parent pointers and sibling pointers are "design patterns from C++" to you?
Most such datastructures either get implemented with Rc/Weak (which has a performance cost but often not a problem), or with "unsafe", which lets you write Rust as if it were more like C++ (you still have types, but you now also have certain dangerous abilities that you use carefully). Rust provides you the tools to properly abstract this unsafe such that it stays within the implementation and doesn't leak. This is true for Vec and BTreeMap, for example.
You're talking about arguing with the compiler but unsafe Rust is not much worse than regular C++ in this aspect (there are some differences), so you always have the ability to drop down to this place where the compiler won't fight you to do stuff like this. Generally you can abstract away low level datastructures as unsafe code that's safe to use from the outside (this is usually something you can manageably audit) and everything else stays safe. Most such datastructures exist as libraries or in the stdlib already.
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/5758c25663da2421...
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.
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.
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̶?̶
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.