4 ms·
When tree will go out of scope, their nodes memory will be reclaimed automatically ("dropping" in Rust terms) by automatic garbage collector built-in into compi
by oneshtein 2y ago
When tree will go out of scope, their nodes memory will be reclaimed automatically ("dropping" in Rust terms) by automatic garbage collector built-in into compiler: `drop(root)->drop(leaf_a),drop(leaf_b)`. However, if leaf will have reference to its parent, then an infinite loop occurs: `drop(root)->drop(leaf_a)->drop(root)->drop(leaf_a)...`
The solution is to use an alternative automatic garbage collector instead of compiler built-in: arenas, RC with weak references, or Mark&Sweep GC. Arenas have better performance, because they drop all nodes at once. The easiest way to quickly implement an arena in safe Rust is to use vector (array) of nodes and used indices instead of direct references.
- LudwigNagasena 2y agoYou've said it would be obviously wrong "even in a language with garbage collector, such as JavaScript." But, obviously, most modern GC can handle cyclic references just fine.
- oneshtein 2y agoBut even languages with Tricolour Mark&Sweep GC, which handles cyclic references just fine, it's still possible to make memory leak via a dangling reference to a node in a complex cross-linked graph, because language and GC allows that. Rust by default forbids cyclic references, by forcing to use trees, which completely avoids the problem.
- LudwigNagasena 2y agoYou can leak memory in any complex project, even if you only use safe Rust. Linux kernel uses doubly linked lists, Redis uses doubly linked lists, V8 JS engine uses doubly linked lists. Have their authors chosen something obviously wrong?
- oneshtein 2y agoRust uses double linked lists, they are not harder to implement in Rust than in any other language. Moreover, built-in borrow checker will help to implement them properly, without memory leaks or use-after-free. What is your point?
- LudwigNagasena 2y agoMy point is that it's not obviously wrong to create cyclic references.
- oneshtein 2y agoOK, it's was obviously wrong to create cyclic references few years ago.
- LudwigNagasena 2y agoBut doubly linked lists use cyclic references…
- oneshtein 2y agoDouble linked lists use double links.