News for hackers. Stuff that matters.
Re:How fast can we make interpreted Python? by cwzwarich on Tuesday June 25, 2013 @10:32PM (#5943806)
There are a couple of things you want to do (some of which overlap with the article):

1) Use a register-based VM (with a sliding and growing register file) instead of a stack-based VM. In theory you can make a stack-based VM fast with lots of macroinstructions that fuse smaller operations together, but it isn't worth it.

2) Use inline caching for method calls, property accesses, and primitive operations that do type checks. In an interpreter you can modify the instruction stream even on platforms that disallow modification of executable code. I know this isn't the origin of the technique in bytecode interpreters, but here's a paper describing it in case it's not obvious:

http://www.lirmm.fr/~ducour/Doc-objets/ECOOP10/papers/6183/6...

3) Pick your value encoding carefully. You almost always want fast immediate integers. On 64-bit platforms it is quite common these days to repurpose some of the NaN range in IEEE doubles for type tags to enable storing doubles in immediate values.

4) Write your interpreter in assembly. Compilers generate terrible code for interpreters, even (especially?) with the use of computed goto / labels-as-values extensions. The register allocators of traditional compilers are designed to optimize loops by moving spill code outside of them and to reduce the impact of function calls. They will not be able to realistically allocate registers across different instruction bodies, and they won't be able to make the correct tradeoff about how much work to push into the slow path of instruction bodies.

5) Rearrange your instruction bodies based on execution / transition frequencies to improve instruction cache performance.

6) Pay close attention to the boundaries between your interpreter and the runtime libraries / the FFI. You don't want to take a bigger hit than you need to every time you call out to native code.

Re:How fast can we make interpreted Python? by JoshTriplett on Tuesday June 25, 2013 @11:42PM (#5944059)
> 3) Pick your value encoding carefully. You almost always want fast immediate integers. On 64-bit platforms it is quite common these days to repurpose some of the NaN range in IEEE doubles for type tags to enable storing doubles in immediate values.

That technique applies more to JavaScript, which uses doubles as the standard number type, than in Python, which has both integers and floats. Still a good idea to make sure that both native integers and native floats end up as unboxed native types in registers, though.

Re:How fast can we make interpreted Python? by cwzwarich on Wednesday June 26, 2013 @12:14AM (#5944151)
Thanks for the correction, I wasn't aware that Python uses floats. I would guess that most new languages starting today would use doubles instead of floats.
Re:How fast can we make interpreted Python? by laurencerowe on Wednesday June 26, 2013 @01:48AM (#5944405)
'''...almost all platforms map Python floats to IEEE-754 “double precision”.''' http://docs.python.org/2/tutorial/floatingpoint.html
Re:How fast can we make interpreted Python? by MostAwesomeDude on Wednesday June 26, 2013 @09:43AM (#5945922)
Python as a language requires the float type to have at least double precision. This is sadly not documented explicitly, but the big four Python implementations all respect this.
Re:How fast can we make interpreted Python? by JoshTriplett on Wednesday June 26, 2013 @10:12AM (#5946130)
I didn't mean that Python uses "float" instead of "double"; I meant that Python has both integer and floating-point types, not just floating-point types as in JavaScript.
Re:How fast can we make interpreted Python? by iskander on Tuesday June 25, 2013 @11:21PM (#5943979)
>Rearrange your instruction bodies based on execution / transition frequencies to improve instruction cache performance.

Do you mean...group all the frequent operations together so they overlap on cache lines? It's hard to tell how much this would help, have you tried it?

Re:How fast can we make interpreted Python? by cwzwarich on Wednesday June 26, 2013 @12:09AM (#5944134)
When I was working on WebKit we would rearrange instruction bodies to influence the generated code based on opcode statistics, but back then the interpreter was using computed goto, so there wasn't quite a direct connection between the placement of the input code and the generated code. It's unlikely that any two instruction implementations will overlap on cache lines, since they are all typically larger than a cache line, but more temporal coherency throughout code execution will improve performance, especially on CPUs with smaller caches.

You can do it automatically by gathering statistics on frequent instruction pairs. In practice greedy algorithms for code scheduling work fairly well, assuming you have meaningful statistics.

Re:How fast can we make interpreted Python? by mentat on Tuesday June 25, 2013 @11:49PM (#5944079)
Looks like he's contributed significantly to the Webkit javascript interpreter: https://www.webkit.org/blog/196/cameron-zwarich-is-a-webkit-...
Re:How fast can we make interpreted Python? by krichman on Tuesday June 25, 2013 @11:51PM (#5944088)
This is great, it's taken me months to learn all the things you just listed. Do you know of anywhere where this type of thing is discussed?
Re:How fast can we make interpreted Python? by cwzwarich on Wednesday June 26, 2013 @12:11AM (#5944143)
I mostly picked it up by working on interpreters and compilers, doing performance analysis on the generated code, trying to find all papers on the subject (some of them good, some of them really bad - you have to filter them yourself), and reading about what other implementations have been doing. It's also important to be able to run experiments quickly; you don't want to have to get every patch production-worthy before doing basic performance analysis.
Re:How fast can we make interpreted Python? by krichman on Wednesday June 26, 2013 @11:11PM (#5950539)
Aha! So I am on the right track! :)
Re:How fast can we make interpreted Python? by iskander on Tuesday June 25, 2013 @11:59PM (#5944111)
Language implementation sometimes gets discussed up on lambda-the-ultimate . Also, searching for anything and everything Mike Pall has written about VM design is probably worthwhile. Mozilla developers also have some pretty interesting blog posts about TraceMonkey, IonMonkey and all the other monkeys.
Re:How fast can we make interpreted Python? by krichman on Wednesday June 26, 2013 @11:15PM (#5950554)
I've actually seen most of those, I guess I'm more advanced than I thought :)
Re:How fast can we make interpreted Python? by iskander on Thursday June 27, 2013 @11:59AM (#5952968)
You're probably ready to write your own JIT -- I'd recommend making one for Python ;-)

I think after the low-hanging fruit above, there's lot of weird interpreter/compiler folklore on old usenet posts, Forth VM designs, random papers (like the Register vs. Stack machine showdown).

There are also some enlightening books like "Lisp in Small Pieces".

I'm at SciPy right now and I was just talking to the Julia developers yesterday about the need for a textbook, website, or wiki to gather all this disparate info in one place.

Want to help us get it started?

Re:How fast can we make interpreted Python? by krichman on Thursday June 27, 2013 @11:22PM (#5956009)
JIT? ...as soon as I get over my perfectionism long enough to finish the parser :)

I'd enjoy being on a project like that. Can I send you an email?

Re:How fast can we make interpreted Python? by iskander on Friday June 28, 2013 @11:38AM (#5958543)
Sure, it's alex dot rubinsteyn atop google's excellent email service.