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.
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.