4 ms·

> I feel confident that my Rust is strong enough that I can already write any structure that is expressible in another language. I think it still can't handle

> I feel confident that my Rust is strong enough that I can already write any structure that is expressible in another language. I think it still can't handle arbitrary reference graphs without a garbage collector. If I'm wrong, please correct me, and provide proof. I'm very interested in the problem of non-GC arbitrary reference graph cleanups. On the other hand, one could ask the question of do we really need the arbitrary reference graphs? Or are they just a crutch that we use to make things easier for us? Perhaps every algorithm that requires a complex reference graph can be also expressed in Rust's safe mechanisms. Note that I don't have any deep knowledge about Rust, only stuff that I've read on various blogs.

vgel 4y ago
If you need a graph, the main approaches I see in Rust code are: a) Good ol' `Arc<Mutex>`, messy and has overhead, but easy to slap in and recreate the Java sea of objects. b) Arena allocators -- often if the graph is used for an uppercase Algorithm like spring layout or something, the graph has a singular lifetime, so not being able to individually free the nodes is fine. Then you just have `struct Node<'a> { others: Vec<&'a Node<'a>> }` and all is good, the nodes all have the same lifetime and the borrow checker doesn't care about the mutual reference recursion. c) Generational indices into a `Vec`. This gets used a lot for ECS systems like in Bevy, but they're very neat -- you can reassign a spot by just bumping the generation, so you don't need to worry about leaving holes or use-after-free. If you squint at it, a generational index is basically a pointer with provenance.
cjg 4y ago
Think vgel's answer to you was helpful. There are other techniques too, such as https://docs.rs/crossbeam-epoch/latest/crossbeam_epoch/ https://docs.rs/crossbeam-epoch/latest/crossbeam_epoch/ You can also use Rc/RefCell rather than Arc/Mutex if you don't need a multi-thread capable structure. You can always wrap a Mutex round the tree as a whole instead.
deleted 4y ago
[deleted]

vgel 4y ago

If you need a graph, the main approaches I see in Rust code are: a) Good ol' `Arc<Mutex>`, messy and has overhead, but easy to slap in and recreate the Java sea of objects. b) Arena allocators -- often if the graph is used for an uppercase Algorithm like spring layout or something, the graph has a singular lifetime, so not being able to individually free the nodes is fine. Then you just have `struct Node<'a> { others: Vec<&'a Node<'a>> }` and all is good, the nodes all have the same lifetime and the borrow checker doesn't care about the mutual reference recursion. c) Generational indices into a `Vec`. This gets used a lot for ECS systems like in Bevy, but they're very neat -- you can reassign a spot by just bumping the generation, so you don't need to worry about leaving holes or use-after-free. If you squint at it, a generational index is basically a pointer with provenance.

cjg 4y ago

Think vgel's answer to you was helpful. There are other techniques too, such as https://docs.rs/crossbeam-epoch/latest/crossbeam_epoch/ https://docs.rs/crossbeam-epoch/latest/crossbeam_epoch/ You can also use Rc/RefCell rather than Arc/Mutex if you don't need a multi-thread capable structure. You can always wrap a Mutex round the tree as a whole instead.

deleted 4y ago

[deleted]