Introducing the WebKit FTL JIT

https://www.webkit.org/blog/3362/introducing-the-webkit-ftl-jit/

by panic • 12 years ago

491 96 12 years ago

nadav2562• 12 years ago

This project is such a great technological achievement for both the Webkit and LLVM communities. There are so many 'first times' in this project. This is the first time profile guided information is used inside the LLVM _JIT_. This is the first time the LLVM infrastructure supported self-modifying code. This is one of the very few successful projects that used LLVM to accelerate a dynamic language. This is the first time Webkit integrated their runtime (JITs and garbage collector) with an external JIT. This is the first JavaScript implementation that has advance features such as auto-vectorization. Congrats guys!

erichocean3• 12 years ago

This is one of the very few successful projects that used LLVM to accelerate a dynamic language.

Yup. Another is Open Shading Language[0]. They ended up with performance 25% faster than the previous shaders, which were coded by hand in C. It's used now in Blender's "Cycles" renderer. Yay, open source!

[0] https://github.com/imageworks/OpenShadingLanguage/

nadav2562• 12 years ago

I don't think that OpenShadingLanguage is dynamic.

xioxox• 12 years ago

There is also numba, http://numba.pydata.org/, which uses LLVM to compile annotated Python code, although this is more limited of course.

aaronbrethorst• 12 years ago

    dubbed the FTL – short for Fourth Tier LLVM

Is it still a backronym if it redefines an existing acronym? (even a fictional one?)

http://en.wikipedia.org/wiki/List_of_Battlestar_Galactica_ob...

scott_karana• 12 years ago

The term FTL is generally used, and predates Battlestar Galactica.[1]

But of course, your point of confusing people with acronyms still stands!

http://en.wikipedia.org/wiki/Faster-than-light

MBCook• 12 years ago

When I first saw references to Apple's engine updates the other day and they were referred to as FTLJIT I just assumed it stood for Faster-Than-Light. Perhaps that's just too nerdy for Apple to admit. Maybe it's not a backronym, it just worked out that way.

But I bet the engineers like the name.

gregory144• 12 years ago

I bet the "redefinition" is intentional.

tambourine_man• 12 years ago

I'm so glad to see that Webkit is not dead after the Blink fork. I still use Safari as my main browser, but its developer tools and optimizing compiler lag behind.

phoboslab• 12 years ago

Right, but seeing the speed comparison with the LLINT makes me really sad that we can't even use the baseline JIT in iOS Apps. I still have some hope that Apple works on a way to run JSC in an isolated, trusted process that is allowed to use the JIT. Otherwise the new FTL JIT doesn't get us anything in many cases.

[1] http://www.webkit.org/blog-files/ftl-jit/four_tier_performan...

higherpurpose• 12 years ago

And allow other competing engines on the platform, while they're at it.

Theodores• 12 years ago

Much like how hairdressers don't necessarily have the most promising haircuts, it would seem that companies that make the finest in web browsers don't necessarily have the greatest of web pages! I don't think there is an ounce of javascript on the webkit website yet that article goes waaay over the heads of mere mortals on mega-speedy-javascript.

rimantas• 12 years ago

This is actually a good thing. Do you expect the page about racecars come with a racecar attached? Javascript is already overused on the web.

rayiner7• 12 years ago

The Bartlett mostly copying collector is just a really neat design. Even if your compiler gives you precise stack maps, conservative root scavenging still has the major advantage of giving the optimizer the most freedom. Its the basis of SBCL's collector, which is probably 20 years old now. Good to see it still has legs.

This is the patch point intrinsic documentation: http://llvm.org/docs/StackMaps.html. This is a really significant addition to LLVM, because it opens up a whole world of speculative optimizations, even in static languages. Java, for example, suffers on LLVM for want of an effective way to support optimistic devirtualization.

pcwalton6• 12 years ago

