Hunting bugs

My version of MIT Scheme appears to be able to self-host. I can bootstrap it from the original Scheme, load the syntaxer, re-syntax everything and then boot from the new files.

I did find a bug in how internal definitions are handled when pretty printing, so I'm on the hunt now.

Dry spell

I've been in a bit of a dry spell as far as blogging is going. I think I'll have some more news soon, though.

The comment spammers are getting more clever. I found one today that almost seemed relevent (except for the link to cheap drugs). I hope I don't have to turn on comment moderation.

update

I've tweaked and optimized things in my interpreter so that the median time for sboyer.scm is now at 2.1 seconds (down from the baseline of 6.56 seconds). It wouldn't be too hard to push it below 2 seconds with some more specialization of the conditionals, but that's not where I want to go.

Now that flat environments are working fairly good, the bottleneck has shifted. The top three items on the ‘top of stack’ histogram are the primitive procedures CAR, PAIR?, and NULL?. Let's look at the code for PrimitiveCombination1:

 
public override bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    // Evaluate the argument.
    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;
    }

    // Call the primitive.
    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;
}

The method for CAR is this:

public static bool PrimitiveCar (out object answer, object arg0)
{
    answer = ((Cons) arg0).Car;
    return false;
}

There's quite a bit of noise in that code, so here is the main code path:

bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    // Evaluate the argument.
    Control unev0 = this.arg0;
    Environment env = environment;
    object ev0;
    while (unev0.EvalStep (out ev0, ref unev0, ref env)) { };
    if (ev0 == Interpreter.UnwindStack) { ... }

    // Call the primitive.
    if (this.method (out answer, ev0)) { ... }
    else return false;
}

The while statement is the tail-recursion trampoline. The immediately following conditional is there to support first-class continuations. The method is expected to stuff its result in answer and return false, unless it needs to make a tail-recursive call, in which case it returns true.

This is pretty general, and it has to be if we are going to support primitives like call-with-current-continuation, but the number one primitive procedure is CAR, and we can handle that one a bit more efficiently. The first thing we need to do is inline the call to CAR:

bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    // Evaluate the argument.
    Control unev0 = this.arg0;
    Environment env = environment;
    object ev0;
    while (unev0.EvalStep (out ev0, ref unev0, ref env)) { };
    if (ev0 == Interpreter.UnwindStack) { ... }

    // Attempt to cast.
    Cons theCell = ev0 as Cons;
    if (theCell == null) {
        ... enter error handler ...
        }
    else {
        answer = theCell.Car;
        return false;
    } 
}

This avoids several operations. We no longer push ev0 as an argument just to pop it off in the primitive, and we no longer return a flag for a conditional branch. This is about half of the work.

The other half is in evaluating the argument to CAR. The debug version shows that the argument to CAR is usually bound in an argument position in the enclosing lambda. If that is the case, then there is no need for the tail-recursion trampoline or the continuation handling code. We can just fetch the argument.

bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    // Attempt to cast.
    Cons theCell = environment.ArgumentValue(this.argumentOffset) as Cons;
    if (theCell == null) {
        ... enter error handler ...
        }
    else {
        answer = theCell.Car;
        return false;
    } 
}

If the primitive cannot throw an error (for example, PAIR?), it is even simpler:

public override bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    answer = environment.ArgumentValue (this.offset) is Cons;
    return false;
}

This code takes almost a negligable amount of time.

Unfortunately, specializing on the primitive procedure and the argument type like this requires a lot of code. Each one-argument primitive can be specialized in at least six different ways, and each way is its own separate class. C# does not have macros and templates don't quite work for this sort of thing. The alternative is some code-generation mechanism, but I've been too lazy to automate that (I've been expanding these things by hand). On the other hand, the unspecialized mechanism is not unreasonable if it isn't called to often, so by specializing only a handful of the top primitives we get a lot of performance improvement for very little work.

