Honest to a Segfault

Background

Lately, I’ve been doing a little work on closure optimization, as permitted by static analysis; i.e. the parser/compiler marks which functions can be optimized into various closure forms.

In a language that permits nested functions and functions as first-class values, there are a few things you need to ask about each function before you optimize it:

• Can it escape (leave the scope it’s defined in)?
• Does it refer to free variables (identifiers declared outside the function definition)?
• Are the free variables it refers to potentially redefined after the function definition?

Function escape (the funarg problem)

If a function can execute outside the scope in which it was lexically defined, it is said to be a "funarg", a fancy word for "potentially escaping outside the scope where it’s defined". We call certain functions in the JS runtime Algol-like closures if they are immediately applied function expressions, like so:

function outer() {
    var x = 12;
    return (function cubeX() { return x * x * x; })();
}

The function cubeX can never execute outside the confines of outer — there’s no way for the function definition to escape. It’s as if you just took the expression x * x * x, wrapped it in a lambda (function expression), and immediately executed that expression. [†]

Apparently a lot of Algol programmers had the hots for this kinda thing — the whole function-wrapping thing was totally optional, but you chose to do it, Algol programmers, and we respect your choice.

You can optimize this case through static analysis. As long as there’s no possibility of escape between a declaration and its use in a nested function, the nested function knows exactly how far to reach up the stack to retrieve/manipulate the variable — the activation record stack is totally determined at compile time. Because there’s no escaping, there’s not even any need to import the upvar into the Algol-like function.

Level 0: &outerStackFrame
Level 1: NULL
Level 2: NULL
...

Level 0: &outerStackFrame
Level 1: &cubeX
Level 2: NULL
...

function outer() {
    var x = 24;
    function innerFirst() { return x; }
    function innerSecond() {
        var x = 42;
        return innerFirst();
    }
    return innerSecond();
}

Level 0: &outerStackFrame
Level 1: &innerSecond
Level 2: NULL
...

Level 0: &outerStackFrame
Level 1: &innerFirst (encapsulates &innerSecond)
Level 2: NULL
...

Free variable references

