News for hackers. Stuff that matters.
Re:PartialExecuter: Reducing WebAssembly size by exploring a... by rowanG077 on Tuesday March 15, 2022 @12:14PM (#30687143)
Have you guys looked the literature of supercompilation? This seems to be a special case of it.
Re:PartialExecuter: Reducing WebAssembly size by exploring a... by fulafel on Tuesday March 15, 2022 @01:16PM (#30688025)
All analytical solutions to optimization problems can be seen as special cases of the brute force search I guess. But SC is impractically slow for anything except a few instructions long sequences.

edit: actually I was thinking of superoptimizers, I guess it's a different concept.

Re:PartialExecuter: Reducing WebAssembly size by exploring a... by titzer on Tuesday March 15, 2022 @05:34PM (#30692078)
Superoptimizers have gotten a lot better in the past few years. E.g. have a look at [1].

[1] https://arxiv.org/abs/1211.0557

Re:PartialExecuter: Reducing WebAssembly size by exploring a... by fulafel on Wednesday March 16, 2022 @03:13AM (#30696114)
Thanks, cool stuff.

This paper from the same project was also cool: https://raw.githubusercontent.com/StanfordPL/stoke/develop/d...

Quote from abstract: " For many applications, the best possible code is conditionally correct: the optimized kernel is equal to the code that it replaces only under certain preconditions on the kernel’s inputs. The main technical challenge in producing conditionally correct opti- mizations is in obtaining non-trivial and useful conditions and proving conditional equivalence formally in the pres- ence of loops. We combine abstract interpretation, decision procedures, and testing to yield a verification strategy that can address both of these problems. This approach yields a superoptimizer for x86 that in our experiments produces binaries that are often multiple times faster than those pro- duced by production compilers"

Re:PartialExecuter: Reducing WebAssembly size by exploring a... by rowanG077 on Tuesday March 15, 2022 @01:23PM (#30688129)
Supercompilation is not brute force search.
Re:PartialExecuter: Reducing WebAssembly size by exploring a... by carlopi on Tuesday March 15, 2022 @12:52PM (#30687656)
Hi, author of the post here, I am not familiar with this concept, do you have any pointers?
Re:PartialExecuter: Reducing WebAssembly size by exploring a... by rowanG077 on Tuesday March 15, 2022 @01:16PM (#30688023)
The idea is to evaluate the program at compile time and obtain a trace of the program that allows you to reconstruct a semantically equivalent program which has some desirable properties. In your case (and most cases in literature) it's done for optimization. Partial evaluation, which is a subset of supercompilation, is similar to what you are doing. See the wiki page: https://en.wikipedia.org/wiki/Partial_evaluation

Some literature:

https://dl.acm.org/doi/10.1145/5956.5957

https://ndmitchell.com/downloads/paper-rethinking_supercompi...

Re:PartialExecuter: Reducing WebAssembly size by exploring a... by moralestapia on Tuesday March 15, 2022 @01:01PM (#30687795)
Supercompilation came to my mind as well!

Wasm + SC would be a killer deal.