C# How to pool the objects of a node tree efficiently?

Question

I have a node class that contains only value type properties, and one reference type: it's parent node. When performing tree searches, these nodes are created and destroyed hundreds of thousands of times in a very short time span.

public class Node
{
   public Node Parent { get; set; }
   public int A { get; set; }
   public int B { get; set; }
   public int C { get; set; }
   public int D { get; set; }
}

The tree search looks something like this:

public static Node GetDepthFirstBest(this ITree tree, Node root)
{
   Node bestNode = root;
   float bestScore = tree.Evaluate(root);

   var stack = new Stack<Node>();
   stack.Push(root);

   while(stack.Count > 0)
   {
      var current = stack.Pop();

      float score = tree.Evaluate(current);
      if (score > bestScore)
      {
         bestNode = current;
         bestScore = score;
      }

      var children = tree.GetChildren(current);
      foreach(var c in children) { stack.Push(c); } 
   }

   return bestNode;
}

Because this is done in a Mono runtime that has a very old GC, I wanted to try and pool the node objects. However, I am at a loss on how to know when a node object is safe to return to the pool, since other nodes that are still in use might reference it as a parent. At the end of the search, the best node is returned and a list of nodes is formed by walking back through its ancestors. I have full control over how the nodes are created inside the tree, if that's useful.

What options could I try and implement?

Answer 1

So, fortunately, if you're doing a Depth-First-Search, which you appear to be, this is a bit easier. Any time you reach a leaf node, there are two possibilities: that leaf node is part of the current deepest tree, or it's not.

If it's not, that means it's safe to return this node to the pool. If it is, that means we can return any nodes in our old tree back to our pool that are not in our own ancestor chain.

Now, if we're not a leafnode, we don't know if we can be freed until after we've finished checking our children. then, once all our children are checked, we find out if any of our children said they were the current best. if so, we keep ourselves

this does mean we're doing quite a bit more checking.

Here's some sudo code:

List bestNodes;

bool evalNode(node, score)
{
    if (childCount == 0)
    {
        if (score > bestScore)
        {
            bestScore = score;
            bestNode = node;
            bestNodes.Add(node);

            return true;
        }
        else
        {
            freeNode(this);

            return false;
        }
    }
    else
    {
        bool inLongest = false;
        foreach (child in children)
        {
            inLongest = evalNode(child, score + 1) || inLongest;
        }

        if (!inLongest)
        {
            freeNode(node);
        }
        else
        {
            free(bestNodes[score]);
            bestNodes[score] = node;
        }             

        return inLongest;
    }
}