The Ins and Outs of Invalidation

One of the primary goals of JIT engines for dynamic languages is to make high-level code run fast by compiling it into efficient machine code.  A key property of this, however, is that the compiled code for any piece of JavaScript must behave exactly the same at runtime as the interpreted code for that JavaScript would have behaved.  In a nutshell, providing efficiency while maintaining correctness is the fundamental problem faced by JIT compilers.

This efficiency is tricky to achieve because dynamic languages like JavaScript are highly polymorphic: any variable can hold values of any type, and in the general case, the runtime cannot know ahead of time what type a particular value will have. For example, even if the program will always add two integers together at a particular place in the code, the engine has to allow for the possibility that a non-integer value might unexpectedly show up.

There are two broad techniques which can be used to deal with this challenge.  The first is guarding, where the engine generates machine code that checks its assumptions before executing the code that relies on those assumptions.  For the adding example above, the engine will generate machine code to do integer addition, but it will make sure to prefix that code with checks which ensure that the two values being added are actually integers.  If the checks fail, the machine code jumps to a slowpath that handles the uncommon case in a general way.  If the check succeeds, the fastpath (or optimized) machine code is executed.  The expectation is that the checks will succeed most of the time, and so the fastpath will be executed most of the time.

While guarding is a useful technique, it imposes a performance penalty.  Checking assumptions takes time, and having those checks in hot code can be a significant performance drain.  The second technique for emitting efficient code while retaining correctness is invalidation.  That’s what I’m going to talk about in this post.  I’m going to use SpiderMonkey’s newly added JIT engine, IonMonkey, to illustrate my examples, but aside from the details the overall strategy will apply to most JIT engines.

Invalidation at 10,000 Feet

The key idea behind invalidation is this: instead of making our jitcode check an assumption every time we are about to do something that relies on that assumption, we ask the engine to mark the jitcode as invalid when the assumption becomes false.  As long as we take care never to run jitcode that’s been marked invalid, then we can go ahead and leave out the guards we would have otherwise added.

Let’s take a look at a simple example to get started.  Here’s a small JavaScript program that computes the sum of some point distances:

function Point(x, y) {
    this.x = x;
    this.y = y;
}
 
function dist(pt1, pt2) {
    var xd = pt1.x - pt2.x,
        yd = pt1.y - pt2.y;
    return Math.sqrt(xd*xd + yd*yd);
}
 
function main() {
    var totalDist = 0;
    var origin = new Point(0, 0); 
    for (var i = 0; i < 20000; i++) {
        totalDist += dist(new Point(i, i), origin);
    }
    // The following "eval" is just there to prevent IonMonkey from
    // compiling main().  Functions containing calls to eval don't
    // currently get compiled by Ion.
    eval("");
    return totalDist;
}
 
main();

When this script is run, the dist function is compiled by IonMonkey after roughly 10,000 iterations, generating the following intermediate representation (IR) code:

[1]   Parameter 0          => Value     // (pt1 value)
[2]   Parameter 1          => Value     // (pt2 value)
[3]   Unbox [1]            => Object    // (unbox pt1 to object) 
[4]   Unbox [2]            => Object    // (unbox pt2 to object)
[5]   LoadFixedSlot(x) [3] => Int32     // (read pt1.x, unbox to Int32)
[6]   LoadFixedSlot(x) [4] => Int32     // (read pt2.x, unbox to Int32)
[7]   Sub [5] [6]          => Int32     // xd = (pt1.x - pt2.x)
[8]   LoadFixedSlot(y) [3] => Int32     // (read pt1.y, unbox to Int32)
[9]   LoadFixedSlot(y) [4] => Int32     // (read pt2.y, unbox to Int32)
[10]  Sub [8] [9]          => Int32     // yd = (pt1.y - pt2.y)
[11]  Mul [7] [7]          => Int32     // (xd*xd)
[12]  Mul [10] [10]        => Int32     // (yd*yd)
[13]  Add [11] [12]        => Int32     // ((xd*xd) + (yd*yd))
[14]  Sqrt [13]            => Double    // Math.sqrt(...)
[15]  Return [14]

The above is a cleaned-up version of the actual IR for illustration. For the actual nitty-gritty low-level IR, Click Here.

In instructions [3] and [4], Ion blindly unboxes the argument values into Object pointers without checking to see if they are actually object pointers and not primitives. In instructions [5], [6], [8], and [9], Ion blindly converts the x and y values loaded from the objects to Int32s.

(Note: Unboxing in this case refers to decoding a generic JavaScript value into a raw value of a specific type such as Int32, Double, Object pointer, or Boolean).

