Nice code, I had thought about doing trees this way myself, but I feel that this tree is not as flexible as pointer based tree. For instance, if I would like to add one tree as a children to another tree I would have to copy whole tree node by node updating each index. This is kinda slow process. In comparison, in pointer based tree we just say that this root node is now a child of that tree.
Another example is deleting subtrees. If we were to remove some nodes with deallocating the memory, then we're removing data from vector, which in turn will move all values in a vector for each node we delete. This is like super unoptimized for a tree.
I think this solution is great for grow-only trees, and not for trees that change frequently.
Both great points. As always, you've gotta fit the data structure to the task, and this solves some problems but not all.
For point two, could you just "leak" those nodes, and then de-allocate in bulk as part of some other operation if needed? @mkm mentioned the node leaking issue, but it seems like an easier solve than the problem you describe, where each node is actually moving for each de-allocation.
As always, you've gotta fit the data structure to the task, and this solves some problems but not all.
Exactly. There are always some tradeoffs.
For point two, could you just "leak" those nodes, and then de-allocate in bulk as part of some other operation if needed?
I think leak is an option, however only if trees are consistently small, and their lifetime determines that those will be deallocated relatively soon. It is a leak after all, and leaks are more painful over time as they tend to grow.
Though in my case (not related to AOC) it wasn't an option because I parse code to a huge tree structure and then do big amount of node manipulation on reduction, which also has tree attachment as a some part of reduction in some cases, which in turn will be removed in the end. So after all reductions the resulting arena would be bloated with so many trees that the memory usage would actually be quite big. The tree would die in the end, of course, but this is not an option for really huge structures that I can theoretically parse.
Interesting. I think I'm going to keep playing with this code to see if it can be made more practical. It was so much more ergonomic than any alternative for solving the AoC problem, and took such a minimal amount of planning and code, that I feel all of these concerns could be at least mitigated if not totally resolved with a little more logic built in.
I slightly doubt, but kudos if you will come up with something. Leaking nodes seems the only performant way for removal, because if we remove items from vector, we'll have to update IDs of all nodes that were allocated after removed ID in the arena, which can be huge amount of work if we decided to remove leftmost root's child. In this sense I think HashMap is more affordable, though we're going to have to sacrifice some performance to hashing and looking up.
Heh, that was exactly what I had in mind. You're probably right.
update IDs of all nodes that were allocated after removed ID in the arena
Could this be mitigated by not indexing arena directly, and instead searching for node.idx? All edit operations would just need to ensure they're managing the stored indices properly, but to me it looks like you wouldn't ever need to change an index of a node after it's allocated. It won't match the actual index in the arena, but I'm not sure that matters.
It's not something I know anything about, but I think there are crates designed around sparse data structures as well. Assuming trade-offs but for trees expected to have long lives over which they grow and shrink a lot, could be useful.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Nice code, I had thought about doing trees this way myself, but I feel that this tree is not as flexible as pointer based tree. For instance, if I would like to add one tree as a children to another tree I would have to copy whole tree node by node updating each index. This is kinda slow process. In comparison, in pointer based tree we just say that this root node is now a child of that tree.
Another example is deleting subtrees. If we were to remove some nodes with deallocating the memory, then we're removing data from vector, which in turn will move all values in a vector for each node we delete. This is like super unoptimized for a tree.
I think this solution is great for grow-only trees, and not for trees that change frequently.
Both great points. As always, you've gotta fit the data structure to the task, and this solves some problems but not all.
For point two, could you just "leak" those nodes, and then de-allocate in bulk as part of some other operation if needed? @mkm mentioned the node leaking issue, but it seems like an easier solve than the problem you describe, where each node is actually moving for each de-allocation.
Exactly. There are always some tradeoffs.
I think leak is an option, however only if trees are consistently small, and their lifetime determines that those will be deallocated relatively soon. It is a leak after all, and leaks are more painful over time as they tend to grow.
Though in my case (not related to AOC) it wasn't an option because I parse code to a huge tree structure and then do big amount of node manipulation on reduction, which also has tree attachment as a some part of reduction in some cases, which in turn will be removed in the end. So after all reductions the resulting arena would be bloated with so many trees that the memory usage would actually be quite big. The tree would die in the end, of course, but this is not an option for really huge structures that I can theoretically parse.
Interesting. I think I'm going to keep playing with this code to see if it can be made more practical. It was so much more ergonomic than any alternative for solving the AoC problem, and took such a minimal amount of planning and code, that I feel all of these concerns could be at least mitigated if not totally resolved with a little more logic built in.
I slightly doubt, but kudos if you will come up with something. Leaking nodes seems the only performant way for removal, because if we remove items from vector, we'll have to update IDs of all nodes that were allocated after removed ID in the arena, which can be huge amount of work if we decided to remove leftmost root's child. In this sense I think
HashMapis more affordable, though we're going to have to sacrifice some performance to hashing and looking up.Heh, that was exactly what I had in mind. You're probably right.
Could this be mitigated by not indexing
arenadirectly, and instead searching fornode.idx? All edit operations would just need to ensure they're managing the stored indices properly, but to me it looks like you wouldn't ever need to change an index of a node after it's allocated. It won't match the actual index in the arena, but I'm not sure that matters.It's not something I know anything about, but I think there are crates designed around sparse data structures as well. Assuming trade-offs but for trees expected to have long lives over which they grow and shrink a lot, could be useful.