Wednesday, July 15, 2009

Variable lookup

After the changes I mentioned in an earlier post I find that about 63% of all variable references are to arguments in the immediately enclosing lambda. In fact, more than half the variable references are to the first argument in the argument list. I'm going to guess that most of the remaining variable references end up referring to global variables, but I could be wrong.

It also turns out that most of the argument references are subproblems of PrimitiveCombination1 and PrimitiveCombination2. Enabling specialization of these forms should be a big win.

Without specialization, these are the steps to evaluating a PrimitiveCombination1:
public override bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    Control unev0 = this.arg0;
    Environment env = environment;
    object ev0;
    while (unev0.EvalStep (out ev0, ref unev0, ref env)) { };

    if (ev0 == Interpreter.UnwindStack) {
        ((UnwinderState) env).AddFrame (new PrimitiveCombination1Frame0 (this, environment));
        answer = Interpreter.UnwindStack;
        environment = env;
        return false;
    }

    // It is expensive to bounce down to invoke the procedure
    // we invoke it directly and pass along the ref args.
    if (this.method (out answer, ev0)) {
        TailCallInterpreter tci = answer as TailCallInterpreter;
        if (tci != null) {
            answer = null; // dispose of the evidence
            // set up the interpreter for a tail call
            expression = tci.Expression;
            environment = tci.Environment;
            return true;
        }
        else
            throw new NotImplementedException ();
    }
    else return false;
}
Now if we know that the argument to the primitive is simply going to be an argument bound in the enclosing lambda expression, we can bypass the code that evaluates it and just fetch the value:
public override bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    if (this.method (out answer, environment.Argument0Value)) {
        TailCallInterpreter tci = answer as TailCallInterpreter;
        if (tci != null) {
            answer = null; // dispose of the evidence
            // set up the interpreter for a tail call
            expression = tci.Expression;
            environment = tci.Environment;
            return true;
        }
        else
            throw new NotImplementedException ();
    }
    else return false;
}