Because JS is a lexically scoped language [¶] we can determine which enclosing scope a free variable is defined in. [#] If a function’s free variables only refer to bindings in the global scope, then it doesn’t need any information from the functions that enclose it. For these functions the set of free variables in nested functions is the null set, so we call it a null closure. Top-level functions are null closures. [♠]

function outer() {
    return function cube(x) { return x * x * x; }; // Null closure - no upvars.
}

Free variables are termed upvars, since they are identifiers that refer to variables in higher (enclosing) scopes. At parse time, when we’re trying to find a declaration to match up with a use, they’re called unresolved lexical dependencies. Though JavaScript scopes are less volatile — and, as some will undoubtedly point out, less flexible — I believe that the name upvar comes from this construct in Tcl, which lets you inject vars into and read vars from arbitrary scopes as determined by the runtime call stack: [♥]

set x 7
 
proc most_outer {} {
    proc outer {} {
        set x 24
        proc upvar_setter {level} {
            upvar $level x x
            set x 42
        }
        proc upvar_printer {level} {
            upvar $level x x
            puts $x
        }
        upvar_printer 1
        upvar_setter 1
        upvar_printer 1
        upvar_setter 2
        upvar_printer 2
        upvar_printer 3
        upvar_setter 3
        upvar_printer 3
    }
    outer
}
most_outer # Yields the numbers 24, 42, 42, 7, and 42.

Upvar redefinitions

If you know that the upvar is never redefined after the nested function is created, it is effectively immutable — similar to the effect of Java’s partial closures in anonymous inner classes via the final keyword. In this case, you can create an optimized closure in a form we call a flat closure — if, during static analysis, you find that none of the upvars are redefined after the function definition, you can import the upvars into the closure, effectively copying the immutable jsvals into extra function slots.

On the other hand, if variables in enclosing scopes are (re)defined after the function definition (and thus, don’t appear immutable to the function), a shared environment object has to be created so that nested functions can correctly see when the updates to the jsvals occur. Take the following example:

function outer() {
    var communicationChannel = 24;
    function innerGetter() {
        return communicationChannel();
    }
    function innerSetter() {
        communicationChannel = 42;
    }
    return [innerGetter, innerSetter];
}

Closing over references

In this case, outer must create an environment record outside of the stack so that when innerGetter and innerSetter escape on return, they can see both communicate through the upvar. This is the nice encapsulation-effect you can get through closure-by-reference, and is often used in the JS "constructor-pattern", like so:

function MooCow() {
    var hasBell = false;
    var noise = "Moo.";
    return {
        pontificate: function() { return hasBell? noise + " <GONG!>" : noise; }
        giveBell: function() { hasBell = true; }
    };
}

It’s interesting to note that all the languages I work with these days perform closure-by-reference, as opposed to closure-by-value. In constrast, closure-by-value would snapshot all identifiers in the enclosing scope, so immutable types (strings, numbers) would be impossible to change.

Sometimes, closure-by-reference can produce side effects that surprise developers, such as:

def surprise():
    funs = [lambda: x ** 2 for x in range(6)]
    assert funs[0]() == 25

This occurs because x is bound in function-local scope, and all the lambdas close over it by reference. When x is mutated in further iterations of the list comprehension (at least in Python 2.x), the lambdas are closed over the environment record of surprise, and all of them see the last value that x was updated to.

I can sympathize. In fact, I’ve wrote a program to do so:

var lambdas = [];
var condolences = ["You're totally right",
        "and I understand what you're coming from, but",
        "this is how closures work nowadays"];
for (var i = 0; i < condolences.length; i++) {
    var condolence = condolences[i];
    lambdas.push(function() { return condolence; });
}
print(lambdas[0]());

Keep in mind that var delcarations are hoisted to function scope in JS.

I implore you to note that comments will most likely be received while I’m sober.

Footnotes

Goals

I always feel stupid writing down goals — they seem so self-evident; however, it helps to put the work I’m doing into perspective and gives me something that I can to refer back to.

I’m also a big believer in the effectiveness of public accountability, so publishing those goals seems prudent — my notes from the JS pit are poised to help me stay motivated more than anything else.

My goals are to:

• Do my part to meet and exceed performance targets in the JS engine. It’s an exciting time with lots of healthy competition to motivate this.
• Immerse myself in language design concepts and seek out important implementation details, even if those details don’t pertain to something that I’m working on directly. This also entails some independent research and small projects to gain better understanding of foreign language concepts.
• Deliberately take time to think constructively about alternative or innovative ways to accomplish our language goals. Taking things at face value as "the way we’ve always done it" is the way that innovative things get overlooked — this is relatively easy to do with a pair of fresh eyes, but similarly difficult because you’re the team noob.

Working with compiler engineers from diverse language backgrounds, it’s prime time for sucking knowledge out of people’s heads, comparing and contrasting it, and listening to them argue with each other. Heck, just look at the concepts behind JS: an imperative, Scheme-inspired, prototypal, C-and-Java-syntax conforming language that’s irrevocably tied to a practical platform, the web. It’s bound to be a fun ride.

From start to present

I started off implementing the simpler opcodes for JaegerMonkey (JM) and getting an understanding the JM code base. Not too long into it, I was told that looking into quick-and-easy parser optimizations was a priority — somebody had reported that a significant fraction of the GMail load bar time could be attributed to JS parsing. [*]

Now, JavaScript isn’t the easiest language in the world to parse; for example, automatic semicolon insertion creates some non-traditional obstacles for generated shift/reduce parsers [†] — it effectively makes an error correction algorithm part of the normal parse procedure. The details are for another entry, but suffice it to say that our recursive descent parser code gets complex, especially due to our E4X support and some of the static analyses we perform for optimizations before bytecode emission.

In pursuing JS parser optimization I assembled a suite of parsing benchmarks from sites on the web with "large" JS payloads — I call this suite parsemark. After getting some speedups from simple inlining, I attempted a somewhat fundamental change to the parser to reduce the number of branch mispredictions, in converting it to always have a token "pre-lexed" as opposed to the prior "lex-on-demand" model. Roughly, this required adding a "there’s always a lexed token" invariant to the lexer and hoisting lexer calls/modesets from substitution rules into their referring nonterminals in the parser. The details for this are also entry fodder. Sadly, it demonstrated negligible performance gains for the increase in complexity. Sure taught me a lot about our parser, though.

The biggest performance win was obtained through a basic fix to our parser arena-allocation chunk sizing. sayrer noticed that a surprising amount of time was being spent in kernel space, so we tracked the issue down. It was frustrating to work for a few weeks on a fundamental change and then realize that multiplying a constant by four can get you a 20% parsing speedup, but I’ve certainly learned to look a lot more closely at the vmem subsystem when things are slow. I have some speedup statistics and a comparison to V8 (with all its lazy parsing and parse-caching bits ripped out), but I don’t have much faith that my environment hasn’t changed in the course of all the historical data measurements — writing a script to verify speedup over changesets seems like a viable option for future notes.

In the miscellany department, I’ve been trying to do a good amount of work fixing broken windows via cleanup patches. I’m finding it difficult to strike a balance here, since there’s a lot of modularity-breaking interdependencies in the code base — what appear to be simple cleanups tend to unravel into large patches that get stale easily. However, cleanup does force you to read through the code you’re modifying, which is always good when you’re learning a new code base.

Looking back on it, it doesn’t seem like a lot of work; of course, my hope is that the time I spend up-front getting accustomed to the codebase will let me make progress on my goals more rapidly.

Stay tuned for more JS pittage — unpredictable time, but predictable channel.

Footnotes

Footnotes

Object Models

Let’s say that you so happened to be eliminating web service dependencies with a language-specific abstraction barrier — using deferreds to represent your lazy data retrieval is a very nice abstraction. [*]

/**
 * Constructor.
 */
function RemoteAnimal(uri, kwargs) {
    var self = this;
    self._uri = uri;
    if (!kwargs) {
        return;
    }
    self._children = kwargs.children;
}
 
/**
 * Simple (synchronous) getter.
 */
RemoteAnimal.prototype.getURI = function() {
    // Simple, synchronous getter.
    var self = this;
    return self._uri;
};
 
/**
 * Asynchronous fetcher.
 */
RemoteAnimal.prototype.fetchChildren = function() {
    if (self._children !== undefined) {
        // Already fetched
        return self._children;
    }
    var deferred = dojo.Deferred();
    asyncFind('animal', // type
        'Parent = ' + self.getURI(), // query
        function callback(results) {
            var objs = dojo.map(results, self.constructor);
            self._children = objs;
            deferred.callback(self._children);
        },
        function errback(errors) {
            console && console.dir(errors);
            throw new Exception('Problem finding children');
        });
    return deferred;
};

The above uses an obvious naming convention to differentiate between synchronous and asynchronous getters — it’s important to know when a method will be returning a deferred as opposed to the desired value itself!

There is, however, a sneaky issue with RemoteAnimal.prototype.fetchChildren — can you tell what it is? You have to think pretty hard about what kinds of execution asynchronous I/O allows from the perspective of a caller.

Caveat

The key is to realize that fetchChildren could be called a whole lot of times in a row on a really slow connection (or if the caller is calling it in a for loop, which is more likely to be a problem). This will create n outstanding asyncFinds, triggering n asynchronous XMLHttpRequests, where we really only needed one. To fix this, you need to patch your code so that only one request could be outstanding at any given time, like so:

RemoteAnimal.prototype.fetchChildren = function() {
    // Property where the first deferred gets stashed.
    var flagProperty = '_childrenDeferred';
    // Property where runner-up deferreds get stashed.
    var othersProperty = '_childrenDeferredOthers';
 
    if (self._children !== undefined) {
        // Already fetched
        return self._children;
    }
    var deferred = dojo.Deferred();
 
    if (self[flagProperty]) {
        // Fetch is outstanding... latch on
        if (!(othersProperty in self)) {
            self[othersProperty] = [];
        }
        self[othersProperty].push(deferred);
        return deferred;
    }
 
    asyncFind('animal', // type
        'Parent = ' + self.getURI(), // query
        function callback(results) {
            var objs = dojo.map(results, self.constructor);
            self._children = objs;
            deferred.callback(self._children);
            delete self[flagProperty];
            if (!self[othersProperty]) {
                // No runner-ups.
                return;
            }
            // Trigger the runner-up deferreds in the order that they came.
            dojo.forEach(self[othersProperty], function(otherDeferred) {
                otherDeferred.callback(self._children);
            });
            delete self[othersProperty];
        },
        function errback(errors) {
            console && console.dir(errors);
            throw new Exception('Problem finding children');
        });
    self[flagProperty] = deferred; // Flag as outstanding
    return deferred;
}

There’s a non-trivial amount of added complexity there:

• Flag that a deferred is outstanding
• Accumulate the rest of the deferreds that need to be triggered
• Trigger them all in the order they came once the result is back
• Delete references to everything so that they can be garbage collected

The annoying part is that you can’t just tack the runner-up deferred triggers onto the original as callbacks. (That would make the construction so much easier!) Between the first and any later invocation of fetchChildren;, there may be callbacks added to the original deferred that would arbitrarily change the outcome. As a result, we have to call the other deferreds back directly with the found children from the original fetch.

It’s possible to factor out this runner-up-aggregating behavior in a highly reusable way — this code was meant to demonstrate the caveat and how to fix it. Encapsulating the runner-up triggering behavior is left as an exercise to the reader. :-)

