5 ms·
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) ins
by cwzwarich 13y ago
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/61830429.pdf 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.
- iskander 13y ago>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?
- mentat 13y agoLooks like he's contributed significantly to the Webkit javascript interpreter: https://www.webkit.org/blog/196/cameron-zwarich-is-a-webkit-reviewer/ https://www.webkit.org/blog/196/cameron-zwarich-is-a-webkit-...
- cwzwarich 13y agoWhen 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.
- JoshTriplett 13y ago> 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.
- cwzwarich 13y agoThanks 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.
- laurencerowe 13y ago'''...almost all platforms map Python floats to IEEE-754 “double precision”.''' http://docs.python.org/2/tutorial/floatingpoint.html http://docs.python.org/2/tutorial/floatingpoint.html
- MostAwesomeDude 13y agoPython 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.
- JoshTriplett 13y agoI 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.
- krichman 13y agoThis 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?
- iskander 13y agoLanguage 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.
- krichman 13y agoI've actually seen most of those, I guess I'm more advanced than I thought :)
- iskander 13y agoYou'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?