5 ms·
Needs (2023) > I predict that tracing garbage collectors will become popular in Rust eventually. The use of Rc is already very widespread in projects when peo
by hyperbrainer 2y ago
Needs (2023)
> I predict that tracing garbage collectors will become popular in Rust eventually.
The use of Rc is already very widespread in projects when people don't want to deal with the borrow checker and only want to use the ML-like features of Rust (Sum types, Option, Error etc.)
> Rust has arrived at the complexity of Haskell and C++, each year requiring more knowledge to keep up with the latest and greatest.
I wonder when we will see the rise of Haskell like LanguageExtensions in Rust. AFAIK, pretty much everybody uses things like GADT, PolyKinds, OverloadedStrings etc. The most similar thing I can think of Rust right now for is python-like decorator application of things like builder macros using Bon.
> Async is highly problematic
Agreed. Tokyo is the only reason, I think, anybody is able to use Rust for this stuff.
- tptacek 2y agoDoes Rc really resolve the core problem this post is talking about, which is that it's really painful to naturally express tree and graph structures in Rust? It feels like I mostly see people talking about building application-layer pointer systems with integers, which would be surprising if (in a single thread, perhaps) you could just Rc your way around the problem.
- cmrdporcupine 2y agoSure, Rc/Arc absolutely solves this problem. It's not super idiomatic to go crazy with using it like that, but it's possible/acceptable. Using SlotMap and integer ids, etc. doesn't I think offer any advantage.
- tptacek 2y agoI feel pretty comfortable with Rc and Arc, read the "too many lists" book, &c. and feel like it is not actually simple to model trees with Rc? What am I missing? I'd love to be convinced I'm wrong about this (I want to like Rust more than I do).
- cmrdporcupine 2y agoA tree of Rc/Arc<T> is a tree of references, and is really no different than a Java or Python reference value, except that you'll have to do explicit .clone()s Is it mutability that's tripping you up? Because that's the only gotcha I can think of. Yes, you won't get mutability of the content of those references unless you stick a RefCell or a Mutex inside them.
- tptacek 2y agoYes! Mutability is what's tripping me up! That is not a minor detail!
- cmrdporcupine 2y agoYou can get something like what you're used to a "traditional" language without compiler safeguards by using RefCell and .borrow_mut() on it. That will let you get past the compile-time borrow checks but will do runtime borrow checking and throw panic if more than one borrow happens at runtime. It's verbose, but it's explicit, at least. So: struct Node { parent: Rc<RefCell<Node>>, left: Option<Rc<RefCell<Node>>>, right Option<Rc<RefCell<Node>>>, } and just off the top of my head it'd be something like { let my_parent = my_node.parent.borrow_mut(); ... do stuff with my_parent ... } ... my_parent drops out of scope here, now others can borrow ... etc. Haven't tried this in compiler my memory might not be right here.
- tptacek 2y agoI do know that it's possible, but when people complain about this --- as with this tweet, from a PL theorist: https://x.com/LParreaux/status/1839706950688555086 https://x.com/LParreaux/status/1839706950688555086 ... this is what they're talking about. (I know the tweet is about the "idiomatic" answer to this problem, which is to replace references with indices into flat data structures).
- cmrdporcupine 2y ago
- nine_k 2y agoDoesn't SlotMap save RAM and pointer dereferences?
- cmrdporcupine 2y agoWhat is a slotmap lookup... if not a pointer dereference, or at least a dereference out of a vector likely on heap... so probably a pointer...?
- School-Cotton 2y ago> Does Rc really resolve the core problem this post is talking about, which is that it's really painful to naturally express tree and graph structures in Rust No, it doesn't. If you naively express graphs containing cycles with `Rc` you will leak memory, just like you would with `std::shared_ptr` in C++.
- hyperbrainer 2y agoConsidering that there exists a book about building linked lists in Rust[0], I am going to go ahead and say "Unclear" That does not matter though. It is easier (though verbose and often unidiomatic), and hence Rc has become really popular, especially with beginners. [0] https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/
- ordu 2y ago> Does Rc really resolve the core problem this post is talking about, which is that it's really painful to naturally express tree and graph structures in Rust? No, but Gc will not resolve the core problem either. The core problem is that rust forbids two mutable pointers into one chunk of memory. If your tree needs backlinks from child nodes to parents, then you are out of luck.
- tptacek 2y agoIn what way am I "out of luck"? It's trivial to express a tree, including one with backlinks, in Java.
- okanat 2y agoand then your gc will leak it. Rust programs are not only safe but CPU and memory efficient.
- truetraveller 2y agoI simple standard mark-and-sweep GC will not "leak it".
- guappa 2y agoThis has been a solved problem for decades.
- ordu 2y agoJava doesn't enforce the rule "mutable XOR shared". But if you have a link "child" in the parent node, and a link "parent" in the child node, then parent.child.parent == parent, and compiler cannot know it. So Rust as the language makes it impossible to do with &-pointers, while standard library of Rust allows it to do with combination of Option, Rc, RefCell but it is really ugly (people above says it is impossible, but I believe it is just ugly in all ways). Like this: type NodeRef = Rc<RefCell<NodeInner>>; struct Node { parent: Option<NodeRef>, left: Option<NodeRef>, right: Option<NodeRef> } So the real type of `parent` field is Option<Rc<RefCell<NodeInner>>>. I hate it when it comes to that. But the ugliness is not the only issue. Now any attempt to access parent or child node will go through 2 runtime checks: Option need to check that there is Some reference or just None, and RefCell needs to check that the invariant mut^shared will not be broken. And all this checks must be handled, so your code will probably have a lot of unwraps or ? which worsens the ugliness problem. And yeah, with Rc you need to watch for memory leaks. You need to break all cycles before you allow destructors to run. If I need to write a tree in rust, I'll use raw-pointers and unsafe, and let allergic to unsafe rustaceans say what they like, I just don't care.
- pcwalton 2y agoRc does solve the problem, but it often introduces interior mutability, which ends up causing usability problems. That's why at the end of the day adjacency representations (i.e. integers) are often preferred.
- nicce 2y ago> Agreed. Tokyo is the only reason, I think, anybody is able to use Rust for this stuff. A lot of problems related to Tokyo can be avoided if you think your code as structured concurrency and avoid using Tokio::spawn. However, too often this is not possible.
- hyperbrainer 2y agoI don't have too much experience with async, but I have noticed a similar pattern. Maybe you are right.
- written-beyond 2y agoI haven't, yet, run into building rust apps that require highly complex async implementations with lifetimes etc. however excluding those situations I've found it very straightforward and easy to use. I've built some applications with a lot of moving parts, mpsc has always been a life saver.
- bsder 2y ago> The use of Rc is already very widespread in projects when people don't want to deal with the borrow checker and only want to use the ML-like features of Rust (Sum types, Option, Error etc.) And the fact that this hasn't caused alarm is kind of an issue. The problem with that is Reference Counting is WAY slower than good Garbage Collectors on modern CPUs. Reference Counting breaks locality, hammers caches and is every bit as non-deterministic as a garbage collector.