Sunday, June 21, 2009

Serialization, etc.

In order to speed up my interpreter, I'm playing around with specializing certain elements of the SCode. For instance, the form
(+ x 3)
would normally involve three sub-evaluations. One to lookup +, one to lookup x, and finally one to evaluate the literal constant 3. The EvalStep looks like this:
        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;
                    throw new NotImplementedException ();
            else return false;
With the appropriate configuration flags set, the constructor for PrimitiveCombination2 would delegate to PrimitivePlusFixnum, PrimitivePlusFixnum would notice that x is (for example) lexically bound in the current frame, and that 3 was a quoted constant. It would (under these conditions) construct a PrimitivePlusFixnumA0Q. The EvalStep for this is:
        public override bool EvalStep (out object answer, ref Control expression, ref Environment environment)
            answer = (int) environment.Argument0Value + this.rand1Value;
            return false;
This, you can imagine, is a fair amount faster.

Now I want it to be the case that when I change the configuration flags I get better or worse performance depending on what I allow to be optimized. So when I turn off the EnablePrimitiveCombination2Optimization flag, I want the slow, generic form of the SCode to be constructed. To make this work correctly, when I serialize the SCode, I always serialize it as if it were the base form. When it is deserialized and the constructor is called, it has the choice of returning the optimized or non-optimized version as called for by the flags.

That's the theory, anyway.

There are a bunch of problems, though. In C#, like in Java, the contructor for an object must return an object of the type constructed. If I call new PrimitiveCombination2, there is no way to return a PrimitivePlusFixnumA0Q instance instead. There are standard workarounds for this problem — ‘factory’ classes are one way — I decided to use ‘smart constructors’. Each SCode class has a static Make method that is called to instantiate the class. The specialized classes are subclasses of the base, unspecialized version, so Make checks the flags and simply dispatches to the appropriate Make method for the specialized class (or calls new if the flags do not permit optimization).

Of course the default serialization protocol doesn't know about this, so I have to patch it. The base class for each unoptimized SCode class overrides the default deserializer. The new serializer actually serializes a special ‘deserializer’ object. Later, when the SCode is deserialized, an instance of the special deserializer is created. Then, during the fix-up phase of deserialization, the special deserializer calls the Make method of the base class, and at that point the appropriate specialized object is created.

This actually sort of works. But here's a problem. Almost all of the SCode is immutable. There is no reason to mutate the SCode (the exception being adding advice to lambdas), so we can avoid the immense amount of complication that mutable SCode would entail (consider mutating some SCode that was currently being run in another thread). If the SCode is immutable, then there can be no cycles in the SCode graph. (Another benefit. SCode analyzers can assume the input is a finite acyclic directed graph rather than something more complex.) Since the SCode is immutable, the SCode graph must be constructed from bottom up. The contents of a node must exist before the node itself is constructed. Under normal conditions, like when reading a file, this is naturally the case. But deserialization isn't a normal case.

The default serialization will in fact traverse the data structure in depth-first order, so when the object is reconstructed its components will already have been deserialized. But I don't want to use the default serialization because I want to change what nodes are constructed depending on the configuration flags. The specialized deserializers however are not necessarily called in the correct order. The subcomponents of the objects ought to exist, as far as I can determine, but they are not necessarily initialized. This causes problems.

When I create a lambda object I do a sanity check to ensure that there are no duplicates in the argument list. This check fails on deserialization. The argument list seems to be a vector of nulls at the point where I deserialize the lambda, and then it gets fixed up before the graph structure is returned to the caller. It is easy enough to turn off the sanity check (which I in fact did), but this throws a monkey wrench into my plan for using smart constructors. How can the smart constructor analyze the body of the lambda expression without knowing what the argument list is?

This makes no sense to me. Why does the deserializer defer fixup of the lambda argument list until after the fixup of the lambda? More importantly, how can I enforce the deserialization order I want (I don't see a means to override the deserialization of built-in objects like vectors)?

And there is a lurking bug having to do with deserializing the entire heap. SCode files are not circular, but the heap most definitely is. And under my current design, the type of a closure is related to the type of the lambda it is closed over, and the type of an environment is related to the type of closure that created it. If these objects are not instantiated in the right order upon deserialization, I won't be able to keep the SCode consistent with the envionment structure.

I guess I'll have to figure that out soon.

No comments: