Wednesday, November 5, 2008

Advanced Topics in Inefficiency: Anonymous Methods

This is the first in what may be a series of posts on various theoretical (and not so theoretical) corner cases in common code. Despite being obtuse, these issues are useful to explore both to avoid inefficiencies and to better understand what's happening behind the code. Today's topic: anonymous methods.
class Foo()
{
    void Bar()
    {
        var thing1 = new Thing();
        var thing2 = new Thing();

        DoSomeStuff (() => thing1.Shimmy());
        DoOtherStuff(() => thing2.Shake());
    }
}
There is a potential memory problem with this method. It's not obvious from looking at the code, but both things must be garbage collected together. As long as there is an active reference to one, the other will live on as well. If 'Thing' is a heavy type, this could keep significant memory from being reclaimed on the heap. To better understand, let us look at how the C# compiler handles anonymous methods.

The above example demonstrates "local variable capture." This means local variables from the enclosing method body can be used inside closures (such as the two lambdas above). To accomplish this, the C# compiler shunts the values of the local variables to an object. The type of the object is generated by the compiler. In essence, the compiler turns the above code into this:
class Foo()
{
    class GeneratedTypeForMethodBar
    {
        public Thing thing1;
        public Thing thing2;

        public void AnonymousMethod1()
        {
            thing1.Shimmy();
        }

        public void AnonymousMethod2()
        {
            thing2.Shake();
        }
    }

    void Bar()
    {
        var closure_object =
            new GeneratedTypeForMethodBar();
        closure_object.thing1 = new Thing();
        closure_object.thing2 = new Thing();

        DoSomeStuff(closure_object.AnonymousMethod1);
        DoOtherStuff(closure_object.AnonymousMethod2);
    }
}
This is actually a very clever way of achieving local variable capture since it makes use of the CLI's pre-existing garbage collector to clean up the captured variables. The problem is, the compiler shunts all local variables to a single object. In our above example, the two anonymous methods do not reference any of the same local variables, but both local variables are stored in the same object. This can lead some captured variables to become prisoner variables: they are no longer needed, but they cannot be garbage collected. Suppose that our 'DoSomeStuff' method just invokes the delegate and returns. No problem. But now suppose that our 'DoOtherStuff' method holds on to the delegate, perhaps planing to invoke it later. Or suppose we were to return the second lambda, allowing the caller to hold the delegate as long as they please. That delegate holds a reference to the 'closure_object' which holds a reference to both Things, even though that delegate just needs 'thing2'. There is no way for any code to reach 'thing1' but it won't be garbage collected until we're done with 'thing2'.

Solution?

Well, we could modify the compiler to generate a type for each set of local variables that appear in only one anonymous method, like so:
class Foo()
{
    class GeneratedTypeForMethodBar1
    {
        public Thing thing1;

        public void AnonymousMethod()
        {
            thing1.Shimmy();
        }
    }

    class GeneratedTypeForMethodBar2
    {
        public Thing thing2;

        public void AnonymousMethod()
        {
            thing2.Shake();
        }
    }

    void Bar()
    {
        var closure_object1 =
            new GeneratedTypeForMethodBar1();
        closure_object1.thing1 = new Thing();

        var closure_object2 =
            new GeneratedTypeForMethodBar2();
        closure_object2.thing2 = new Thing();

        DoSomeStuff(closure_object1.AnonymousMethod);
        DoOtherStuff(closure_object2.AnonymousMethod);
    }
}
This poses problems as well. First of all, we are instantiating two (or more) generated-type objects rather than one. Object instantiation is not cheap and that could potentially slow down certain code. Also, this approach cannot be used to optimize more complex scenarios. Suppose we have five anonymous delegates, each referencing some of seven local variables like so: a {1 2} b {2 3} c {3 4 5} d {1 5 6} e {6 7}. In these situations we must default to the one-compiler-generated-type-for-everything approach.

Ultimately, the lesson here is just to be aware of these potential issues. If you find via profiling that objects are not being garbage collected and you make heavy use of anonymous methods, you might want to examine your closures to make sure this isn't causing the problem.

And what do people think about modifying the compiler as proposed above? Also, anyone who comes up with a better mechanism for local variable capture gets cool points. Double points if your solution doesn't require VM changes.

P.S. Thanks to Michael for help with this post.