Rust Memory Management: Ownership vs. Reference Counting
slicker.me
slicker.me
> Every heap allocation has exactly one owner...
This goes one step further, in that every value including on the stack has a single owner. That's why you can't pass the same `let a = [0; 10];` by value multiple times, even though that's an array on the stack.
> Zero overhead — no extra indirection
I think this is slightly misleading for borrowing, since a reference (`&`) is fundamentally a pointer that the compiler ensures upholds some special properties. So borrows come with a pointer deref when used, similarly to a `Box` or `Rc`, etc. I think the intention is to point out the heap allocations when using smart pointers which are definitely more expensive than `&`, but that doesn't really come across.
Only other call-out is that I'm not sure what the various colours indicate throughout. They look really pretty, but I'm not sure when something becomes teal vs yellow vs orange vs purple.
Isn't the crux that Rust does those things without a garbage collector, that's the novel part? Someone correct me if I'm wrong (likely), but I think all those languages have garbage collectors, which Rust doesn't.
The thing about it being optional in some languages is that it's an experiment, but one that as a feature it really pays off the more code in the ecosystem is compliant to ownership tracking. For rust, it's the vast majority of it (with opt out explicitly findable..) For languages offering it optionally, it's harder to assemble the full benefit.
That's not quite how it works in various languages. You appear to be thinking of the garbage collector as something inseparable from the language.
Both Dlang and Vlang have optional garbage collectors, that can be turned off. In the case of Vlang, none of its libraries depend on the garbage collector. Vlang offers optional (flexible) memory management, somewhat similar to Nim (but they presently don't have optional ownership).
In the case of Julia and Vlang, their optional ownership is new and experimental. Dlang's optional ownership has been around for some years now, showing that it could be done.
Dlang and Vlang allow you to choose the type of memory management (along with some other languages) that you would like to use. Vlang does it by command line flags. You can turn off garbage collection and turn on ownership.
Until you need a library that was written with the assumption of using a garbage collector.
If you were to implement a Rust GC, then Rust can guarantee that references haven't escaped the current thread, which means there is no stop the world pause anymore, only the current thread gets paused, which is acceptable.
In fact, we can see this "defaults matter" problem in Rust as well. Note that Rust by-default assumes that code is running in a context where a dynamic allocator is available, but allows one to opt-out of this ("no_std" mode). Code written for embedded devices or baremetal contexts uniformly opt into this mode, but because it's not the default, you can't just pull any old library off the shelf and expect it to work for you, so the ecosystem is much smaller and less mature. Defaults matter.
The argument is often about when ownership and borrowing is truly necessary. Rust has its uses, but arguably not all the time and with everything, because of its defaults.
It opens up entirely new avenues for statically error-free programming, letting you model things like “if the caller has an instance of this type, I can guarantee that this other larger proposition is true”. Namely without also having to handle the case where the user smuggled another instance from another call site.
This is really, really useful.
In various forms, affine types, linear types, dependent types, effects, formal proofs.
The list is already rather long, D, Chapel, Swift, Linear Haskell, Ox, OCaml, Koka, Ada/SPARK, Mojo,...
struct Node {
value: i32,
children: Vec<Rc<RefCell<Node>>>>,
parent: Option<Weak<RefCell<Node>>>>, // Weak breaks parent→child cycle
}
there ought to be a crate that handles "Vec<Rc<RefCell<..." part (maybe https://crates.io/crates/orx-concurrent-vec ? haven't tried it yet)
Internally shared ownership is a huge anti-pattern and rarely achieves what you’re actually trying to do. Graphs like these are much better represented by splitting the topology from the node data, and using indices or keys to form edges instead of (smart) pointers.
You can use pointers, but then the correct choice is actually raw pointers and `unsafe`, with a safe whole-graph-level API for traversal and access. This is what Rust’s own collection types do internally.
I always heard that but comming from Python internal references would be the way to go so it's not natural to me.
Node data in one list. Indices of node parents in another list of the same length. If you need to find children quickly, you can have another list of lists containing children indices.
The key is to consider the node’s position in the list as its ID, and refer to nodes by that index instead of the pointer.
In most cases, this model is both easier to work with and more performant. For example, you can usually get by with 32-bit indices instead of 64-bit pointers, so things are much more likely to be in cache.
Edit: also the simplest way how to do cyclic structures is to heap-allocate via Box and leak memory. Box::leak This is also mentioned in the linked article.
I wouldn't like to work with it, but I wouldn't be too surprised if I encountered a List<Optional<WeakReference<Holder<Node>>>>. A list, containing optionally-present weak references to a holder object (which you might need if you intend to update such an object from a lambda, as those can only take effectively final variables from their parent scope).
I think there's value to the Rust implementation. In many other languages, these wrappers are either non-optional or hidden away with syntax, but they're still present. The Rust approach puts the developer in charge of how data should be exchanged (copied/borrowed/on stack/in heap/etc.). You can write extremely efficient programs that stack very few of those types, with many restrictions on how they ca be passed around to methods, or you can make your life easier at the cost of some performance and clutter.
For clarity, you could do something like this:
type RVec<T> = Vec<Rc<T>>;
type RNode = RefCell<Node>;
struct Node {
value: i32,
children: RVec<RNode>,
parent: Option<Weak<RNode>>
}
It's not without problems, but the idea is less confusing in practice than it seems.
A scene graph needs 2 mutable references, and has nothing to do with ownership. Same issue exists with GUI's. The pattern that Rust forces is to always request a reference, which incurs a performance penalty while retrieving the same reference again and again and again.
Even memory locality of a arena doesn't provide benefit, because memory order does not mirror execution order.