4 ms·

I think its worthless to find the "optimal" sequence of instructions these days. The performance of a computer system depends far more on the runtime context th

I think its worthless to find the "optimal" sequence of instructions these days. The performance of a computer system depends far more on the runtime context then on anything a compiler can infer from compile-time information. I worked on production compilers at a major chip company, and the best thing we can do is improve the context in which a compiler is deployed. Runtime systems and compilers have to cooperate better. The compiler needs to have an interface that is cheap (low overhead) for the runtime to call into and make changes to programs. The runtime needs to sample more architectural perf counters that matter and send them into the compiler so that it can make smarter decisions.

maaku 12y ago
For some problems. Not for others.
clord 12y ago
Also worked on compilers at a major chip company. Generally it's better to have clear code than fast code. For that reason I would say that the future of optimization are things like whole-program optimization that exploits language features to improve the asymptotic costs of mechanically provable algorithms. For a primitive example, consider taking a simple Haskell program that is provably correct but needs O(n^3). Put it through some 'equivalent optimal implementation' system that provably spits out an algorithm that does the same task in O(n lg n). We did stuff like this for simple matrices in Fortran and C, but I think it is generalizable to more problems than that. And of course, I agree that most of the time no one really cares except HPC.
- meowface 12y ago
  The problem is that the subset of programs which can be proved to be correct (in 2015) is mostly restricted either to uninteresting problems, solved problems, or both.
  - TheLoneWolfling 12y ago
    Don't think of it at the program level. Think of it at a smaller level. Even optimizing, say, a single "trivial" function in a widely used library can have large effects overall.
  - clord 12y ago
    Not always true. For a trivial example, in fortran code, we'd often see people wanting to write code that calls runtime methods directly because it leads to clearer implementations. The language rules were such that we could prove invariants on these runtime calls that were much stronger and farther reaching than the general bitcode optimizer could do, resulting in a class of matrix operations going to n*lg(n) from n^3, and we could also switch the stride direction to make better use of cache because of the algorithm change. This sort of thing was only possible because language knowledge was exploited — generic optimizers will miss this stuff. I think the future of languages like haskell are bright in terms of performance, because they are so loosey goosey with what gets evaluated when, which gives language-aware optimizers a lot of meat to chew. An aggressive optimizer could turn out versions of the same code that run screaming-fast single-threaded, or that fully exploit massive parallel machines, or even version for all of those.
- TorKlingberg 12y ago
  If only we could do whole-program optimization without recompiling everything after the tiniest change.
vardump 12y ago
I also think runtime information is critical. Integrated specialized JITs and hinted binary translation might be the solution. Especially considering the pace new instructions have been added lately. Maybe superoptimization databases for some common sequences.
- LnxPrgr3 12y ago
  You might find this interesting reading: Automatic Generation of Peephole Superoptimizers: http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf http://theory.stanford.edu/~aiken/publications/papers/asplos... Binary Translation Using Peephole Superoptimizers: https://www.usenix.org/legacy/event/osdi08/tech/full_papers/bansal/bansal.pdf https://www.usenix.org/legacy/event/osdi08/tech/full_papers/... The first one was referenced in the post, but that feature wasn't mentioned.
phkahler 12y ago
>> I think its worthless to find the "optimal" sequence of instructions these days. That's funny, the difference between Intel and AMD processors performance is on the same order as what an optimizer can do. People are very disappointed in AMD these days because of it. Low level optimization always has and always will be important and people will pay really money for that difference in performance. Getting the right algorithm and having good cache behavior are still important too of course, but too many CS folks keep thinking that's all that matters.

maaku 12y ago

For some problems. Not for others.

clord 12y ago

Also worked on compilers at a major chip company. Generally it's better to have clear code than fast code. For that reason I would say that the future of optimization are things like whole-program optimization that exploits language features to improve the asymptotic costs of mechanically provable algorithms. For a primitive example, consider taking a simple Haskell program that is provably correct but needs O(n^3). Put it through some 'equivalent optimal implementation' system that provably spits out an algorithm that does the same task in O(n lg n). We did stuff like this for simple matrices in Fortran and C, but I think it is generalizable to more problems than that. And of course, I agree that most of the time no one really cares except HPC.

meowface 12y ago
The problem is that the subset of programs which can be proved to be correct (in 2015) is mostly restricted either to uninteresting problems, solved problems, or both.
- TheLoneWolfling 12y ago
  Don't think of it at the program level. Think of it at a smaller level. Even optimizing, say, a single "trivial" function in a widely used library can have large effects overall.
- clord 12y ago
  Not always true. For a trivial example, in fortran code, we'd often see people wanting to write code that calls runtime methods directly because it leads to clearer implementations. The language rules were such that we could prove invariants on these runtime calls that were much stronger and farther reaching than the general bitcode optimizer could do, resulting in a class of matrix operations going to n*lg(n) from n^3, and we could also switch the stride direction to make better use of cache because of the algorithm change. This sort of thing was only possible because language knowledge was exploited — generic optimizers will miss this stuff. I think the future of languages like haskell are bright in terms of performance, because they are so loosey goosey with what gets evaluated when, which gives language-aware optimizers a lot of meat to chew. An aggressive optimizer could turn out versions of the same code that run screaming-fast single-threaded, or that fully exploit massive parallel machines, or even version for all of those.
TorKlingberg 12y ago
If only we could do whole-program optimization without recompiling everything after the tiniest change.

vardump 12y ago

I also think runtime information is critical. Integrated specialized JITs and hinted binary translation might be the solution. Especially considering the pace new instructions have been added lately. Maybe superoptimization databases for some common sequences.

LnxPrgr3 12y ago
You might find this interesting reading: Automatic Generation of Peephole Superoptimizers: http://theory.stanford.edu/~aiken/publications/papers/asplos06.pdf http://theory.stanford.edu/~aiken/publications/papers/asplos... Binary Translation Using Peephole Superoptimizers: https://www.usenix.org/legacy/event/osdi08/tech/full_papers/bansal/bansal.pdf https://www.usenix.org/legacy/event/osdi08/tech/full_papers/... The first one was referenced in the post, but that feature wasn't mentioned.

phkahler 12y ago

>> I think its worthless to find the "optimal" sequence of instructions these days. That's funny, the difference between Intel and AMD processors performance is on the same order as what an optimizer can do. People are very disappointed in AMD these days because of it. Low level optimization always has and always will be important and people will pay really money for that difference in performance. Getting the right algorithm and having good cache behavior are still important too of course, but too many CS folks keep thinking that's all that matters.