6 ms·

Interpreter, Compiler, JIT

82 points by hnuser1243 11y ago

ndesaulniers 11y ago
Hey all, happy to take questions/feedback/criticism. Funny anecdote: while developing this post, once I got the JIT working I was very excited. I showed a few people in the office. Our CTO walked by and came to take a look. He's worked on numerous VMs in the past. SpiderMonkey's first JIT, TraceMonkey, being his PhD thesis. He took one look and asked "Is it self hosted." I replied, "well...not yet." To which his response was "pffft!" and walked off. I found that pretty funny. Maybe in the next blog post!
- vidarh 11y ago
  Dr. Gal studied under Prof. Michael Franz as well, who in turn did his PhD studies under Niklaus Wirth. If you haven't yet, you should read Franz' PhD thesis [1]. It was on load time code generation from what's effective a compressed representation of an ast that was designed for re-using generated code-segment by compying and template instantiation. So a JIT, but not generating from bytecode. Consider it somewhat like inserting a serialization/deserialization step right before your code-generation step, sort of, with some added optimizations to cache re-usable fragments. [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1424 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1...
- wvenable 11y ago
  You could try using C2BF[1] in an attempt to make it self hosting. :) [1] http://esolangs.org/wiki/C2BF http://esolangs.org/wiki/C2BF
  - ndesaulniers 11y ago
    Hey! I like the way you think, my friend!
- deleted 11y ago
  [deleted]
- nickpsecurity 11y ago
  wvenable's idea is good but a cheat. You referenced Wirth, who simplified assembly (eg P-code). Do something similar: extend BF with a macro language that simplifies it, build macros for BF-like programming constructs, use them to simplify programming the interpreter/compiler, and then host with that. If you want to do real BF, the very act of implementing those macros might help you mentally understand how to... one piece at a time lol... implement the real thing in vanilla BF. Which you can hand-implement in machine code if you want. Choose your level of masochism carefully. :)
  - ndesaulniers 11y ago
    The part I'm most curious about would how to make the JIT itself self hosting. If brainfuck's only method of I/O is getchar/putchar, the only way I can think of calling mmap is doing a stack buffer overflow attack based on the misrepresentation of tape. I remember hacking on Rust being a mind bending experience (the Rust compiler has been self hosting for a long time). Thinking in another level of abstraction is hurting my head. I think it would have to be able to output an macho64 executable. Oh man.
    - nickpsecurity 11y ago
      That does sound difficult. Maybe do it bare-metal on a simple, non-MMAP architecture* with basic routines coded in assembler. Both main interpreter and JIT'd code might reference those core functions. I know it's not directly solving the problem but I sneak around the impossible parts wherever possible. * Come to think of it, one of those microcontrollers or Java processors might come in handy here as they supply basic libs or RTOS's with primitive I/O functionality.