Well, with conservative-on-stack GC you lose the ability to do bump allocation in the nursery for all objects (since you can't update all roots when you tenure objects, so you can't move them, so you can't do two-space stop-and-copy), which is to my mind a pretty severe drawback.

You're right that you can do some optimizations such as reassociation of pointer arithmetic, but I'm not sure how much they matter in practice—I'd be quite surprised if they outweighed the advantage of being able to allocate in ~5 instructions [1].

That said, in a practical sense I'm certain the advantage of being able to use the mature optimizations in the LLVM JIT outweighs the disadvantages of having to use conservative GC (and as I understand Azul is working on precise GC support for LLVM). Given their constraints I think they did a great job.

[1] Edit: I've been informed that the fast path in JSC is around this for pulling a bin off the free list. I should be more precise: what I mean is that you can stay on the fast path more often. You can always allocate very quickly, only falling off the fast path if the nursery fills up. Of course, falling off a malloc fast path is rare anyhow, so this isn't likely to be that much of a difference in practice…

rayiner7• 12 years ago

Both MPS and SBCL, which are Bartlett-style collectors, use bump pointer allocation. They divide the heap into pages, and bump allocate into pages. At collection time, when a page is the target of an ambiguous pointer, it is pinned and promoted in place. A pinned page is not used for allocation the next round. The downside is that unless the ambiguous pointers are transient, a page may be pinned and unusuable for allocation for awhile.

hosay123• 12 years ago

    > Profile-driven compilation implies that we might invoke an optimizing
    > compiler while the function is running and we may want to transfer the
    > function’s execution into optimized code in the middle of a loop; to our
    > knowledge the FTL is the first compiler to do on-stack-replacement for
    > hot-loop transfer into LLVM-compiled code.

Reading this practically made my hair stand on end, it is one hell of a technical feat, considering especially they had no ability to pre-plan so that both LLVM and their previous engine would maintain identical stack layouts in their designs. It's really insane they got this to work at all.

I was reminded of the old story about a search engine that tried to supplant JS with a Java bytecode-clone because at the time it was widely believed Javascript had reached its evolutionary limit. How times change!

Someone• 12 years ago

And it's not just two engines, but four, with at least one of them using the amount of available executable memory to choose whether to switch between them.

I know WebKit has tons of tests, but there must be some truly hairy bugs in that code. Does anybody know how they exercise the various optimize/deoptimize steps?

sanxiyn9• 12 years ago

One neat testing strategy is to artificially lower counter used to tier up. Instead of using 1000 for DFG and 100000 for FTL, use something like 10 for DFG and 100 for FTL. This will cause lots of opt/deopt stress and can discover correctness bugs which may hide in more normal executions.

InclinedPlane• 12 years ago

Indeed. Although, to be honest, I'd expected such technology to be the norm for most interpreted/compiled languages at this point.

It turns out that instrumentation and optimization is actually a harder problem than one would think, which makes a lot of rather nifty technology farther out of reach than it otherwise should be.

rayiner7• 12 years ago

You don't have to maintain identical stack layouts, just be able to translate between frame formats at transitions. Most of the necessary semantics can be expressed as a function call. Figure out what JS values are live across the transition point, and pass them as arguments to a function call which transitions to the interpreter, which proceeds using those values. That can be done without any changes to LLVM, although obviously the code patching can't, and its more efficient not to require values to be shuffled into argument registers. Keeping things updated when the target function is inlined is also tricky. But overall its not as invasive a change to LLVM as you'd think. See: A Modular Approach to On-Stack Replacement in LLVM, https://www.google.com/url?sa=t&source=web&rct=j&ei=IrByU5Hx....

jevinskie2• 12 years ago

Also http://llvm.org/docs/StackMaps.html

plantain• 12 years ago

Maybe the first browser to do so, but my colleagues at university were doing this 2-3 years ago (hot profile guided optimized replacement in LLVM for generic/non-browser specific code). I will see if their papers are available without journal access.

SSLy• 12 years ago

Can you provide papers' names for those of us who have access to academia stuff?

tomp2• 12 years ago

They use a conservative GC, which I understand, as they were using it before FTL JIT, and it required minimal changes for integration with LLVM-based JIT. However, in the blog post, they mention several times that they wanted to avoid stack maps because that would require spilling pointers from registers to stack, which they say is undesirable for performance reasons.

I wonder, however, how slow register spilling really is. I will test it when I have time, but logically, it shouldn't take up much time. Under the x64 ABI, 6 registers are used for argument passing [1], and the rest of the arguments are passed on the stack. So, when the runtime calls into GC functions, all but at most 6 pointers are already in the stack, at (in theory) predictable locations. Those 6 registers can be pushed to stack in 6 instructions that take up 8 bytes [2], so the impact on the code size should be minimal, and performance is probably also much faster than most other memory accesses. Furthermore, both OCaml and Haskell use register spilling, and while not quite at C-like speeds, they are mostly faster than JS engines and probably also faster than FTL JIT.

Of course, predicting the stack map after LLVM finishes its optimisations is another thing entirely, but I sincerely hope the developers implement it. EDIT: it seems that LLVM includes some features [3] that allow one to create a stack map, though I wonder if it can be made as efficient as the GHC stack map, which is simply a bitmap/pointer in each stack frame, identifying which words in the frame are pointers and which aren't.

[1] http://en.wikipedia.org/wiki/X86_calling_conventions#x86-64_...

[2] tested using https://defuse.ca/online-x86-assembler.htm#disassembly

[3] http://llvm.org/docs/GarbageCollection.html

rayiner7• 12 years ago

Registers have to be spilled at every location where the GC can be entered. This includes places where the GC can be triggered, including function calls and loop back edges. Having to spill values held in registers across a loop back edge is quite suboptimal.

pcwalton6• 12 years ago

That isn't true with all stack map implementations though: mature ones (such as OCaml's IIRC) have the ability to track registers as well, eliminating the spilling requirement. But LLVM doesn't have support for this yet (although I'll be delighted if Azul lands their patches to implement it!)

