Hacker News Reader

Comment by DannyBee | Hacker News Reader

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_pr... and http://blog.sigfpe.com/2009/05/three-projections-of-doctor-f...

View on HN

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.

"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.

> This actually was true then too, FWIW.

Ah, you were referring to a era before my time, and it seems I made some false assumptions about motivations back then. Thanks for the correction.

> 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.

Are you referring to meta-compilation techniques here, or the techniques for runtime type modeling developed to drive type-specialization of dynamic code?

If you are referring to the latter, I agree completely. If the former, I'd argue that the runtime type modeling work brings something new to the table which changes the dynamic. But in general I agree with your point - the main difference between now and then is the sheer level of engineering effort by multiple parties, cross-pollination of ideas, and other prosaic matters.

In terms of research, my exposure has been to two main pedigrees of thought in runtime type modeling serving to drive type-specialization of dynamic code: the Self work by Ungar and friends, and Type-Inference by Hackett and Guo (both of whom I have the pleasure of working closely with).

> While i'm not sure how much it matters, i guess i'd just point out these are not different concerns than history had

It always helps to understand the motivations and efforts of what came before, so thanks for the clarification. Any more insight or information or references would be welcome.

> I certainly hope you succeed, FWIW.

This is nbp's baby, but yeah, I hope it succeeds as well. I will never get bored of working in this space :)

Where do you draw the line between engineering and research?

Graal has shown that you can use interpreter specialization to create a Javascript engine that's essentially as fast as V8. It relies on a lot of clever tricks to do that, like partial escape analysis. Graal has generated quite a few published research papers. It seems like both engineering and research, to me.

This is obviously a hard line to draw.

I tend to draw it at "research produces new things that were not previously known, engineering may produce new insights or improvements of things that were already known".

(but again, I admit this is not a very very bright line)

I consider graal to be good engineering. It is a new arrangement and engineering of existing techniques. That will in fact, often produce new papers.

For example, I built the first well-engineered value based partial redundancy elimination in GCC. before that, there were zero production implementations, and it was considered "too slow to be productionizable" until i took a whack at it. I helped with some papers on it. It's not research, just good engineering. The theory was known, etc. I just made it practical. That wasn't research.

Another example: LLVM now has the first shipping implementation ever of an efficient incremental dominator tree updating scheme (that i'm aware of. GCC has a scheme to do it for some things, but it's not efficient). Again, previously not efficient. Theory has been published. Again, making it work well is just good engineering.

Another example: LLVM's phi placement algorithm is a linear time algorithm based on sreedhar and gao's work. If you read further research papers, they actually pretty much crap on this algorithm as very inefficient.

It turns out they were just bad at implementing it effectively, and LLVM's version is way faster than anything else out there. Is it research because our results are orders of magnitude better than anything else out there? No. It may be cool, it may be amazing, etc, but it's still engineering.

Remember that conferences like PLDI and CGO accept papers not just on research, but on implementation engineering.

All that said, i also don't consider trying to differentiate heavily between research and engineering to be that horribly interesting (though i know some prize one or the other).

> 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.

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

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.

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.

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...

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.

Are they using the generated IR, or using the AST of the interpreter code? The latter would probably be more amenable to JITification.

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.

> 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.)

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.

I admit that I'm quite curious about determining exactly what features could be left out of maximally-explicit Rust, because it would determine the obvious MVP for an alternative compiler, that could technically compile all Rust code with the caveat that you would need to first losslessly and automatically transform the source (which theoretically shouldn't be too hard to add the Rust compiler, e.g. it already has the capability to print Rust source post-macro expansion). Without macros, you'd need neither an implementation of pattern macros nor syntax extensions; without inferred types, you'd need neither a trait resolution engine nor anything of Hindley-Milner; with every identifier fully qualified you wouldn't need any name resolution rules... and we've already established that a borrow checker is unnecessary to implement if your goal is to merely compile Rust code that has already been typechecked. All that together means that you could have a legitimately useful alternative backend with so, so much less work on behalf of the implementor!

This is why I wish that there was a higher-level, maintained api for the compiler internals, to make it easier to do these kinds of experiments

This is kind of what mrustc does? It's a Rust-to-C compiler in C++; one which assumes the Rust program is correct (i.e. passes type/borrow check).

But you still need to resolve types to do dispatch, so that's a nontrivial amount of work.

mrustc can currently compile rustc, but the produced rustc doesn't pass the entire rustc testsuite (yet).

A colleague of mine was considering writing a Rust-to-C++ compiler that was similar, but offloading most of the dispatch/resolution work onto C++. This is actually possible, you can turn method dispatch and autoderef into template resolution. You can do stuff to fake type inference too if you know the program is correct already. This is much harder however and I'm not yet sure if it's 100% possible without doing some typechecking in the Rust-to-C++ compiler itself.

You could however take rustc --unpretty=typed (or whatever that option is these days) output and transform that really easily.

This requires you to be able to independently verify that the two ASTs are equal if you resugar, because you can't trust rustc's output for this. In fact, the poc trusting trust attack I wrote[1] would still go under the radar here.

Verifying ASTs as semantically equal is much less work. But there's a loophole here, it is possible to add type annotations to type inference'd Rust to get different behavior. This is because (among other things) integers are inferred more loosely (an uninferable integer type is defaulted as u32). It's possible that a trusting trust attack would be able to propagate itself merely by flipping around the results of inference.

Even if we looked out for that, you still have the problem of dispatch, where a backdoored rustc could change the method being dispatched to be a different trait. Now this isn't something that would work if you assume that the original code was code which compiled fine with rustc (because rustc complains when there's unqualified ambiguity). But we can't actually trust the original compiler to have handled this correctly either!

In both cases there would be need to be traces of weird code in rustc for this to work, but it might be possible to hide this.

(This is also somewhat a problem for mrustc, but to much a lesser degree)

[1]: http://manishearth.github.io/blog/2016/12/02/reflections-on-...

Reply on news.ycombinator.com