Allocating ValueCell objects at every function application takes a bit of time. It isn't always necessary, either. The point of creating a value cell is so that side-effects on variables have the appropriate sharing semantics. Most variables are not side effected.

It is easy to find the side effected variables by tree-walking the body of a lambda expression. If none of the lambda-bound variables are assigned to, then we can create more efficient environment structures at apply time. StaticEnvironments have this structure:

class StaticEnvironment : LexicalEnvironment
{
    readonly ValueCell [] bindings;

    internal StaticEnvironment (Closure closure, object [] initialValues)
        : base (closure)
    {
        object [] formals = closure.Lambda.Formals;
        this.bindings = new ValueCell [initialValues.Length];
        for (int i = 0; i < initialValues.Length; i++)
            this.bindings [i] = new ValueCell (formals [i], initialValues [i]);
    }

    ...
}

We define SimpleEnvironments like this:

class SimpleEnvironment : LexicalEnvironment
{
    readonly object [] bindings;

    internal SimpleEnvironment (Closure closure, object [] initialValues)
        : base (closure)
    {
        this.bindings = initialValues;
    }
    ...
}

Earlier, I posted a table of frame sizes after a long run:

[0]      99656436
[1]     817178031
[2]     219585322
[3]      45556970       
[4]       6140170       
[5]       2857104       
[6]        702372       
[7]        448574       
[8]          3080       
[9]             1       
[10]          568       
[11]          156       
[12]            3       
[13]            2       
[14]          177       
[15]            6 

More than 99% of the environment frames have three or fewer variables. Instead of holding the variable values in a vector, it is worthwhile to simply enumerate them as fields in the environment object itself. Here is SmallEnvironment1:

class SmallEnvironment1 : LexicalEnvironment
{
    readonly object binding0;

    internal SmallEnvironment1 (Closure, object binding0Value)
        : base (closure)
    {
        this.binding0 = binding0Value;
    }

There are similar classes for SmallEnvironment0, SmallEnvironment2, and SmallEnvironment3.

Although these environments are quite specialized, they account for the vast majority of environments that are dynamically created. This leads to a good performance increase. sboyer now takes a median time of 3.504 seconds. It now turns out that variable lookup is not the dominating factor in the performance. I'll discuss the next problem in the next post.