MIT-Scheme has reflective operations for manipulating its own SCode. In order to maintain compatiblity with these, the specialized primitives inherit from PrimitiveCombination1. The code for EvalStep is overridden, but we retain the rest of the class. This allows the Scheme level to reflect on this code as if it were unoptimized code. A good example of this is the pretty printer. When it encounters an optimized PrimitiveCarA (primitive CAR of an argument), it treats it just like a PrimitiveCombination1 with an operator of CAR and an argument of some Variable.

Just by optimizing CAR, CDR, PAIR?, and NULL?, the median time for sboyer drops to 2.62 seconds.

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.

Oh yeah, those flat environments

I did finally get flat environments working the way I want, and then refactored to be simpler and clearer. The basic idea is that rather than chasing down environment frames looking for a binding, we keep the lexical variables in a vector. A closure now looks like this:

    class Closure
    {
        protected readonly Lambda closureLambda;
        protected readonly Environment closureEnvironment;
        protected readonly ValueCell [] staticBindings;
        ...
    }

When we need the value of a lexical variable, we find it at a precomputed offset in the staticBindings. (They are ‘static’ because the location of the binding cell doesn't move.) When we create a closure, we need to copy some of the static bindings from the parent environment. For this we need a StaticMapping.

class StaticMapping
{
    int [] offsets;
    ....
}

The StaticMapping is stored in the StaticLambda from which we construct the StaticClosure. We copy the bindings when we construct the StaticClosure.

bool EvalStep (out object answer, ref Control expression, ref Environment environment)
{
    answer = new StaticClosure (this, environment.BaseEnvironment, environment.GetValueCells (this.staticMapping));
    return false;
}

And the code for GetValueCells is this:

internal override ValueCell [] GetValueCells (StaticMapping mapping)
{
    int count = mapping.Size;
    ValueCell [] cells = new ValueCell [count];
    for (int index = 0; index < count; index++) {
        int o = mapping.GetOffset(index);
        if (o < 0)
            cells [index] = this.bindings [(-o) - 1];
        else
            cells [index] = this.Closure.StaticCell (o);
    }
    return cells;
}

The StaticMapping encodes argument bindings as negative numbers and static bindings as positive numbers. The appropriate cells are copied from the parent environment.

Going to flat environments makes a substantial improvement. Our baseline median time for the sboyer benchmark was 6.596 seconds. With flat environments, the median time is now 4.346 seconds.

Variable lookup is no longer the bottleneck in the interpreter. Procedure application is. It was worth the tradeoff, but let's see what procedure application involves:

bool Apply (out object answer, ref Control expression, ref Environment environment, object [] args)
{
    if (args.Length != this.arity)
        throw new NotImplementedException ();
    expression = this.closureLambda.Body;
    environment = new StaticEnvironment (this, args);
    answer = null; // keep the compiler happy
    return true;
}

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]);
}

The big problem is that we are allocating ValueCells for the argument bindings. We'll deal with this next.

Short solution

No takers? Oh well. Here's the solution for yesterday's short exercise.

The amount of remote data is small. We only have 10K records and only add a handful a day. This will all fit in memory just fine.

Now imagine that the cache is a bucket with a small hole in it. Over time, as the cache entries become stale, the cache slowly empties. We can calculate a long-term rate at which entries expire. (This isn't actually what happens, though. The entries expire en masse, but let's pretend.) If we continue to fill the bucket at the same rate as the bucket empties, it will always be full. Any slower and the bucket will empty. Any faster and it will overflow.

The remote database can deliver one entry in 150ms, but we don't want to saturate that connection (there are other clients and we presumably want to perform work other than cache refresh). So let's dedicate 2% of the client bandwidth to the cache. If we fetch no more than one entry every 50 * 150ms = 7.5 seconds, we'll remain under 2%. Of course this means that we cannot let the records expire at a rate faster than this. If our cache has 10K records and they expire at a rate of one record every 7.5 seconds, the cache will be empty in 75K seconds, or 20.8 hours. We set the expiration time on an entry at a tad more than that and we're all set. If 20.8 hours is unacceptably stale, we can shorten it by reserving more bandwidth for the cache. There is a limit, though. With a handful of clients each consuming 2%, there would be a small constant load on the server. If we increased each client to consume 10-12%, the server will be spending most of its time servicing client caches.