Implementing Fast Interpreters | Hacker News Reader

Implementing Fast Interpreters

nominolo.blogspot.com

161 pointsmalloc4721 comments

This post by Mike Pall has a bit more depth about the assembly interpreter details, particularly about stuff like branch prediction: http://article.gmane.org/gmane.comp.lang.lua.general/75426

This article is awesome. I had read it before but lost track of it. It was nice reading it again. Mike's code is a bliss to read, I don't know how to explain, it shows such a clear way of thinking... I believe one of the best ways to learn about dynamic language implementation this days is by reading his code and the things he writes when participating in discussion forums. He is the real deal.

For an example see: http://lambda-the-ultimate.org/node/3851 (he goes by MikePall - without spaces)

His writing is exceedingly lucid as well. Thanks for that link – there is a lot of good stuff in that thread. I found it interesting, for example, that Mike said that there's no intrinsic reason a JS JIT couldn't compete with LuaJIT.

You might be surprised but V8 these days is pretty close to LJ2 performance. LJ2 does amazingly good job on loopy code but is easily outperformed by V8 on OOPy polymorphic one: e.g. DeltaBlue benchmark ported to Lua was something like 5-10 times slower on LJ2 than on V8 last time I checked.

[here is my port of DeltaBlue: https://github.com/mraleph/deltablue.lua, I admit that I might have screwed up porting it, but internal benchmark verification checks did not catch anything]

So the difference between V8 and LJ2 is more in what kinds of optimization they prioritize, than in overall superior performance by LJ2? Yes, I am surprised to hear that, in a good way. The interesting thing about LJ2 (as distinct from Lua the language) is that it broke such impressive new ground for what is possible in optimizing dynamic languages.

And here is more from Darek Mihocka: http://www.emulators.com/docs/nx25_nostradamus.htm

From that link: "Really what x86 needs is a PREDECODE instruction, a code equivalent of the PREFETCH data instruction, which takes a code pointer as an operand and hints to the CPU that it should start decoding that code."

I'm not sure this makes sense as proposed. Where is the CPU going to put these pre-decoded instructions? The instruction decoder is the first stage of a pipeline, and the decoded instructions are usually fed directly to subsequent pipeline stages. When a branch is predicted, the stream of instructions continues to be decoded and executed in program order from the predicted branch target, and the pipeline stays full. But you can't use this "PREDECODE" instruction to keep the pipeline full, because you can't speculatively execute instructions unless you have already executed all of their dependent instructions (ie. all the instructions prior to the branch that will jump to the target we are feeing to PREDECODE).

What would make sense (to me at least) is if you could have an instruction that tells the branch predictor "the branch at address X will most likely jump to address Y next time." The predictor could then update its tables to adjust the prediction it will make. It seems like this should be pretty straightforward; since the branch predictor and instruction decoder both live at the head of the pipeline, there shouldn't be any danger that the hint is registered only after the branch has already been predicted.

> I'm not sure this makes sense as proposed. Where is the CPU going to put these pre-decoded instructions?

I don't know what folks do now, but Intel had a trace cache as of a few years ago. That trace cache contains decoded instructions.

> What would make sense (to me at least) is if you could have an instruction that tells the branch predictor "the branch at address X will most likely jump to address Y next time."

US Patent 5,949,995 .

I happen to be in the assembly interpreter business, and I agree with Mike 100%. It is all about use registers efficiently, and avoid branch like hell. But just forget whatever your compiler promises you, you are better off with your own hands.

Interesting article. If you're interested in the labels as values approach he mentioned, I read a recent article by Eli Bendersky, here: http://eli.thegreenplace.net/2012/07/12/computed-goto-for-ef...

How do projects like Pypy help this? I know Pypy wants to be able to build fast, cross-platform interpreters; but how close to reality is that?

You can write an interpreter in RPython and PyPy will automatically generate a just-in-time compiler for your interpreter.

http://morepypy.blogspot.com/2011/04/tutorial-writing-interp...

http://morepypy.blogspot.com/2011/04/tutorial-part-2-adding-...

http://tratt.net/laurie/tech_articles/articles/fast_enough_v...

http://tratt.net/laurie/research/talks/2012/kent_fast_enough...

PyPy's focus so far has been on the JIT. The interpreter part is mostly an equivalent of a brain-dead C implementation. Overall it does not matter for long running programs (like web servers), but the warmup times are kind of horrible.

That said, in a language like Python, the interpretation overhead matters much less, because bytecodes are typically very "fat" and involve say multiple dictionary lookups (which are way more costly than bytecode dispatch lookup). If I were to optimize the interpreter, I would start with specialized bytecodes, that avoids fatness of the bytecodes first.

"LuaJIT 2 has interpreters for 6 architectures of around 4000K lines per architecture (ARMv6, MIPS, PPC, PPCSPE/Cell, x86, x86-64)."

Is that number 4000K correct? That sounds awfully big for me.

It seems to be a typo for 4K. For beta9:

  4115 buildvm_arm.dasc
  4873 buildvm_ppc.dasc
  3704 buildvm_ppcspe.dasc
  6458 buildvm_x86.dasc

x86 and x86-64 share code.

400K or 40K seems more likely. Firstly, webkit is ~4M lines. Secondly, nobody would write '4000K' instead of '4M'.

It's actually 4K.

Andy Wingo's exploration of V8's Lithium interpreter [1] describes the reasoning behind the Ruby offline assembly generator.

Actually, if you're reading the original linked article, you should also be reading Andy's series on V8.

[1] http://wingolog.org/archives/2012/06/27/inside-javascriptcor...

The article you are linking to is about LLInt --- JavaScriptCore's interpreter.

V8 does not have an interpreter. Lithium is V8's (low level) intermediate representation.

Thanks for that clarification--I find myself confusing V8 for JSC every now and then.

Anton Ertl and David Gregg cracked this nut a long time ago with gForth / vmgen! It's only when you add registers to their basic two-stack model, like Parrot does, that you gain any more speed.

Reply on news.ycombinator.com