If we were only using guards to check our assumptions, the following extra checks would have gone into this code:

  1. Two type checks: An extra check before each of [3] and [4] to check that the input argument was actually an object pointer before unboxing it.
  2. Four type checks: Ensuring that pt1.x, pt2.x, pt1.y, and pt2.y were all Int32 values before unboxing them.

Instead, the IR code skips these six extra checks, generating extremely tight code. Normally, we wouldn’t be able to do this because the jitcode would simply be wrong if any of these assumptions were not held. If the function dist is ever called with non-object arguments, the jitcode would crash. If dist was ever called with instances of Point with x and y values that were not Int32s, the jitcode would crash.

To get away with generating this efficient code while maintaining correctness, we must make sure that we never run it after its assumptions become invalid. Accomplishing that requires leveraging SpiderMonkey’s type inference system.

Type Inference

SpiderMonkey’s type inference (TI) dynamically tracks known type information for JavaScript objects and scripts, and how those types flow through different parts of the code. The data structures maintained and updated by TI represent the current type knowledge about the program. By tracking when these structures change, the engine can trigger events whenever particular type assumptions are broken.

The following is a very simplified diagram of the type model generated for our program as it runs.

The TypeScript at the top keeps track of the type information for the function dist – such as the type sets associated with the first and second arguments (‘pt1’ and ‘pt2’).

The TypeObject diagrammed below keeps track of the type information associated with instances of Point – such as the type sets associated with the fields ‘x’ and ‘y’.

These structures will be updated by TI as needed. For example, if dist is ever called with an object that is not an instance of Point, TI will update the appropriate argument typeset on the TypeScript. Likewise, if Point is ever instantiated with values for ‘x’ or ‘y’ that are not integers, the parameter type sets on the TypeObject will be updated.

When Ion JIT-compiles a function and makes implicit assumptions about types, it adds invalidation hooks to the appropriate type sets, like so:

Whenever new types are added to type sets, the relevant invalidation hook will be triggered, which will cause the jitcode to be marked invalid.

Experiments With Ion

Let’s see if we can experimentally trigger these kinds of invalidations by changing the code above. I’ll be using the standalone JavaScript shell built from the Mozilla sources to run these examples. You can verify these tests yourself by building a debug version of the JS shell. (See the SpiderMonkey build documentation for more information).

First, let’s start easy – and verify that no invalidations occur with the script above:

$ IONFLAGS=osi js-debug points.js
[Invalidate] Start invalidation.
[Invalidate]  No IonScript invalidation.

(ignore the spurious, extra “Start invalidation” in this and subsequent outputs – it’s due to garbage-collection starting, which makes the engine check for potential invalidations caused by the GC. It’s not relevant to this post)

Passing the environment variable IONFLAGS=osi just asks Ion to dump all invalidation related events to its output as it runs. As the output notes, this program causes no invalidations – since no type assumptions are broken after compilation.

Stab 2

For our second try, let’s break the assumption that all arguments to dist are instances of Point, and see what happens. Here is the modified main() function:

...
function main() {
    var totalDist = 0;
    var origin = new Point(0, 0); 
    for (var i = 0; i < 20000; i++) {
        totalDist += dist(new Point(i, i), origin);
    }
    dist({x:3,y:9}, origin); /** NEW! **/
 
    // The following "eval" is just there to prevent IonMonkey from
    // compiling main().  Functions containing calls to eval don't
    // currently get compiled by Ion.
    eval("");
    return totalDist;
}
...

In this program, the loop is going to run and make dist hot enough that it gets compiled with the assumption that its arguments are always going to be instances of Point. Once the loop is completed, we call dist again, but with its first argument being an object which is not an instance of Point, which breaks the assumption made by the jitcode.

$ IONFLAGS=osi js-debug points.js
[Invalidate] Start invalidation.
[Invalidate]  No IonScript invalidation.
[Invalidate] Start invalidation.
[Invalidate]  Invalidate points.js:6, IonScript 0x1f7e430

(once again, the first “Start invalidation” is just caused by GC kicking in, and it’s not relevant to this post.)

Aha! We’ve managed to trigger invalidation of dist (points.js, line 6). Life is good.
The diagram below shows what’s happening. The dist TypeScript’s first-argument-typeset changes, adding a reference to a new TypeObject. This triggers its invalidation hook, and marks the IonScript invalid:

Stab 3

For our third stab, we break the assumption that fields of Point instances always contain Int32 values. Here is the modified main() function:

