Inside Mozilla's New JavaScript JIT Compiler

An anonymous reader writes "IonMonkey is the name of Mozilla's new JavaScript JIT compiler, which aims to enable many new optimizations in the SpiderMonkey JavaScript engine. InfoQ had a small Q&A with Lead Developer David Anderson, about this new development that could bring significant improvements in products that use the SpiderMonkey engine like Firefox, Thunderbird, Adobe Acrobat, MongoDB and more. This new JIT infrastructure, will feature SSA compiler intermediate representations which will facilitate advanced optimizations such as type specialization, function inlining, linear-scan register allocation, dead-code elimination, and loop-invariant code motion."

Comments

Javascript Monkeys

[TaoPhoenix]

What's different between IonMonkey and JaegerMonkey (the last engine I thought)?

Re:Javascript Monkeys

[sribe]

Good question - it's a shame there's no way to quantitatively determine the relationship between two releases of the same product. Maybe they could use numbers?

What an excellent, useful, non-obvious invention? Have you considered applying for a patent?

Re:Javascript Monkeys

[DontBlameCanada]

-JaegerMonkey was dreamt up during a night spent consuming JaegerMiester shooters.
-IronMonkey was designed the morning after, behind iron bars in the slammer, following the JaegerMonkey "JaegerMiester" release party.

Re:Javascript Monkeys

[BZ]

This part is one major difference "Clean, textbook IR so optimization passes can be separated and pipelined with well-known algorithms."

The current JM is somewhat goes directly from SpiderMonkey bytecode to assembly, which means any optimizations that happen in the process are ad-hoc (and typically don't happen at all; even basic things like CSE aren't done in JM right now).

Re:Javascript Monkeys

[tigre]

He was still hung over from the JaegerMonkey party.

Re:Javascript Monkeys

[xouumalperxe]

It's a good question, but version numbers would really imply the wrong thing here. SpiderMonkey is the "root" Javascript implementation. TraceMonkey adds trace trees to SpiderMonkey (which apparently means it JIT compiles a type-specialised version of a function if it detects a specific version of a function to be "hot" -- executes very often). Jaeger Monkey uses a more traditional "JIT compile everything" perspective, but then apparently also has the tracing feature in the backend to further optimise hot paths. From skimming TFA, IonMonkey adds to this a first pass that translates all the code into an intermediate representation that makes further optimisations easier. So in reality, all the FooMonkeys seem, to me, to be closer to large-scale plugins into SpiderMonkey than new engine versions per se.

Re:Javascript Monkeys

[Millennium]

This. It seems to be essentially a pipeline: the old code doesn't get thrown out, just added on. In essence, SpiderMonkey's path to awesome started out with the beginning and the end (TraceMonkey), and now they're going back to fill out the middle (JaegerMonkey and now IonMonkey).