tomp2• 12 years ago

If I recall correctly, GHC (at least the non-LLVM code generator) doesn't spill at every location that GC could be entered. Instead, it checks whether GC needs to be entered, by checking if there is any more space on the stack & heap (admittedly, this is quite trivial, due to its bump-pointer allocation), and only spills and enters the GC if necessary.

maximilianburke• 12 years ago

For a similar project I was on -- that is a managed language built on top of LLVM -- we ensured GC events only came from calls to GC functions, either explicit collects or allocates. Spills to the stack of references only occurred in calls to functions and not loops. Our collector was an accurate collector though.

This project was targeting game code for the register heavy, branch-unfriendly, in-order PowerPC PS3 and Xbox 360. Performance in scalar numerical code was equal to equivalent C++ code.

pizlonator3• 12 years ago

That's a half-truth. Callee-save registers are a beautiful thing. When LLVM emits code for a function call, with high probability all of the important state will not be spilled - it'll be left in callee-save registers and it will be up to the callee to save those registers if the callee wishes to use them.

All that the GC has to do is force-spill all callee saves onto the stack, or just save them on the side. A typical conservative-on-the-stack (the more general class of collectors to which WebKit's Bartlett-based GC belongs) algorithm for stack scanning looks like:

void scanConservatively(void* begin, void* end); void scanMyStack() { int fake; void* start = &fake; void* end = ... get the address of where you first entered the VM ... jmp_buf buf; setjmp(&buf); scanConservatively(start, end); scanConservatively(&buf, &buf + 1); }

Notice that this uses setjmp() as a hack to extract all callee-save registers.

That is sufficient to: (1) get all of the pointers you're interested in and (2) allow the compiler (in WebKit's case, LLVM) maximum freedom to not spill registers anymore than it would do in an normal C calling convention where no GC is in play.

Bottom line: Bartlett = zero overhead stack accounting.

nivertech• 12 years ago

no benchmarks versus V8?

azakai3• 12 years ago

You can see some benchmarks comparing them here:

http://arewefastyet.com/#machine=12&view=breakdown&suite=asm...

FTL beats v8 on almost all of those.

acqq• 12 years ago

I wish I knew if lower is better or higher is better on the first page (y axis is not described on the graphs).

yjbanov• 12 years ago

All these benchmarks have "asmjs" in their names, which tells me they are not benchmarking idiomatic JavaScript, but JS generated by emscripten. If that's the case, they do not represent the performance of hand-written applications, which is the majority of all apps on the web.

It would be more interesting to see results for benchmarks such as DeltaBlue or Richards. These would correlate much better with gmail and hipmunk performance, as opposed to in-browser demos of Unreal Tournament.

b0b0b0b• 12 years ago

For me, chrome still beats this webkit and the latest firefox for deep learning mnist in the browser:

http://cs.stanford.edu/people/karpathy/convnetjs/demo/mnist....

bzbarsky• 12 years ago

I'm trying to figure out how to measure performance here. Both Chrome and Firefox seem to take about the same wall-clock time to go through 5000 examples. Should I be waiting longer? Measuring something else?

simcop2387• 12 years ago

I wonder how difficult it would be then to take the hints for asm.js and after validating that it meets the contracts it provides push through all the code into the FTLJIT to get a huge speed boost on that code. With the ability to do hot transfers into LLVM compiled code it should be possible to do it without any real noticeable issues to the user.

om210• 12 years ago

We already get a huge speed boost on asm.js code, without having to special case it. It's likely that LLVM could do even better on it, but at this time we're not sure that a specific hint that it's asm.js would help.

sanxiyn9• 12 years ago