...
function main() {
    var totalDist = 0;
    var origin = new Point(0, 0); 
    for (var i = 0; i < 20000; i++) {
        totalDist += dist(new Point(i, i), origin);
    }
    dist(new Point(1.1, 5), origin); /** NEW! **/
 
    // The following "eval" is just there to prevent IonMonkey from
    // compiling main().  Functions containing calls to eval don't
    // currently get compiled by Ion.
    eval("");
    return totalDist;
}
...

And the associated output:

$ IONFLAGS=osi js-debug points.js
[Invalidate] Start invalidation.
[Invalidate]  No IonScript invalidation.
[Invalidate] Start invalidation.
[Invalidate]  Invalidate points.js:6, IonScript 0x1f7e430

And the diagram showing how the script is invalidated:

Invalidation vs. Guarding

Invalidation and guarding are two distinct approaches to generating jitcode for any given operation. Within the jitcode for any given function, both techniques may be used, and neither one is strictly better than the other in all cases.

The advantage of invalidation-based optimization is that guards can be omitted, allowing very hot code to execute extremely quickly. However, there are also downsides. When an assumption fails, every piece of jitcode that relies on that assumption must be marked invalid, and prevented from being executed. This means that the function returns to running via the interpreter, until such a time as we compile it again with a new set of assumptions. If we have the bad luck of choosing invalidation-based optimization on an assumption that happens to break, then we’re suddenly stuck with a very high cost.

With guard-based optimization, we sacrifice the speed of the optimize code, but the resulting code is more resilient to changes in assumptions – we don’t have to throw away jitcode when assumptions break. In those cases, the code will just execute a slowpath. If the number of times a function is called with invalid assumptions is small (but greater than zero), then guard-based optimization might be a better choice than invalidation-based optimization.

The question of which optimization strategy to pick when is not always easily answered. Even if an assumption is invalidated occasionally, the jitcode which assumes it may be hot enough to make it worthwhile to use invalidation-based optimization, and just pay the cost of the occasional recompile – the time saved in between will be worth the recompile cost. Alternatively, it may not be worth the cost. Beyond a certain point, deciding between the two approaches becomes a matter of heuristics and tuning.

On-Stack Invalidation

The post so far gives a general idea of the main principles behind invalidations. That said, there is a very important corner case with invalidation that all JIT engines need to take care of.

The corner case is called on-stack invalidation, and it arises because sometimes, the jitcode that becomes invalid is code that’s on the call stack (i.e. it’s one of the callers of the code that’s currently executing). This means that once the current code finishes running, it’s going to execute a machine-level return to jitcode that we can no longer safely execute.

Handling this case requires a bit of juggling, and consideration for a number of subtle errors that may arise. I’ll cover more on that in a follow-up post.

9 responses