Firefox 3.0 (and lower): SpiderMonkey (JavaScript interpretation
Firefox 3.5: SpiderMonkey -> TraceMonkey (awesome JIT for hot functions only)
Firefox 4.0: SpiderMonkey -> JaegerMonkey -> TraceMonkey (decent JIT for everything, awesome JIT for hot functions)
Firefox ??? (I can't imagine this will be ready for FF5; maybe FF6?): SpiderMonkey -> IonMonkey -> JaegerMonkey -> TraceMonkey (better IR leading into the JIT, making it even better for everything, but still with awesome JIT for hot functions)

Re:Javascript Monkeys

[BZ]

The big gains from JS interpreters to most of the current crop of JS JIT compilers (excluding Crankshaft and Tracemonkey, and possibly excluding Carakan's second-pass compiler) come from class infrence, type specialization, ICs, etc. That work is already done. The result is about 30x slower than C code (gcc -O2, say) on numeric manipulation.

To get better performance than that, you need to do more complicated optimizations. For example, Crankshaft does loop-invariant code motion, Crankshaft and Tracemonkey both do common subexpression elimination, both do more complicated register allocation than the baseline jits, both do inlining, both do dead code elimination. For a lot of code the difference is not that big because there are big enough bottlenecks elsewhere. For some types of code (e.g. numeric manipulation) it's a factor of 2-3 difference easily, getting into the range of gcc -O0. And that's without doing the really interesting things like range analysis (so you can eliminate overflow guards), flow analysis so you know when you _really_ need to sync the stack instead of syncing after every arithmetic operation, and so forth.

For code that wants to do image or audio manipulation on the web, the textbook IR optimizations make a gigantic difference. That assumes that you already have the dynamic-language problems of property lookup and whatnot solved via the techniques Smalltalk and Self pioneered.

One end goal here is pretty explicitly to be able to match C or Java in performance on numeric code, at least in Mozilla's case.

Re:Javascript Monkeys

[TheRaven64]

TraceMonkey adds trace trees to SpiderMonkey (which apparently means it JIT compiles a type-specialised version of a function if it detects a specific version of a function to be "hot" -- executes very often)

Not quite. Traces are sequences of instructions without interior branches. When you write some code, you split it up into functions. A trace flattens this structure - you can think of inlining as a very special case of trace-based optimisation. A trace has a single entry point and (potentially) multiple exit points.

Traces are very useful for JavaScript code, because it tends to be very branch heavy. You can identify a hot path, and then compile a linear sequence of instructions where the branches all take you out of that sequence and are all hinted to be not-taken branches. This means that the common path will contain no instruction cache misses and no mispredicted branches, which can make it very fast.

This kind of optimisation is only possible with profiling information, which is why you see it more commonly in JIT compilers, where profiling information is always available.

LLVM

[nhaehnle]

I'd be interested to hear why the Mozilla developers don't use an existing compiler framework like LLVM, which already implements many advanced optimization techniques. I am aware that JavaScript-specific problems need to be dealt with anyway, but it seems like they could save themselves a lot of hassle in things like register allocation etc. Those are not so interesting problems that are handled by existing tools like LLVM quite well, so why not use that?

Re:LLVM

[BZ]

http://blog.mozilla.com/dmandelin/2011/04/22/mozilla-javascript-2011/ has some discussion about LLVM in the comments. The short summary is that the LLVM register allocator, for example, is very slow; when doing ahead-of-time compilation you don't care much, but for a JIT that could really hurt. There are various other similar issues with LLVM as it stands.

Re:LLVM

[lucian1900]

Because it's easier. All the projects that tried to write a good JIT with LLVM came to the same conclusion: LLVM sucks for JITs. That's both because of implementation issues and design choices. LLVM is a huge, complex C++ program. No one's going to fix it. Nanojit and the register allocators floating around are competitors.

Re:LLVM

[Animats]

I'd be interested to hear why the Mozilla developers don't use an existing compiler framework like LLVM...

LLVM is intended for more static languages than Javascript. The Unladen Swallow project tried to use it for Python, and that was a failure..

Re:LLVM

[mad.frog]

A guy did in fact transplant LLVM in place of Nanojit (in Tamarin rather than SpiderMonkey, but close enough):

http://www.masonchang.com/blog/2011/4/21/tamarin-on-llvm-more-numbers.html

And found that LLVM didn't really produce an overall win for this sort of code generation. LLVM is nice for ahead-of-time-compilation, but isn't a good fit for just-in-time.

javaScript as a platform

[hey]

Now javaScript is so fast perhaps other interpreted languages would be "compiled" to JS. I am thinking of Perl6 for one.

Re:javaScript as a platform

[Anonymous Coward]

Yup. Python is translated to javascript in pyjamas. http://pyjs.org

Re:javaScript as a platform

[Anonymous Coward]

Check Coffeescript, Objetive J, Pyjamas, Skulpt.

Re:types

[BZ]

OK. Let's look at http://code.jquery.com/jquery-1.5.2.js very quick. This isn't even a minified version; just the original source. Pretend like you don't know what jquery is doing. The first few functions with arguments here:

> function( selector, context )

What are the types of those?

> function( selector, context, rootjQuery )

And those?

> function( num )

And that one? Hint: the function expects it to be "null" or at least "undefined" sometimes.

> function( elems, name, selector )

And that? Note that the function itself is not sure what to expect in |elems| and has different codepaths depending on what it finds there.

The point is, going from name to type is not really that easy.

Worse yet, "type" in this context also means what JS engines variously call "shape" or "hidden type": two instances of Object are considered the same type if they have the same properties in the same order. Telling _that_ from a variable name is pretty hard.

Dead-code ellimination

[ferongr]

Didn't Mozilla cry bloody murder when IE9 was discovered to perform dead-code elimination claiming it was "cheating" because it made some outdated JS benchmarks finish in 0 time?

Re:Dead-code ellimination

[BZ]

No, they just pointed out that IE's dead-code elimination was somewhat narrowly tailored to the Sunspider benchmark. That's quite different from "crying bloody murder".

Tracemonkey does dead-code elimination right now; it has for years. It's just that it's a generic infrastructure, so you don't usually get artifacts with code being eliminated only if you write your script just so. On the other hand, you also don't usually get large chunks of web page dead code eliminated, because that wasn't a design goal. Keep in mind that a lot of the dead code JS JIT compilers eliminate is code they auto-generated themselves (e.g. type guards if it turns out the type doesn't matter, stack syncs it it turns out that no one uses the value, and so forth), not code the JS author wrote.

Re:Dead-code ellimination

[BZ]

> Narrowly pointing out and having their lead
> "evangelist", Asa Dotzler

Uh... I think you're confused about Asa's role here. But anyway...

> I haven't seen any proof that the dead-code
> eliminator is "somewhat narrowly tailored for
> Sunspider"

Well, it only elimintated code that restricted itself to the set of operations used in the Sunspider function in question. This is pretty clearly described at http://blog.mozilla.com/rob-sayre/2010/11/17/dead-code-elimination-for-beginners/

For example, it eliminated code that included |TargetAngle > CurrAngle| but not code that was otherwise identical but said |CurrAngle >) was not. Addition and subtraction were eliminated while multiplication and division and % were not.

If it eliminated "any code that doesn't touch the DOM" that would be a perfectly good general-purpose eliminator. That's not what IE9 was doing, though.

There was the side issue that it also produced buggy code; that's been fixed since, so at least IE9 final doesn't dead-code eliminate live code.

Re:Dead-code ellimination

[BZ]

Turns out, figuring out whether code in JS is dead is hard. See http://blog.mozilla.com/rob-sayre/2010/11/17/dead-code-elimination-for-beginners/ for some examples of things that look dead but aren't.

Re:Dead-code ellimination

[TheRaven64]

That's not what dead code elimination does. It removes code that does not affect the program's result. For example, if you have i++ and you then don't use i before it goes out of scope, this is a dead expression and the compiler can remove it. In a language as dynamic as JavaScript, it's quite hard to do because you have to make sure that the expression that you eliminate doesn't have any side effects before you eliminate it, and for nontrivial JavaScript expressions determining whether something has side effects can be as costly as just executing it.

Re:How many JIT engines is this now?

[Millennium]

Damn, Mozilla changes JIT engines like every year. Why should be believe this one will last any longer than all the others they have tried?

That's not actually what's happening, though Mozilla isn't helping matters with all the confusing names.

What's actually going on is that Mozilla is essentially implementing different parts of a longer pipeline. Even as recently as FF4, SpiderMonkey is still present at the front of that pipeline, and TraceMonkey is still present at the end (actually nanoJIT is at the very end, but it's not named after a monkey so we won't count it here). JaegerMonkey, IonMonkey, and all the other monkeys go in the middle.

Re:types

[TheRaven64]

Type annotations are only useful for documentation, and for some sanity checking (although type theory is not expressive enough to catch any interesting classes of programmer error). The StrongTalk team discovered that they got much more accurate information from type feedback than they did from programmer-provided type annotations. They created a dialect of Smalltalk with explicit type annotations. Their VM was the fastest Smalltalk implementation at the time by quite a large margin, and they found that they got no performance benefit at all from using the user-specified type information.