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

i have node class contains value type properties, , 1 reference type: it's parent node. when performing tree searches, these nodes created , destroyed hundreds of thousands of times in short time span.

public class node {    public node parent { get; set; }    public int { get; set; }    public int b { get; set; }    public int c { get; set; }    public int d { get; set; } } 

the tree search looks 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 done in mono runtime has old gc, wanted try , pool node objects. however, @ loss on how know when node object safe return pool, since other nodes still in use might reference parent. @ end of search, best node returned , list of nodes formed walking through ancestors. have full control on how nodes created inside tree, if that's useful.

what options try , implement?

so, fortunately, if you're doing depth-first-search, appear be, bit easier. time reach leaf node, there 2 possibilities: leaf node part of current deepest tree, or it's not.

if it's not, means it's safe return node pool. if is, means can return nodes in our old tree our pool not in our own ancestor chain.

now, if we're not leafnode, don't know if can freed until after we've finished checking our children. then, once our children checked, find out if of our children said current best. if so, keep ourselves

this mean we're doing quite bit more checking.

here's 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;     } }