A supercompiler pass for Erlang | Hacker News Reader

A supercompiler pass for Erlang

github.com

152 pointsbryanrasmussen29 comments

Author of the repo here.

Just wanted to say that 99% of this is thanks to [1] and his 2013 Masters thesis.

There has been slight discussion to integrate a supercompiling pass (more involved than the ones that are in the compiler already) over at [2].

Hope to motivate enough people to see this happen, especially since we now have even cheaper constant literals [3]! Let's get on this.

[1] https://github.com/weinholt

[2] https://github.com/erlang/otp/pull/1080#issuecomment-3145985...

[3] https://medium.com/@jlouis666/an-erlang-otp-20-0-optimizatio...

Can you share any more information about the types of code patterns that can be superoptimized or how much speedup you see on benchmarks?

So if you look into [1] you'll find .hrl sources (actually .erl) and their .S counterpart in the subfolders. From these you will see that functions `a` and `b` look more and more like each other. Note that `b` is the literal version of `a`.

How much speedup? Potentially infinite, at the price of compile time. In real world cases though I don't have any data yet. I want to be able to compile a whole project first and that fails for one last reason, described in the README. But I have faith :)

The patterns that can be superoptimized are few for now. [2] describes how some of lists.erl functions work so that they can be supercompiled. The long-term idea is to have a local(/global if secured) cache of code so that inter-module calls can be optimized if the developer wants.

My real world case/motivation is supercompilation of code such as [3] (goal is to turn `a` into `b` at the assembly level). This pattern is extremely common in my employer's software [4] (which is probably the biggest open source Erlang project AFAIK).

A short example of a being super compiled into b:

    a() -> hd([get()]).
    b() -> get().

[1] https://github.com/fenollp/erlscp/tree/master/test/asm_data

[2] https://github.com/fenollp/erlscp/blob/master/src/erlang_sup...

[3] https://github.com/fenollp/erlscp/blob/master/test/asm_data/...

[4] https://github.com/2600hz/kazoo

From what I understand (on phone so no refs right now), "super compilation" is limited to a linear speedup. However, "distillation" can achieve super-linear speedup.

I used to know and talk to this guy ^

For those wondering what a supercompiler is, here is a simple introduction to it on c2 : http://wiki.c2.com/?SuperCompiler.

To quote it :

A SuperCompiler is a dynamic optimizer that can transform the code of an object according to its actual usage.

This may be simple static optimizations, removing state that isn't used from an object; or it may be very complex e.g. partial evaluation of functions leading to code transformation.

How does a supercompiler differ to the optimisations that occur in a JIT compiler?

To be honest I think even the most sophisticated use of super-compilation - the partial evaluation described above - is really just a fancy way of saying inlining, constant folding and expression simplification.

Note that "inlining, constant folding and expression simplification" covers everything in functional programming :)

Erlang isn't purely functional, since it has things like message sends. This project doesn't seem to handle such things properly :(

> Something will happen if the supercompiled module contains side-effects such as message passing, and it will probably not be something good.

Isn't the point of Erlang to use it's message system in most cases?

If the supercompiler can't handle message passing then it can't handle ~98% of all Erlang code.

Lots of optimisations don't apply in the presence of side-effects but are still useful.

It's on a spectrum with it. JITs don't actually do much "optimization", because they need to be fast. It's subjective, but I'd say supercompiling is nearer to profile-guided whole-program optimization.

Huh.

It would be kind of cool to hook a profiling execution tracer into a JIT to find hot paths, resolve that to the nearest "usefully supercompilable" code block (it sounds like supercompilation works best when fed whole programs, I'm not sure how much bigger-picture comprehension [large-scale] JITs have of program scope in practice) and then supercompile that in a CPU-throttled background thread.

Thinking in the context of LLVM et al.

I'm aware that JS engines do a "fast" compile designed to just generate code now within a few ms, and a fractionally slower compile that does do some optimizations and returns executable results within a few hundred ms.

This could be a third optimization stage that takes 1 second, or maybe even 2 or 3, but produces really really good results. If this doesn't already exist - I don't know, so I can't really assume either way - it almost sounds like low hanging fruit, and a super fun project too.

Completely agree! There is plenty of unexplored space and tradeoffs across the spectrum :)

SuperCompiler, superoptimizer, ...

Naming things are really hard

"Not that the Futamura projections can be used with erlscp yet, but, you know, just in case that day ever comes. A man can dream."

I feel like this is the lament of every compiler author.

When first read about partial evaluation, I misread Futamura as "Futurama". Maybe my brain was trying to tell me something...

I think it's trying to tell you you really like Futurama.

Same here. Started wondering what episode was being discussed.

Obviously the first Tales of Interest episode, where the Professor uses the What-If machine to find out what would have happened if he had invented the Finglonger.

Yes, and then I found this wiki page about the topic and I still am confused: https://en.wikipedia.org/wiki/Partial_evaluation

Can anybody explain like I'm 5?

Dan Piponi has a nice introduction to Futamura's projections in his blog: http://blog.sigfpe.com/2009/05/three-projections-of-doctor-f...

Here's the simplest code I could come up with for 'dynamic' partial evaluation, showing interpreter->compiler but not the higher projections: http://wry.me/~darius/writings/peval/

Not like you're five, but if you're interested: the standard introduction is still 'Partial Evaluation and Program generation', which is freely available http://www.itu.dk/~sestoft/pebook/pebook.html

Did you know that there is a new Java compiler that can do the first Futamura projection? https://github.com/graalvm/graal/tree/master/compiler

Graal and Truffle are cool. It's unfortunate that it's in Java, mostly because I don't trust Oracle to do the right thing with the community and I expect them to change licenses to make business opportunities for Substrate VM licensing.

Isn't Oracle giving leadership of Java over to the open source community (i.e. to Apache or Elcipse )

As such, what's concerns still exist?

http://www.infoworld.com/article/3217347/java/oracle-doesnt-...

Even without SubstrateVM, Graal is a big step forward IMO in terms of interop and performance for the JVM. And Graal/Truffle are under the GPLv3, and only need JDK9 JVMCI interfaces, so I think it's mostly in the clear at this point... They can change the license, but they can't take away the code that's already open.

That said: I agree it seems extremely likely at this point that Oracle is going to milk Substrate for enterprise money, and that's a shame because it is a really important component of the system, in my opinion. And not having it will be a big drag for people who are considering Truffle/Graal.

The Futamura projections are such a cool result of partial evaluation! Thanks for pointing it out, otherwise I would not have known about them.

Reply on news.ycombinator.com