CODEWITHSUNDEEP
c#memorylambdaclosures
argyle
argyle

Reputation: 1339

Memory behavior of recursivity using Lambda

I'm doing a preorder traversal of a binary tree using the following code:

        public void PreorderTraversal(Action<BinaryTreeNode<T>> act) {
            Action<BinaryTreeNode<T>> InnerTraverse = null;
            InnerTraverse = (node) => {
                if (node == null) return;
                act(node);
                InnerTraverse(node.Left);
                InnerTraverse(node.Right);
            };
            InnerTraverse(this.Root);
        }

Is this approach of using a locally defined lambda to recurs over the tree worse from a performance perspective in relation to simply defining the InnerTraverse function as a method on the BinaryTree class, which is where the PreorderTraversal function itself is defined?

Upvotes: 0

Views: 43

Answers (1)

Ivan Stoev
Ivan Stoev

Reputation: 205649

The sample method will be translated by the compiler to something like this:

class Closure
{
     public Action<BinaryTreeNode<T>> act;
     public Action<BinaryTreeNode<T>> InnerTraverse;

     public void InnerTraverseFunc(BinaryTreeNode<T> node)
     {
         if (node == null) return;
         this.act(node);
         this.InnerTraverse(node.Left);
         this.InnerTraverse(node.Right);
     }
}

public void PreorderTraversal(Action<BinaryTreeNode<T>> act)
{
    var c = new Closure();
    c.act = act;
    c.InnerTraverse = new Action<BinaryTreeNode<T>>(c.InnerTraverseFunc);
    c.InnerTraverse(this.Root);
}

As you can see, the cost is one new type per T, 2 heap allocations per each root method call plus using delegate calls vs direct calls with regular static recursive method.

IMO the additional runtime cost is not so big, but at the same time since there is absolutely no benefit of using recursive lambda in such scenarios, better off to be avoided.

Upvotes: 1

Related Questions