WebKit’s JS Interpreter was an AST walker

I was surprised to discover that the current previous JavaScript interpreter in Apple’s WebKit, which is the engine for the Safari browser, is very slow. Go here, scroll down to “Why It’s Fast”. They were interpreting the syntax tree rather than compiling down to bytecodes. The first line says “Like the interpreters for many scripting languages…”, which implies that there are other interpreters using this awful technique. If anyone knows of a popular interpreter that does this, please tell me in the comments.

A better way to implement an interpreter is as a bytecode interpreter. Most people implement the interpreter as a big switch statement, but an obvious improvement is to use direct threading (described in that post). Most interpreters use a stack to store operands, so here’s a paper that tries to reduce the redundant load/stores in a stack-based VM, and another that reduces the code bloat from this technique. Better yet, this paper describes a register layout that reduces the number of bytecode dispatches. Another improvement is to use “selective inlining”, which is described here by the guy working on the Squeak interpreter. This trick is complicated, but improves performance substantially. The point is that there’s been lots of work on efficient interpreters, yet WebKit uses a technique taught in an Intro to Compilers class that is intended to be easy for undergrads to understand. I can’t believe they used this in a real product.

[ed: Apparently, WebKit’s previous interpreter was still faster than most other interpreters (IE, Mozilla, Opera, etc).]

Advertisements

5 comments

  1. Maciej Stachowiak

    While bytecode is a better architecture, note that the old AST interpreter was highly optimized and achieved speed comparable to the fairly well optimized SpiderMonkey bytecode interpreter for JavaScript (and beat the pants off of Opera’s and IE’s bytecode interpreters). It’s not just the architecture that matters, it is the implementation quality. So if you want to throw around terms like “shockingly slow”, I would say you should base it on measurements, not theory based on the architecture. You would be surprised how much it is possible to speed up a tree-based interpreter.

    (As another example, many would say that a JIT is faster than a regular bytecode interpreter; but SquirrelFish is faster than some known JIT-based JS implementations.)

  2. Oliver

    Errr, the old interpreter was not “slow”, in fact it was the fastest JavaScript interpreter out there (WebKit3.1 has the fastest released interpreter, and the nightlies prior to merging SquirrelFish were the fast unreleased JS interpreter).

    That SquirrelFish is even faster does not change the fact that the old interpreter was fast.

  3. Mark Rowe

    Ruby is another popular interpreter that makes use of AST-walking as its primary means of execution. As you mention, it is a very naive approach to performance and there are higher-performance alternatives available. That said, WebKit’s old JavaScript interpreter was as as fast or faster than the other JavaScript implementations on all benchmarks (Mozilla, Opera, IE, etc).

    A better direction for thought may be why the naive AST-walking interpreter that JavaScriptCore previously used is as fast (and often faster) than the more “advanced” designs used in the interpreters of Mozilla, Opera and IE.

  4. Mark Rowe

    Oh, and it seems a little strange to pick on JavaScriptCore’s *old* interpreter when the new interpreter design matches quite closely with what you describe as being a better approach.

  5. Pinku

    Thanks for your comments. Rather than describe WebKit’s interpreter as “slow”, I should have said “an architecture that is known to be slow”. But then it’s faster than existing bytecode interpreters, which means the others are doing something terribly wrong. I should take a look at SpiderMonkey to see what’s going on in there.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s