4 ms·

For those wondering, it's a specializer, applied to an interpreter, to specialize the interpreter into a jit. This is a pretty well explored technique, it's ra

For those wondering, it's a specializer, applied to an interpreter, to specialize the interpreter into a jit. This is a pretty well explored technique, it's rarely done these days because historically, people could not get good enough performance. (I am not trying to knock them, just put it in context) For more context on how you'd do something like this, read this: https://en.wikipedia.org/wiki/Partial_evaluation#Futamura_projections https://en.wikipedia.org/wiki/Partial_evaluation#Futamura_pr... and http://blog.sigfpe.com/2009/05/three-projections-of-doctor-futamura.html http://blog.sigfpe.com/2009/05/three-projections-of-doctor-f...

stefano 9y ago
Isn't this what pypy does? pypy does the specialization at runtime, maybe this does it at (interpreter) compile time?
- steveklabnik 9y ago
  Given how HolyJIT is implemented (with compiler plugins etc), I believe that it does this work at compile time, yes. I haven't actually confirmed this though.
  - nbpname 9y ago
    The goal is to optimize the code both at compile-time and at run-time. We need to optimize it at compile time to prevent slow start-up, and we need to optimize it at run-time to benefit from profile guided optimizations.
- bjt 9y ago
  It sounds very similar to what RPython and Pypy do. You can even use RPython to create a VM for a language besides Python. I read a good blog post from an author who had done that 5 years ago. http://tratt.net/laurie/blog/entries/fast_enough_vms_in_fast_enough_time.html http://tratt.net/laurie/blog/entries/fast_enough_vms_in_fast...