pron 11y ago
JITs don't have to repeat all their work every time they run. They can cache their output (this feature is planned for Java 9, I think). And while, as the article says, JITs are pretty much a necessity for languages with dynamic dispatch, which are nearly impossible to optimize ahead-of-time, they can be great for statically-typed languages, too: 1. Their ability to speculatively optimize (and then de-optimize when the assumption proves false and recompile) makes it possible for them to implement zero-cost abstractions, such as inlining polymorphic virtual calls. 2. They make it possible to optimize across shared libraries, even those that are loaded dynamically. To those interested in the future of JITs, I very much recommend watching one of the talks about Graal[1], HotSpot's (the OpenJDK JVM) next-gen JIT. Like HotSpot's current optimizing JIT compiler, it does speculative, profile-guided optimization, but exposes an API that lets the language designer (or even the programmer) to control optimization and code generation. It is also self-hosted (i.e. written in Java). It's still under heavy development but early results are promising. Even though it supports multithreading (which complicates things), it performs better (often much better) than PyPy when running Python[2] and on par with V8 when running JavaScript[3]. [1]: https://wiki.openjdk.java.net/display/Graal/Publications+and+Presentations https://wiki.openjdk.java.net/display/Graal/Publications+and... [2]: https://docs.google.com/spreadsheets/d/1fFMWcRIuPKt7wSAM5Ox9Rho4BBRhA5xgX6oemGhVxAA/edit#gid=1 https://docs.google.com/spreadsheets/d/1fFMWcRIuPKt7wSAM5Ox9... [3]: http://www.slideshare.net/ThomasWuerthinger/jazoon2014-slides http://www.slideshare.net/ThomasWuerthinger/jazoon2014-slide...
- vidarh 11y ago
  > JITs are pretty much a necessity for languages with dynamic dispatch, which are nearly impossible to optimize ahead-of-time, Depends what you consider "nearly impossible". A lot of compilers for dynamic languages are just awful for no particularly good reason so it's often hard to assess what is slow because it is hard and what is slow because the implementation disregards the last 30 years of experience with compiling dynamic languages. E.g. I'm working on an ahead-of-time Ruby compiler. While it will need a JIT component for cases where people call eval, and while Ruby is particularly nasty to compile for a variety of reasons, the method dispatch is easy to reduce to one indirection via a vtable (you just need to propagate method overrides down the class hierarchy and update the vtables, but updates to the methods is much rarer than cals so it's ok for it to be more expensive), equivalent to C++ virtual member functions (though C++ compilers have better hope of being able to optimize away the virtual call). Despite the pathological cases possible because of the singly rooted object hierarchy, for most typical applications the wasted space in vtables (for method slots for methods that are unimplemented in a specific branch of the class hiearchy) is easily compensated for by e.g. needing less bookkeeping for methods that are known statically at compile time (which is the vast majority for most applications). If you're willing to compile a fallback path and suitable guards, you can sometimes optimize away many indirections entirely and even inline code ahead of time even for languages like Ruby (incidentally for example of that you can look at the work Chris Seaton has done on a JRuby Truffle/Graal backend - while that does these optimizations at runtime, many of them are applicable ahead of time too, though the JIT can get the advantage of not having to generate code for fallback cases unless they're actually needed at runtime) Note that I agree with you that JIT's have many advantages. At the same time, while I love the flexibility of dynamic languages, I prefer the smallest number of moving wheels possible in production environment. Spent too long doing devops.. Makes me lament the lack of attention to AOT/"as static as possible" compilers for dynamic languages.
ndesaulniers 11y ago
Over in the comments in proggit the inventor of brainfuck, Urban Müller, showed up and gave the Chuck Norris thumbs up: https://www.reddit.com/r/programming/comments/377ov9/interpreter_compiler_jit/crkkrz4 https://www.reddit.com/r/programming/comments/377ov9/interpr...
vardump 11y ago
Maybe one day someone will write a native JIT for x86[-64]. Native x86 code in, optimized native x86 code out. It should be possible to JIT native code and run it faster than running the native code directly! It could do: 1) Peephole optimizations (and known sequence/function replacement). Utilize target instruction set extensions. 2) "Constant" folding. Replace code that processes values that can be proven to be immutable with a constant. Also removes unnecessary branches. Guards at loads, indirect stores, by marking page read only, etc. 3) Vectorization. This includes widening existing vectorization if target instruction set supports it. 4) Loadable library call inlining. This could even mean inlining system calls, but of course in that case the JIT would need to be running in kernel... 5) Profile guided optimization. Of course there are some very hard problems. For example, there'd need to be guards for the case the assumed constant value does change. Or that unexpected call target occurs. Etc. Maybe this system could learn possible call targets and unexpectedly changing "constants".
- lmz 11y ago
  Wasn't that what some x86 emulators did before hardware virtualization? (maybe not to that extent).
  - dfox 11y ago
    Translating code for one architecture into code for host (possibly same) architecture is what Qemu does. But Qemu does not do any significant optimizations in this process as it attempts to do this without extensive knowledge of host architecture (it does not even directly generate separate instructions). Other thing that comes to mind is HP Dynamo (http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html), which essentially is PA-RISC on PA-RISC optimizing JIT VM (that also does trace-driven optimization).
- ndesaulniers 11y ago
  Doesn't LTO do some of these things?
  - 11y ago

82 points by hnuser1243 11y ago

Hey all, happy to take questions/feedback/criticism. Funny anecdote: while developing this post, once I got the JIT working I was very excited. I showed a few people in the office. Our CTO walked by and came to take a look. He's worked on numerous VMs in the past. SpiderMonkey's first JIT, TraceMonkey, being his PhD thesis. He took one look and asked "Is it self hosted." I replied, "well...not yet." To which his response was "pffft!" and walked off. I found that pretty funny. Maybe in the next blog post!

vidarh 11y ago
Dr. Gal studied under Prof. Michael Franz as well, who in turn did his PhD studies under Niklaus Wirth. If you haven't yet, you should read Franz' PhD thesis [1]. It was on load time code generation from what's effective a compressed representation of an ast that was designed for re-using generated code-segment by compying and template instantiation. So a JIT, but not generating from bytecode. Consider it somewhat like inserting a serialization/deserialization step right before your code-generation step, sort of, with some added optimizations to cache re-usable fragments. [1] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1424 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1...
wvenable 11y ago
You could try using C2BF[1] in an attempt to make it self hosting. :) [1] http://esolangs.org/wiki/C2BF http://esolangs.org/wiki/C2BF
- ndesaulniers 11y ago
  Hey! I like the way you think, my friend!
deleted 11y ago
[deleted]
nickpsecurity 11y ago
wvenable's idea is good but a cheat. You referenced Wirth, who simplified assembly (eg P-code). Do something similar: extend BF with a macro language that simplifies it, build macros for BF-like programming constructs, use them to simplify programming the interpreter/compiler, and then host with that. If you want to do real BF, the very act of implementing those macros might help you mentally understand how to... one piece at a time lol... implement the real thing in vanilla BF. Which you can hand-implement in machine code if you want. Choose your level of masochism carefully. :)
- ndesaulniers 11y ago
  The part I'm most curious about would how to make the JIT itself self hosting. If brainfuck's only method of I/O is getchar/putchar, the only way I can think of calling mmap is doing a stack buffer overflow attack based on the misrepresentation of tape. I remember hacking on Rust being a mind bending experience (the Rust compiler has been self hosting for a long time). Thinking in another level of abstraction is hurting my head. I think it would have to be able to output an macho64 executable. Oh man.
  - nickpsecurity 11y ago
    That does sound difficult. Maybe do it bare-metal on a simple, non-MMAP architecture* with basic routines coded in assembler. Both main interpreter and JIT'd code might reference those core functions. I know it's not directly solving the problem but I sneak around the impossible parts wherever possible. * Come to think of it, one of those microcontrollers or Java processors might come in handy here as they supply basic libs or RTOS's with primitive I/O functionality.

pron 11y ago

JITs don't have to repeat all their work every time they run. They can cache their output (this feature is planned for Java 9, I think). And while, as the article says, JITs are pretty much a necessity for languages with dynamic dispatch, which are nearly impossible to optimize ahead-of-time, they can be great for statically-typed languages, too: 1. Their ability to speculatively optimize (and then de-optimize when the assumption proves false and recompile) makes it possible for them to implement zero-cost abstractions, such as inlining polymorphic virtual calls. 2. They make it possible to optimize across shared libraries, even those that are loaded dynamically. To those interested in the future of JITs, I very much recommend watching one of the talks about Graal[1], HotSpot's (the OpenJDK JVM) next-gen JIT. Like HotSpot's current optimizing JIT compiler, it does speculative, profile-guided optimization, but exposes an API that lets the language designer (or even the programmer) to control optimization and code generation. It is also self-hosted (i.e. written in Java). It's still under heavy development but early results are promising. Even though it supports multithreading (which complicates things), it performs better (often much better) than PyPy when running Python[2] and on par with V8 when running JavaScript[3]. [1]: https://wiki.openjdk.java.net/display/Graal/Publications+and+Presentations https://wiki.openjdk.java.net/display/Graal/Publications+and... [2]: https://docs.google.com/spreadsheets/d/1fFMWcRIuPKt7wSAM5Ox9Rho4BBRhA5xgX6oemGhVxAA/edit#gid=1 https://docs.google.com/spreadsheets/d/1fFMWcRIuPKt7wSAM5Ox9... [3]: http://www.slideshare.net/ThomasWuerthinger/jazoon2014-slides http://www.slideshare.net/ThomasWuerthinger/jazoon2014-slide...

vidarh 11y ago
> JITs are pretty much a necessity for languages with dynamic dispatch, which are nearly impossible to optimize ahead-of-time, Depends what you consider "nearly impossible". A lot of compilers for dynamic languages are just awful for no particularly good reason so it's often hard to assess what is slow because it is hard and what is slow because the implementation disregards the last 30 years of experience with compiling dynamic languages. E.g. I'm working on an ahead-of-time Ruby compiler. While it will need a JIT component for cases where people call eval, and while Ruby is particularly nasty to compile for a variety of reasons, the method dispatch is easy to reduce to one indirection via a vtable (you just need to propagate method overrides down the class hierarchy and update the vtables, but updates to the methods is much rarer than cals so it's ok for it to be more expensive), equivalent to C++ virtual member functions (though C++ compilers have better hope of being able to optimize away the virtual call). Despite the pathological cases possible because of the singly rooted object hierarchy, for most typical applications the wasted space in vtables (for method slots for methods that are unimplemented in a specific branch of the class hiearchy) is easily compensated for by e.g. needing less bookkeeping for methods that are known statically at compile time (which is the vast majority for most applications). If you're willing to compile a fallback path and suitable guards, you can sometimes optimize away many indirections entirely and even inline code ahead of time even for languages like Ruby (incidentally for example of that you can look at the work Chris Seaton has done on a JRuby Truffle/Graal backend - while that does these optimizations at runtime, many of them are applicable ahead of time too, though the JIT can get the advantage of not having to generate code for fallback cases unless they're actually needed at runtime) Note that I agree with you that JIT's have many advantages. At the same time, while I love the flexibility of dynamic languages, I prefer the smallest number of moving wheels possible in production environment. Spent too long doing devops.. Makes me lament the lack of attention to AOT/"as static as possible" compilers for dynamic languages.

ndesaulniers 11y ago

Over in the comments in proggit the inventor of brainfuck, Urban Müller, showed up and gave the Chuck Norris thumbs up: https://www.reddit.com/r/programming/comments/377ov9/interpreter_compiler_jit/crkkrz4 https://www.reddit.com/r/programming/comments/377ov9/interpr...

vardump 11y ago

Maybe one day someone will write a native JIT for x86[-64]. Native x86 code in, optimized native x86 code out. It should be possible to JIT native code and run it faster than running the native code directly! It could do: 1) Peephole optimizations (and known sequence/function replacement). Utilize target instruction set extensions. 2) "Constant" folding. Replace code that processes values that can be proven to be immutable with a constant. Also removes unnecessary branches. Guards at loads, indirect stores, by marking page read only, etc. 3) Vectorization. This includes widening existing vectorization if target instruction set supports it. 4) Loadable library call inlining. This could even mean inlining system calls, but of course in that case the JIT would need to be running in kernel... 5) Profile guided optimization. Of course there are some very hard problems. For example, there'd need to be guards for the case the assumed constant value does change. Or that unexpected call target occurs. Etc. Maybe this system could learn possible call targets and unexpectedly changing "constants".

lmz 11y ago
Wasn't that what some x86 emulators did before hardware virtualization? (maybe not to that extent).
- dfox 11y ago
  Translating code for one architecture into code for host (possibly same) architecture is what Qemu does. But Qemu does not do any significant optimizations in this process as it attempts to do this without extensive knowledge of host architecture (it does not even directly generate separate instructions). Other thing that comes to mind is HP Dynamo (http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html http://www.hpl.hp.com/techreports/1999/HPL-1999-78.html), which essentially is PA-RISC on PA-RISC optimizing JIT VM (that also does trace-driven optimization).
ndesaulniers 11y ago
Doesn't LTO do some of these things?
- 11y ago