4 ms·

I think what the paper does is a variant of profile-guided optimisation (PGO) [1], an old approach to optimising compilers, where the binary is annotated and r

by mafribe 11y ago

I think what the paper does is a variant of profile-guided optimisation (PGO) [1], an old approach to optimising compilers, where the binary is annotated and run to produce information about runs that is then feed back to the compiler so as to allow better optimisation the next time the compiler is run. The most well-know off-shoot of PGO are tracing JIT compilers. The first (well-known) tracing JIT compiler was Dynamo [2], and indeed, the system under discussion here uses DynamoRIO [3], a descendant of Dynamo to instrument a compiled binary. The instrumented binary is then executed multiple times to generate execution traces that allow the optimiser to find hot code, which is then analyses to adapt the code to the new architecture, e.g. change buffer sizes. [1] https://en.wikipedia.org/wiki/Profile-guided_optimization https://en.wikipedia.org/wiki/Profile-guided_optimization [2] http://www.cs.virginia.edu/kim/courses/cs771/papers/bala00dynamo.pdf http://www.cs.virginia.edu/kim/courses/cs771/papers/bala00dy... [3] http://www.dynamorio.org/ http://www.dynamorio.org/

aaronkrolik 11y ago
Interesting. So what would you say is novel/noteworthy about this research?
- mafribe 11y ago
  I have not had time to study this paper in detail, so please take what I say here with a grain of salt. Dynamic instrumentation is powerful, I think Google is using DynamoRIO heavily. Optimising compilers for DSLs is a trendy topic because 1. We are beginning to understand well how canonically to embed DSLs in general purpose languages, and have to build compilers for languages. 2. DSLs typically work on much more restricted domains than general purpose languages, so optimisation is much easier, and more powerful. The Pochoir compiler for stencil computations is an example of this. There are many open questions about compilation of DSLs other than optimisation, for example automatic generation of operational and axiomatic semantics of DSLs, and associated tooling. Really interesting research field. [1] https://people.csail.mit.edu/yuantang/ https://people.csail.mit.edu/yuantang/
- vmarsy 11y ago
  In typical PGO you have access to the source code, the compiler instruments it for you automatically, you run the program with what You consider good input. During that time the instrumentation records a lot of interesting stuff. Then the compiler recompiles your program with that extra knowledge, making much better decisions[1]. For instance the compiler might realize: "Oh, this function is called much more often than I thought, I will now inline it." Here (Link to the paper:[2]) this is different: The authors do NOT have access to the source code, they only have stripped binaries. From these unreadable binary instructions, they are able to identify interesting patterns: they extract the algorithm from the assembly. For this to work, they seem to need run time information. This means, as in conventional PGO, they need to have a wide variety of valuable input. It apparently cannot be done at compile time: "Current state-of-the-art techniques are not capable of extracting the simple algorithms from these highly optimized program." Once the algorithm is figured out, the Helium framework is generating domain specific code in "Halide". Halide compilers knows how to optimize these stencil computation better than old hand written code, which give them these impressive improvements. [1]https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx [2] http://groups.csail.mit.edu/commit/papers/2015/mendis-pldi15-helium.pdf http://groups.csail.mit.edu/commit/papers/2015/mendis-pldi15...
  - marktangotango 11y ago
    Also seems like 'highly optimized' is another way of saying 'obfuscated' in this case.
burstsintop 11y ago
They made a second version that had much worse results, actively broke code. This is being sold by the offshore vendors at much cheapness to do the needful!

by mafribe 11y ago

aaronkrolik 11y ago

Interesting. So what would you say is novel/noteworthy about this research?

mafribe 11y ago
I have not had time to study this paper in detail, so please take what I say here with a grain of salt. Dynamic instrumentation is powerful, I think Google is using DynamoRIO heavily. Optimising compilers for DSLs is a trendy topic because 1. We are beginning to understand well how canonically to embed DSLs in general purpose languages, and have to build compilers for languages. 2. DSLs typically work on much more restricted domains than general purpose languages, so optimisation is much easier, and more powerful. The Pochoir compiler for stencil computations is an example of this. There are many open questions about compilation of DSLs other than optimisation, for example automatic generation of operational and axiomatic semantics of DSLs, and associated tooling. Really interesting research field. [1] https://people.csail.mit.edu/yuantang/ https://people.csail.mit.edu/yuantang/
vmarsy 11y ago
In typical PGO you have access to the source code, the compiler instruments it for you automatically, you run the program with what You consider good input. During that time the instrumentation records a lot of interesting stuff. Then the compiler recompiles your program with that extra knowledge, making much better decisions[1]. For instance the compiler might realize: "Oh, this function is called much more often than I thought, I will now inline it." Here (Link to the paper:[2]) this is different: The authors do NOT have access to the source code, they only have stripped binaries. From these unreadable binary instructions, they are able to identify interesting patterns: they extract the algorithm from the assembly. For this to work, they seem to need run time information. This means, as in conventional PGO, they need to have a wide variety of valuable input. It apparently cannot be done at compile time: "Current state-of-the-art techniques are not capable of extracting the simple algorithms from these highly optimized program." Once the algorithm is figured out, the Helium framework is generating domain specific code in "Halide". Halide compilers knows how to optimize these stencil computation better than old hand written code, which give them these impressive improvements. [1]https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx https://msdn.microsoft.com/en-us/library/e7k32f4k.aspx [2] http://groups.csail.mit.edu/commit/papers/2015/mendis-pldi15-helium.pdf http://groups.csail.mit.edu/commit/papers/2015/mendis-pldi15...
- marktangotango 11y ago
  Also seems like 'highly optimized' is another way of saying 'obfuscated' in this case.

burstsintop 11y ago

They made a second version that had much worse results, actively broke code. This is being sold by the offshore vendors at much cheapness to do the needful!