kannanvijayan 9y ago
The state of the art in jit compilation has advanced quite a bit since then, and another difference between the days of old and new is that this is being targeted at runtime code generation, which naturally trades off throughput of generated code for speed-of-generation. Especially for web pages, speed-of-generation, and the stability of the resulting code under polymorphism (so that jitcode with type assumptions doesn't become invalid), is paramount. These issues, as well as developer velocity in translating VM features into optimized VM features, figure more prominently in our problem set than I would expect it historically did. We sat down with nbp and went through his proposal in some detail yesterday. I'm reasonably sold on the theoretical soundness of the idea (actually I was excited about it from the first time he proposed it - hand optimizing every new JS feature is soul-sucking, and Graal already demonstrated the feasibility of variant of the concept). As with any far-reaching idea, though, there are risks associated with it. And we definitely can't rewrite Spidermonkey from scratch. Personally, I think prototyping the tech on top of a small toy language (objects, properties, proto chains, primitive types, functions), proving out the toy implementation, and then examining how we can incrementalize our transition to HolyJIT is the way to go. I think a prerequisite is a good codegen backend that we can target. Cretonne is a good candidate, but we need features that aren't on its roadmap - primarily support for on-stack-invalidation. There's a bit of a road ahead of us on this concept. I think we have a good rough idea of a viable path from here to there, but we are yet in early stages with this.
- DannyBee 9y ago
  "The state of the art in jit compilation has advanced quite a bit since then" Since when? Since the 70's? Sure. But since the 90's, not really in terms of techniques, only in terms of engineering and feasibility of advanced techniques. It's not that there is no research, mind you, but it's definitely more engineering than research. That also doesn't make it any less cool, exciting, etc. "another difference between the days of old and new is that this is being targeted at runtime code generation, which naturally trades off throughput of generated code for speed-of-generation." This actually was true then too, FWIW. "These issues, as well as developer velocity in translating VM features into optimized VM features, figure more prominently in our problem set than I would expect it historically did." While i'm not sure how much it matters, i guess i'd just point out these are not different concerns than history had :) I certainly hope you succeed, FWIW.
cwzwarich 9y ago
It also doesn't help that they're specializing an interpreter generated by a compiler. General-purpose compilers generate pretty bad code for interpreters. If the interpreter was written by hand and had some associated metadata, I think there would be a slightly higher chance of success here.
- wyager 9y ago
  Are they using the generated IR, or using the AST of the interpreter code? The latter would probably be more amenable to JITification.
  - steveklabnik 9y ago
    Rust has several layers of IR: AST -> HIR -> MIR -> LLVM IR This operates at the MIR layer. You can sort of think of MIR as "core Rust", in that it's the final, desugared form of everything. This is why the non-lexical lifetime stuff has taken a while; the precursor to that is "port the borrow checker to MIR". MIR/HIR are also fairly new; using MIR is only a year old.
    - kibwen 9y ago
      > You can sort of think of MIR as "core Rust", in that it's the final, desugared form of everything. Though I don't want anyone to get the impression that MIR is a source-compatible subset of Rust; it's a pretty different thing in its own right. (Worth clarifying because one could imagine a "fully-desugared" maximally-explicit subset of Rust, where e.g. all method calls are maximally disambiguated via UFCS, all types are explicitly annotated, no lifetimes are elided, all macros are expanded, etc.)
      - nickpsecurity 9y ago
        That is what I imagined when the Karger/Thompson attack came up with regards to Rust. The simplest cheat would be mapping low-level Rust to a safe subset of C. Automatically or hand-convert the source for Rust compiler. Then, run that through CompCert. A Csmith-style program run through both versions of Rust compiler might also catch errors in one or both. One might also use the C tooling to find errors in the Rust compiler or apps. And so on. First step that was necessary would be converting the Rust to its lowest-level form. That sounds like the fully-desugared" form you describe.
qznc 9y ago
> people could not get good enough performance PyPy and Graal show good performance. The can be considered special cases of partial evaluation, where the first Futamura project works. They are not generic enough for the second and third projections, though. They even require some help (e.g. annotations) for the first.

stefano 9y ago

Isn't this what pypy does? pypy does the specialization at runtime, maybe this does it at (interpreter) compile time?

steveklabnik 9y ago
Given how HolyJIT is implemented (with compiler plugins etc), I believe that it does this work at compile time, yes. I haven't actually confirmed this though.
- nbpname 9y ago
  The goal is to optimize the code both at compile-time and at run-time. We need to optimize it at compile time to prevent slow start-up, and we need to optimize it at run-time to benefit from profile guided optimizations.
bjt 9y ago
It sounds very similar to what RPython and Pypy do. You can even use RPython to create a VM for a language besides Python. I read a good blog post from an author who had done that 5 years ago. http://tratt.net/laurie/blog/entries/fast_enough_vms_in_fast_enough_time.html http://tratt.net/laurie/blog/entries/fast_enough_vms_in_fast...

kannanvijayan 9y ago

The state of the art in jit compilation has advanced quite a bit since then, and another difference between the days of old and new is that this is being targeted at runtime code generation, which naturally trades off throughput of generated code for speed-of-generation. Especially for web pages, speed-of-generation, and the stability of the resulting code under polymorphism (so that jitcode with type assumptions doesn't become invalid), is paramount. These issues, as well as developer velocity in translating VM features into optimized VM features, figure more prominently in our problem set than I would expect it historically did. We sat down with nbp and went through his proposal in some detail yesterday. I'm reasonably sold on the theoretical soundness of the idea (actually I was excited about it from the first time he proposed it - hand optimizing every new JS feature is soul-sucking, and Graal already demonstrated the feasibility of variant of the concept). As with any far-reaching idea, though, there are risks associated with it. And we definitely can't rewrite Spidermonkey from scratch. Personally, I think prototyping the tech on top of a small toy language (objects, properties, proto chains, primitive types, functions), proving out the toy implementation, and then examining how we can incrementalize our transition to HolyJIT is the way to go. I think a prerequisite is a good codegen backend that we can target. Cretonne is a good candidate, but we need features that aren't on its roadmap - primarily support for on-stack-invalidation. There's a bit of a road ahead of us on this concept. I think we have a good rough idea of a viable path from here to there, but we are yet in early stages with this.

DannyBee 9y ago
"The state of the art in jit compilation has advanced quite a bit since then" Since when? Since the 70's? Sure. But since the 90's, not really in terms of techniques, only in terms of engineering and feasibility of advanced techniques. It's not that there is no research, mind you, but it's definitely more engineering than research. That also doesn't make it any less cool, exciting, etc. "another difference between the days of old and new is that this is being targeted at runtime code generation, which naturally trades off throughput of generated code for speed-of-generation." This actually was true then too, FWIW. "These issues, as well as developer velocity in translating VM features into optimized VM features, figure more prominently in our problem set than I would expect it historically did." While i'm not sure how much it matters, i guess i'd just point out these are not different concerns than history had :) I certainly hope you succeed, FWIW.

cwzwarich 9y ago

It also doesn't help that they're specializing an interpreter generated by a compiler. General-purpose compilers generate pretty bad code for interpreters. If the interpreter was written by hand and had some associated metadata, I think there would be a slightly higher chance of success here.

wyager 9y ago
Are they using the generated IR, or using the AST of the interpreter code? The latter would probably be more amenable to JITification.
- steveklabnik 9y ago
  Rust has several layers of IR: AST -> HIR -> MIR -> LLVM IR This operates at the MIR layer. You can sort of think of MIR as "core Rust", in that it's the final, desugared form of everything. This is why the non-lexical lifetime stuff has taken a while; the precursor to that is "port the borrow checker to MIR". MIR/HIR are also fairly new; using MIR is only a year old.
  - kibwen 9y ago
    > You can sort of think of MIR as "core Rust", in that it's the final, desugared form of everything. Though I don't want anyone to get the impression that MIR is a source-compatible subset of Rust; it's a pretty different thing in its own right. (Worth clarifying because one could imagine a "fully-desugared" maximally-explicit subset of Rust, where e.g. all method calls are maximally disambiguated via UFCS, all types are explicitly annotated, no lifetimes are elided, all macros are expanded, etc.)
    - nickpsecurity 9y ago
      That is what I imagined when the Karger/Thompson attack came up with regards to Rust. The simplest cheat would be mapping low-level Rust to a safe subset of C. Automatically or hand-convert the source for Rust compiler. Then, run that through CompCert. A Csmith-style program run through both versions of Rust compiler might also catch errors in one or both. One might also use the C tooling to find errors in the Rust compiler or apps. And so on. First step that was necessary would be converting the Rust to its lowest-level form. That sounds like the fully-desugared" form you describe.

qznc 9y ago

> people could not get good enough performance PyPy and Graal show good performance. The can be considered special cases of partial evaluation, where the first Futamura project works. They are not generic enough for the second and third projections, though. They even require some help (e.g. annotations) for the first.