Tuesday, October 20, 2009

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.

No comments: