Unbounded memory usage with reuse_tree ?

[fredcallaway]

More of a question than an issue. It seems to me that when the tree is reused, there is no "pruning" of the not-taken branches (i.e. nodes for states and actions that are probably not reachable from the new state). Is that correct?

It seems like it would be difficult to do this pruning in an efficient way because the node information is stored in a central data structure (MCTSTree) and the prunable nodes will have non-contiguous ids. If we had instead stored node information (Q, N, children) within each node data structure, it would be easy to just drop references and the GC would handle that pruning automatically. So I'm curious: are there substantial performance gains to the centralized storage mechanism?

Thanks for helping me understand!

[zsunberg]

Hi @fredcallaway, good question!

Yes, there are substantial performance benefits. The issue is that (Q, N, children) would have to be stored in a mutable struct and mutable structs are allocated on the heap, which is much slower. In the centralized structure, new memory for nodes is just allocated at the end of arrays, which tends to be much faster.

In our experience, reusing the tree provides only a small benefit, so it is not a problem to just get rid of the whole tree.

I have thought a lot about other ways to do it: https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/10 , but have never gotten around to actually trying anything. (note that using arenas from that thread would not fix the re-use tree memory problem because the garbage collector is not in charge of that memory)

[fredcallaway]

Ah okay, that makes sense. Thanks for the help!