Look! Up in the environment!

Variable lookup is right up there with continuation management as an important performance bottleneck. In one benchmark, I measured 2.9 billion evaluations of which 991 million (34%) of them were variable lookups. A good chunk of compiler optimizations revolves around getting the variables to where they need to be as quickly as possible and keeping them in easy to find places.

My interpreter uses the standard `environment model' of evaluation where a linked chain of lexical environment chains are maintained during evaluation. Every variable lookup goes through a `deep search' of the frames looking for a binding with a matching name. Needless to say, this is not blazingly fast. There are two parts to solving this. First is to reduce the need for the deep search, second is to optimize the fast path.

MIT Scheme supports first-class environments. The special form the-environment returns the lexical environment at the point of invocation. The returned environment can be used as an argument to eval and that's where the trouble begins. If eval is called, the user is going to expect that the code will run in a context with the same bindings visible as where the environment was captured. This means we cannot move or collapse the environment frames because it may cause changes visible to the user. Even worse, if the user evals a define expression, or loads a file, it may inject bindings that were not previously visible. This means we cannot even cache the locations of the variables. The flexibility of first-class environments comes with a heavy cost. On the other hand, this flexibility is hardly ever used, so we end up paying this cost to no advantage.

So how do we fix this? First, because (the-environment) is the only documented way to obtain a first-class environment, we can walk the SCode and determine whether a first-class environment will be needed. I do this when I construct an SCode lambda expression. If the body contains a call to (the-environment), I construct a StandardLambda object, but if it does not, I construct a StaticLambda object. A StandardLambda, when evaluated, constructs a StandardClosure. A StandardClosure, when applied, constructs a StandardEnvironment. A StandardEnvironment must be layed out exactly as specified by the source code and variable lookups must do a deep search because the user might inject bindings via define or load.

A StaticEnvironment however, has an important property: because the user cannot use load or eval with it (he can't name the object to pass it as an argument, so this does not create a user-visible restriction), we know that there will not be incremental definitions that could hide the bindings in the environment. We know the lexical depth and offset of all variables bound in a StaticEnvironment.

So the first task is to identify and separate StandardLambda and StaticLambda instances.