5 ms·
A supercompiler pass for Erlang
- DonbunEf7 9y ago"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.
- toolslive 9y agoWhen first read about partial evaluation, I misread Futamura as "Futurama". Maybe my brain was trying to tell me something...
- moomin 9y agoI think it's trying to tell you you really like Futurama.
- bobwaycott 9y agoSame here. Started wondering what episode was being discussed.
- db48x 9y agoObviously 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.
- devmunchies 9y agoYes, and then I found this wiki page about the topic and I still am confused: https://en.wikipedia.org/wiki/Partial_evaluation https://en.wikipedia.org/wiki/Partial_evaluation Can anybody explain like I'm 5?
- gghh 9y agoDan Piponi has a nice introduction to Futamura's projections in his blog: http://blog.sigfpe.com/2009/05/three-projections-of-doctor-futamura.html http://blog.sigfpe.com/2009/05/three-projections-of-doctor-f...
- abecedarius 9y agoHere'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/ http://wry.me/~darius/writings/peval/
- toolslive 9y agoNot 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 http://www.itu.dk/~sestoft/pebook/pebook.html
- chrisseaton 9y agoDid you know that there is a new Java compiler that can do the first Futamura projection? https://github.com/graalvm/graal/tree/master/compiler https://github.com/graalvm/graal/tree/master/compiler
- DonbunEf7 9y agoGraal 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.
- alberth 9y agoIsn'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-want-java-ee-any-more.html http://www.infoworld.com/article/3217347/java/oracle-doesnt-...
- aseipp 9y agoEven 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.
- efferifick 9y agoThe Futamura projections are such a cool result of partial evaluation! Thanks for pointing it out, otherwise I would not have known about them.
- makapuf 9y agoFor those wondering what a supercompiler is, here is a simple introduction to it on c2 : http://wiki.c2.com/?SuperCompiler 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.
- Sean1708 9y agoHow does a supercompiler differ to the optimisations that occur in a JIT compiler?
- chrisseaton 9y agoTo 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.
- chriswarbo 9y agoNote 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.
- OoooooooO 9y agoIsn'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.
- chrisseaton 9y ago
- fenollp 9y agoAuthor 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 https://github.com/weinholt [2] https://github.com/erlang/otp/pull/1080#issuecomment-314598581 https://github.com/erlang/otp/pull/1080#issuecomment-3145985... [3] https://medium.com/@jlouis666/an-erlang-otp-20-0-optimization-efde8b20cba7 https://medium.com/@jlouis666/an-erlang-otp-20-0-optimizatio...
- cpeterso 9y agoCan you share any more information about the types of code patterns that can be superoptimized or how much speedup you see on benchmarks?
- fenollp 9y agoSo 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 https://github.com/fenollp/erlscp/tree/master/test/asm_data [2] https://github.com/fenollp/erlscp/blob/master/src/erlang_supercompiler.erl#L29 https://github.com/fenollp/erlscp/blob/master/src/erlang_sup... [3] https://github.com/fenollp/erlscp/blob/master/test/asm_data/unfold3.hrl https://github.com/fenollp/erlscp/blob/master/test/asm_data/... [4] https://github.com/2600hz/kazoo https://github.com/2600hz/kazoo