It may not help throughput, but it will certainly help warmup and caching.

mccr8• 12 years ago

That is roughly the design that OdinMonkey, the Firefox asm.js compiler, uses: verify the type information, then dump it all onto the high performance JS compiler backend. Two big advantages of an AOT approach like OdinMonkey are:

1. Consistency. You don't have to worry that some critical bit of type information will suddenly start to fail to be propagated all the way through multiple stages. This isn't really a problem for standard benchmarks, which are closely watched for regressions, but can be a problem for random code in the wild. JIT heuristics are complex.

2. Startup speed. AOT does not have to go through all of the various warmup phases, which are needed by JITs both to avoid wasting time on optimizing code that is not important for perf and to get type hints.

InTheArena• 12 years ago

This is a much bigger deal then people are giving credit for, because of the other thing that Apple uses LLVM for. It's the primary compiler for Objective-C, and thus Cocoa (mac apps) and CocoaTouch (ios apps) as well. If apple has Javascript compiling on-the-fly at this speed, this also means that it would be pretty trivial to expose the objective-c runtime to javascript, and mix and match C & Javascript code.

This is going to be a very very big deal.

overcyn• 12 years ago

You've been able to do that for awhile.

http://opensource.apple.com/source/JavaScriptCore/JavaScript...

alayne2• 12 years ago

You can't get the JSContext of a UIWebView though, which is a big hole.

hsivonen• 12 years ago

I doubt "it would be pretty trivial". The problems are probably in cross-language object life times and memory management--not in whether both generate machine instructions using LLVM machinery.

leeoniya• 12 years ago

Note that the FTL isn’t special-casing for asm.js by recognizing the "use asm" pragma. All of the performance is from the DFG’s type inference and LLVM’s low-level optimizing power.

doesnt "use asm" simply skip the initial profiling tiers that gather type stats etc? most of the benefit of compiling to asm.js comes from fast/explicit type coersion.

cromwellian2• 12 years ago

Would be interesting to see Octane numbers.

sanxiyn9• 12 years ago

In my test, Octane numbers improved by 25%. Improved benchmarks are Richards and DeltaBlue, which the blog post already analyzed in depth, and Mandreel and zlib, which are asm.js-like.

azakai3• 12 years ago

You can also see online results at

http://arewefastyet.com/#machine=12&view=breakdown&suite=oct...

There is a discontinuity about a month ago, which is around when FTL was enabled, I believe. There you can see the nice speedups on Mandreel and the others you mention.

om210• 12 years ago

You can try it yourself with a WebKit nightly if you want. http://nightly.webkit.org/

cromwellian2• 12 years ago

On a new Mac Pro 2013, 8-core, 3Ghz, I measure:

Safari: 18159 WebKit Nightly: 25141 Chrome Canary: 29962

That's a 38% speedup which is none too shabby.

harichinnan• 12 years ago

ELI5 version please?

munificent• 12 years ago

Safari got faster.

lobster_johnson• 12 years ago

Is this architecture generic enough that one could, say, build a Ruby compiler on top of it?

I imagine even writing a Ruby -> JS transpiler that used the WebKit VM would provide a speedup, similar to how JRuby works on the JVM, but native compilation would be even better.

sanxiyn9• 12 years ago

Yes.

Moreover, Dropbox is trying roughly similar architecture for their Python implementation.

https://github.com/dropbox/pyston

steveklabnik• 12 years ago

You might be able to try that with http://opalrb.org/

Rubinius already does Ruby -> LLVM.

ksec3• 12 years ago

But as much as i hate to admit Rubinius is still slow.

ksec3• 12 years ago

I am glad WebKit is thriving. I was worried that the fork Blink with Google and Opera would means Webkit gets no love.

Hopefully the next Safari in iOS and OSX will get many more improvements

om210• 12 years ago

In some ways, it's easier to go fast when you don't have to argue over basic strategy or maintain duplicate code paths. Even if you lose some contributors in the process.

ksec3• 12 years ago

Yes, but in this case it isn't just "some" contributors. Google used to contribute more then double the commit and people on the project.

http://hypercritical.co/2013/04/12/code-hard-or-go-home

jwarren• 12 years ago

I adore threads like this. They really bring to focus exactly how much more I have to learn.

otikik• 12 years ago

It's called FTL, but I am not actually sure it's Faster Than LuaJIT.

jongraehl• 12 years ago

wonder how this compares to node - specifically https://github.com/rogerwang/node-webkit

Introducing the WebKit FTL JIT

Related Stories