Just-in-time code generation within WebAssembly
wingolog.org
wingolog.org
I’m not seeing how using the first Futamura projection (targeting wasm) wouldn’t both result in a significantly smaller module size and give more opportunity to optimize/specialize the code as it could perform offline analysis. One could even use the second Futamura projection along with the dynamic code loading from TFA and get an online jit compiler virtually for free.
If I was getting paid megabucks to do these types of things that’s where I’d spend my research time.
I'm not that familiar with this area, but tried to reacquaint myself by skimming through http://www.itu.dk/people/sestoft/pebook/jonesgomardsestoft-l... (via http://www.itu.dk/people/sestoft/pebook/), especially Chapter 11, "Partial Evaluation for the C Language", which I figured would highlight some the biggest potential roadblocks, even if it's not directly pertinent (i.e. in our case we might be symbolically executing a strongly typed functional language implementation of a WASM interpreter).
It doesn’t need fancy stuff like arrays or objects since it just operates on the sandboxed wasm memory. Probably need some runtime system to deal with memory management &etc but that’s just some extra code tacked onto the module.
If one wanted to get all fancy it would be:
code -> ast -> ir -> optimizer -> partial eval -> wasm
Or just a simple:
code -> ast -> tree walker -> wasm
There’s some pretty good algorithms for the first case where you get pretty close to optimal code without having to leave SSA form I’ve been reading about recently. In fact, I totally forgot about the Futamura transformations until I was reading TFA and was wondering why it wouldn’t work.
—edit—
I guess the first case is just a traditional compiler and it would probably not benefit from partial evaluation because there’s also an efficient algorithm that’s part of the mentioned reading to transform SSA -> AST which could be adapted to wasm output quite easily…which is on my laptop and I’m on my phone so…
As an example, imagine a simple case of a program that outputs N verses of the "bottles of beer on the wall" song. A naive partial evaluator given an N will produce the whole output (potentially multi-gigabyte) string during partial evaluation, even if loading and printing that whole string may be slower than just running the original code.
Look at Pypy and GraalVM for partial evaluation in practice; none of it is free and there's a lot of engineering and tweaking involved, not to mention how it can affect debugging.
We use similar techniques to power Webvm[1], an X86 Virtual Machine that runs linux programs in the browser.
A proper Wasm JIT API in JavaScript would be even better of course, but as the article says, cool things are already possible right now.
I expect to see more projects doing Wasm just-in-time compilation in the future (I believe that V86[2] also already does it)
[1]: https://webvm.io/
A Wasm trampoline-continuation.
I assume this is what v86 does.
Generating entire modules works, but it has a number of issues.
For example, you need to carefully decide how big your modules are going to be:
- Too small, and you end up compiling many many modules, which eventually crashes the browser if you don't dispose of the old ones
- Too big (many functions batched together), and you have too much latency before your code is available to run
Being able to compile a single function to add to an existing module (or something like that) would help a lot.