Rust data structures with circular references
eli.thegreenplace.net
eli.thegreenplace.net
> So how can a reference in a child assume the same lifetime? It can't.
Well actually, it can, because the owned Struct itself (Node) can outlive any borrow. You won't be able to mutate the parent though, as you can't mutate any value that has an active immutable borrow. That's the problem: you can't add the child node as adding it would mutate the parent and the there's an active immutable borrow (in the child node).
This reddit comment[0] has one possible solution[1] to this problem: not saving all of those parent references in the node itself, only adding when you're retrieving it. It also seems a lot better since there's less data in-tree to change if the structure itself changes.
[0] https://old.reddit.com/r/rust/comments/qstlto/rust_data_stru... [1] https://play.rust-lang.org/?version=stable&mode=debug&editio...
Slotmap is essentially the Vec + indices solution, while allowing memory to be reused. It is still completely safe, as it automatically versions each slot, and checks the version contained in the key when indexing.
For iteration however, there can be holes that need to be ignored, if the current number of elements in the slotmap is significantly lower than the the maximum capacity. If iteration needs to be very fast (for e.g. game engines) I do have a solution for that, which is the DenseSlotMap. It uses one extra layer of indirection for random access, but stores the actual data values contiguously in a vector, thus iteration is always fast.
E.g. to benchmark removals they used `container.remove(index)` for data structures that support indices but for slotmap they used `slotmap.remove(keys[index])` which unfairly adds another layer of indirection.
DenseSlotMap sort of can. It still can't reclaim the memory used by empty slots for the same reason (at a cost of 8 bytes per slot), but can reclaim the memory used by the actual elements stored.
So if you store 1 million items at one point in a DenseSlotMap, and then clear them all and then shrink to fit (which is actually missing from the API, but I'll fix that soon) you will waste 7.6 megabytes on the empty slots but nothing on the actual data that used to be stored.
1. The name isn't particularly catchy or descriptive. It is the correct name for the data structure, but not too many people know the data structure.
2. People don't even know what they're missing. It's not a very Google-able problem to begin with. Slotmap provides an interesting solution to (circular) ownership and safe allocator / weak pointer design problems, but people don't recognize that they're having them or that slotmap could help.
As an example of this, the doubly linked list example (https://github.com/orlp/slotmap/blob/master/examples/doubly_...) can safely remove nodes from the linked list given their handle, in O(1), even from the middle, completely safely and correctly, even in the presence of double deletions or ABA memory re-use. You can't replicate this with just pointers, without introducing heavy refcounting solutions.
My goal in the post was to avoid "just use this crate" approaches, because clearly there are dozens of crates that could help with this... even crates that implement BSTs :-) The goal was to look at the underlying implementation of such crates, and as the other comment pointed out it seemed like slotmap and others used approaches that mapped to one of the three I outlined in the post.
I very much appreciate this sentiment and it inspires me to actually think about blogging again. Thank you.
You can't do this with a Vec<Node> (unless you can create all the nodes up front before initializing them) because resizing the Vec would invalidate references into it.
But if you use a different "allocator" that leaves its contents in-place, you can make all the links into references with a single lifetime.
The remaining tricky part is, still, deallocation- you can't fully free a node in a structure like this because they all share a lifetime. But you can put it on a free list for future node allocations, with similar risks to the handle approach.
E.g., something like Bumpalo?
#[derive(Debug)]
struct Node {
data: i32,
left: Option<Box<Node>>,
right: Option<Box<Node>>,
parent: Option<*mut Node>,
}
impl Node {
pub fn new_root(data: i32) -> Self {
Node { data, left: None, right: None, parent: None, }
}
pub fn new_leaf(data: i32, parent: *mut Node) -> Self {
Node { data, left: None, right: None, parent: Some(parent), }
}
}
#[derive(Debug)]
struct Tree {
root: Option<Node>,
}
impl Tree {
pub fn new() -> Self {
Tree { root: None }
}
pub fn insert(&mut self, data: i32) -> bool {
match self.root {
Some(ref mut node) => Tree::insert_at(node, data),
None => {
self.root = Some(Node::new_root(data));
true
}
}
}
fn insert_at(current_node: &mut Node, data: i32) -> bool {
match (
current_node.left.as_deref_mut(),
current_node.right.as_deref_mut(),
) {
_ if data == current_node.data => false,
(Some(left_node), _) if data < current_node.data => Tree::insert_at(left_node, data),
(None, _) if data < current_node.data => {
let new_node = Node::new_leaf(data, current_node);
current_node.left = Some(Box::new(new_node));
true
}
(_, Some(right_node)) => Tree::insert_at(right_node, data),
(_, None) => {
let new_node = Node::new_leaf(data, current_node);
current_node.right = Some(Box::new(new_node));
true
}
}
}
}
pub fn main() {
let mut tree = Tree::new();
let data = [5, 3, 65, 123, 6, 11, 3, 1, 5, 42];
for i in data {
tree.insert(i);
}
println!("{:?}", tree);
}Rebalancing of the left branch is a bit complicated, so I implemented just detach() method, which takes out the element with it subbranches from the tree. From there, you can implement your favorite deletion method. For production, I will just mark a node as deleted and then compact the tree later, to have predictable timings.
One gains persistent data structures. In many problems, "reuse" is far more efficient than carving out each new instance from scratch.
I've never understood the evangelists that claim one can't learn functional programming after any exposure to conventional programming, but perhaps the prejudices run deeper than I've recognized. How does one characterize a rejection out-of-hand of persistent data structures?
"One-use plastic bag syndrome"
People ignore existing work (at least at first), and assume they can make it simpler themselves, because they're surprised it _needs_ to be sophisticated.
EDIT: That said, the article does a great job of explaining the problems and the potential solutions.
(I think my problem actually just came down to the lifetime on the object holding the tree itself and the way I was instantiating nodes; but when those lifetime compiler warnings popped up my eyes would glaze over and I knew it was time to put rust down for the day)
I imagine Haskell programmers have a step up because the Monad system is significantly less forgiving than SML’s look-the-other-way approach to side effects, and in this sense Haskell and Rust are more similar than many other functional languages.
In Rust the "problem" is that the safe subset of the language enforces ownership rules, which make directly representing circular pointer structures impossible. Of course, you can use "unsafe" and it becomes as simple as in C. This tradeoff is well known since the inception of Rust.
In Haskell, the "problem" is that all functions need to be pure, so if you need to mutate a data structure, you actually have to create a new instance, sharing the bulk of the structure of the previous instance to be efficient.
This is not the same thing, but you seem to think it is. In Rust, persistent data structures still use reference counting to manage lifetime of the objects inside the structure (see rpds), which is also what one of the solutions listed here does.
They are only different superficially.
The deeper problem here is they both assume that "a new, valid value can only reference old, existing values". (For the sake of simplicity, let's pretend Haskell does not have laziness for a moment.) This is reasonable in almost any language because it enables easy inductive reasoning. Rust forbids circular references exactly for this reason, the whole borrow check builds on this principle: a new pointer becomes invalid when the old pointer becomes invalid. You cannot create them in Haskell either due to this very reason, if there is no laziness.
Techniques in Haskell, like tying the knot, work just because laziness makes it possible to reference values in the future. Unfortunately, it also creates possibilities for bottoms, which renders it unusable for a sound proof system -- Rust cannot do the same thing because borrow check should be sound and terminating.
It's easy in C++ because C++ does not guarantee validity of objects. You know, NULL is _always_ an invalid pointer. Rust and Haskell both guarantee that a constructed object is always valid. (ofc, only in most cases where the escape hatches are not used.)