Non-Obvious Operations with Deferreds

For educational purposes I’ve enumerated a few non-obvious operations that you can perform using deferreds. [†]

Barrier (block until all parallelized operations complete)

var deferreds = dojo.map(animals, function(animal) {
    return animal.fetchChildren();
});
var megaDeferred = DeferredList.gatherResults(deferreds);
megaDeferred.addCallback(function process(listOfChildren) {
    // "Oh yeah, there's definitely more than one children in there.."
    // Extra points if you can name the quote!
    assertEquals(listOfChildren.length, animals.length,
        'Must have equal number of animals and lists of children');
    // ...
});
return megaDeferred;

The great thing about this is that you can take embarrassingly parallel I/O operations and perform them all at once without the headaches that accompany threading.

Recursion (keep issuing I/O until a base condition is met) [‡]

RemoteAnimal.getSubtree = function(animals) {
    var all = new Array(animals);
 
    function flattenAndFilter(listOfLists) {
        var accumulator = [];
        dojo.forEach(listOfLists, function(list) {
            if (!list) { // Filter nulls
                return;
            }
            accumulator.push.apply(accumulator, list);
        });
        return accumulator;
    }
 
    function iterate(generation) {
        if (generation.length === 0) {
            return all;
        }
        var deferreds = dojo.map(generation, function(animal) {
            return animal.getChildren();
        });
        var megaDeferred = Deferred.gatherResults(deferreds);
        megaDeferred.addCallback(flattenAndFilter);
        megaDeferred.addCallback(iterate);
        return megaDeferred;
    }
 
    // Initialize
    var deferreds = dojo.map(animals, function(animal) {
        return animal.getChildren();
    });
    var megaDeferred = DeferredList.gatherResults(deferreds);
    megaDeferred.addCallback(flattenAndFilter);
    megaDeferred.addCallback(iterate);
    return megaDeferred;
}

The key to understanding this example is that returning a deferred from a callback chains that deferred in. In other words, if you return a deferred from a callback, all that deferred’s callbacks will be executed before you come back to the original. That way, we can perform recursion without worrying whether or not somebody has added more callbacks onto the initial megaDeferred returned from the getSubtree function — the chained callbacks execute right away, before any callbacks added by the caller.

Footnotes