Post a comment

  1. David Corbacho wrote on :

    Great post.
    There are JavaScript libraries that to keep it DRY, functions will accept different type of arguments (objects, array, or string) and depending on the type, they act different:

    So this will conflict with this kind of JIT compiling optimization ?
    Or type assumptions are re-initialized each time the function is called?

    It’s a pity that is a brand new blog and still it’s not so popular
    But keep it up! With quality content like this, it will spread faster

    PS. I love the typography and how readable is the text. +1

    Reply

    1. kvijayan wrote on :

      Yes, more polymorphic code will tend to use this sort of optimization less.

      New type assumptions are only used when the function is compiled a second time (after the original code has become invalidated, reverts to using the interpreter, gets run a lot of times, and then scheduled for compilation once again). By that time, a huge cost has already been paid.

      The best way to avoid this is to not have unexpected type behaviour. It’s ok to have really polymorphic code, because as long as we detect that it’s polymorphic early on, we’ll choose not to use invalidation-based optimization in the first place, and this cost won’t be paid. However, if some code seems to be monomorphic and very type stable for a long time, and then suddenly there’s a change in its type behaviour, then invalidations will probably happen.

      Reply

      1. David Corbacho wrote on :

        Ok, I understand it better now. Thanks for answering !

        For sure this will look awesome in benchmarks, but it will be nice also to see more blog posts about how this will translate to real-world code or JS libraries and best practices for JavaScript developers, so we can produce code that it’s easy to be optimized in the JIT engine

        Reply

  2. Arpad Borsos wrote on :

    Interesting read indeed!
    Having read a bit about the structural typing of Rust, i wonder why the first example triggers invalidation at all.
    I mean the passed in object has the “structure”, the same properties with the same types. Of course, the internal [[Prototype]] differs, but the JIT should be able to figure out that the [[Prototype]] is not used in `dist()` at all.

    Anyway, I’m looking forward to read more about SpiderMonkey. 🙂

    Reply

    1. kvijayan wrote on :

      You make an interesting observation. It’s true that we can observe that the two types are similar enough to handle them both in the same way.

      But keep in mind that we have to make it so that TI triggers an invalidation hook whenever the assumptions become false. Currently that’s easy: there’s a list of hooks associated with the type set, and whenever the type set changes those hooks are triggered by TI. If you make the condition for triggering them more complex, though, then the engine has to do a lot more work every time the typeset changes just to figure out if it should trigger a given hook or not.

      In this case, we would have to design a data structure that would allow us to communicate to the engine the condition for invalidation (“invalidate if you add a type to the type set that either has some property that’s not ‘x’ or ‘y’, or has them in an order that’s different, or has types for those fields that are not int32”), and then have the engine check that every time the type set gets updated. That will involve the engine scanning through every type object that’s added to the set, and inspecting it to see if it matches the condition.

      These kinds of invalidations are usually rare, so going to a lot of effort to optimize them is generally not worth the effort, either in terms of developer time, or complexity, or engine time it would require.

      Reply

  3. André wrote on :

    Interesting post.

    Could a similar system be used to “lighten” the guarding of wrapped C++ functions (like JSAPI calls / DOM calls)???

    From my experience with JSAPI you have to guard all function parameters to prevent crashes, but it would be nice if a JSAPI call could get information from Type Inference about when parameter type assumptions are broken. Thus if the parameter types stay the same all the time, the wrapper function could turn off guarding code until invalidation.

    Is this possible? I imagine it could greatly improve wrapped C++ calls ranging from DOM and XPCOM over WebGL and code from Spidermonkey embedders that use JSAPI …

    p.s. off-topic: this blog does not accept email-adresses with a + inside (though they are valid)

    Reply

    1. kvijayan wrote on :

      It would be difficult to get type inference to inform things like DOM or other native-implemented methods. To write those in an optimized way (i.e. to skip unboxing) you really need to enforce a particular type expectation. TI doesn’t enforce anything, it simply describes types that it has seen as they show up.

      The best you could do with that would be to have two or more versions of every function: a specialized one that’s used in sites where TI indicates that the types match, and a generic one that we replace it with when the TI information changes. That’s a lot of complexity for not that much gain. C++ calls have other overheads that mostly outweigh unboxing, so optimizing this part of it wouldn’t provide much benefit.

      There are things we can do to make stuff like DOM calls faster, though. Eric Faust has done some pretty sweet work on that front. He has a presentation on Air Mozilla here: https://air.mozilla.org/intern-presentation-2/

      Reply

  4. fbender wrote on :

    I had an idea a while ago, and Bug 767223 triggered me to finally jot it down here:

    How about having an interpretable and eventually cross-browser way to inform the engine about possible optimizations and pitfalls in a JS script? This is just a rough idea without knowledge on interpreters, and I’d like to see some thoughts from people “knowing the matters”:

    (The ideas use the idea of the `”use strict”;` literal to allow backwards-compat.)

    The first piece is a hint for JIT:
    “`
    function() { // “use strict”;
    “hint earlyjit | nojit”;
    // …
    }
    “`
    `earlyjit` means that the function is expected to run many times and arguments will always have the “correct” type, so it is advised for the interpreter to mark this code as hot faster than what is currently done (maybe after tenth or hundreth of executions – this decision should be left to the implementation).
    `nojit` means that although this function might be called many times, it is expected to suddenly change arg types and thus should never be jitted.

    The second part is a hint for an engine to apply guardians to a function to pre-emptively choose a slow-path (the syntax may include the args’ names to make it more readable):
    “`
    function(a, b, c, d…) { // “use strict”;
    // “hint earlyjit”; // this is not required for the following line
    “guardargs int, str, arr, obj…”;
    }
    “`
    The code should be self-explaining … This could also trigger warnings in the console to allow developers to easily identify where slow-paths may occur.

    What do you think? Is this a sensible idea or not worth investigation further?

    Reply

    1. kvijayan wrote on :

      The hinting mechanism you’re suggesting is doable, and depending on who you talk to there are different opinions on whether that sort of approach is good or not.

      I’m less inclined towards these sorts of measures. For one, it introduces special syntax that’s embedded within comments. This syntax has to be agreed upon by all the browser implementors, and used in the same way. Moreover, it means that comments can now influence program behaviour and performance, which is not a good thing in my opinion.

      My personal view is that forcing the JS developer to provide hints to the engine to achieve performance is a reflection of a weakness in the engine. We need to keep working towards improving program analysis, runtime analysis, and type modeling, so that those sorts of hints are not necessary – and I believe that this is possible.

      Reply

Post Your Comment