justinpombrio / synless

Synless is a language-agnostic tree editor.
20 stars 2 forks source link

Use slab crate to store trees #70

Closed justinpombrio closed 1 year ago

justinpombrio commented 4 years ago

We should use the slab crate as the backing storage from trees. Right now trees are backed by a HashMap, which is very inefficient for their use case. All they really need is what slab provides:

type Key = usize;

struct Slab<T> {
    fn new() -> Slab<T>;
    fn insert(&mut self, value: T) -> Key;
    fn get(&self, key: Key) -> T;
    fn remove(&mut self, key: Key) -> T;
}

Slab stores elements in a Vec. All of these operations are O(1), and involve just an array access/mutation. With the exception of insert, just because it might have to re-allocate the underlying array, so it's O(1) amortized cost. If an element is deleted, slab will re-use that array entry.

The only downside is that slab will re-use keys. Our tree nodes are careful to never contain a reference to another node that has been deleted. Except for bookmarks, which can reference a deleted node. However, if every node stores a UUID, then the bookmark could store both the key (for fast access), and the UUID (as a check against the node being deleted). And all of the other operations could just use the key. (We could even not bother generating a UUID except when bookmarking a node, if that ends up being the only use case for the UUID.)