4 ms·
Implementing Fast Interpreters
- silentbicycle 14y agoThis 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 http://article.gmane.org/gmane.comp.lang.lua.general/75426
- reginaldo 14y agoThis 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 http://lambda-the-ultimate.org/node/3851 (he goes by MikePall - without spaces)
- gruseom 14y agoHis 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.
- mraleph 14y agoYou 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 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]
- gruseom 14y agoSo 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.
- qznc 14y agoAnd here is more from Darek Mihocka: http://www.emulators.com/docs/nx25_nostradamus.htm http://www.emulators.com/docs/nx25_nostradamus.htm
- haberman 14y agoFrom 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.
- anamax 14y ago> 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 .
- chj 14y agoI 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.
- yoklov 14y agoInteresting 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-efficient-dispatch-tables/ http://eli.thegreenplace.net/2012/07/12/computed-goto-for-ef...
- SoftwareMaven 14y agoHow 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?
- corysama 14y agoYou 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-interpreter-with-pypy.html http://morepypy.blogspot.com/2011/04/tutorial-writing-interp... http://morepypy.blogspot.com/2011/04/tutorial-part-2-adding-jit.html http://morepypy.blogspot.com/2011/04/tutorial-part-2-adding-... http://tratt.net/laurie/tech_articles/articles/fast_enough_vms_in_fast_enough_time http://tratt.net/laurie/tech_articles/articles/fast_enough_v... http://tratt.net/laurie/research/talks/2012/kent_fast_enough.pdf http://tratt.net/laurie/research/talks/2012/kent_fast_enough...
- fijal 14y agoPyPy'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.
- _sh 14y agoAndy 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-javascriptcores-low-level-interpreter http://wingolog.org/archives/2012/06/27/inside-javascriptcor...
- chj 14y ago"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.
- sanxiyn 14y agoIt 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.
- ctz 14y ago400K or 40K seems more likely. Firstly, webkit is ~4M lines. Secondly, nobody would write '4000K' instead of '4M'.
- sanxiyn 14y agoIt's actually 4K.
- znmeb 14y agoAnton 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.