12 ms·

The Future of Compiler Optimization

80 points by dochtman 16y ago

sb 16y ago
Excellent post. Aside from the very interesting and important (hence many PLDI publications) work of Sorin Lerner, there is a workshop which deals with the first point of Prof. Regehr: Compiler Optimization meets Compiler Verification, which is a satellite workshop for ETAPS. So for interested people, this might very well be the point to start digging for relevant publications.
ced 16y ago
What is the most advanced compiler, across all high-level (not C/C++) languages? The GHC?
- ori_b 16y ago
  From what I've heard, probably MLton.
  - ced 16y ago
    Can you explain why? Neither their webpage nor Wikipedia goes much beyond "produces fast executables".
    - jules 16y ago
      I found this description of the passes and intermediate languages used in mlton: http://mlton.org/CompilerOverview http://mlton.org/CompilerOverview Another candidate for the most advanced compiler is Stalin.
- beza1e1 16y ago
  What do you mean by "most advanced"? * LLVM is probably the Open-Source compiler which fits your intention most. * GCC has man-years of efforts for little bit/byte tweaks, which no other compiler does. This is not advanced, but tedious. * libFirm is the only compiler which does not deconstruct SSA form. This is advanced in a mostly academic sense. * GHC is probably the best functional (CPS) compiler. * Sun JVM is probably the best Hotspot (online) compiler. * I'm not sure which compiler is "most advanced" for dynamically typed code. Some Smalltalk or Javascript compiler? PyPy?
  - jules 16y ago
    The most advanced dynamically typed code compiler is either Self or Stalin.
    - borisk 16y ago
      Intresting - http://en.wikipedia.org/wiki/Stalin_(Scheme_implementation) http://en.wikipedia.org/wiki/Stalin_(Scheme_implementation) When do we expect Hitler, Churchill and Roosevelt?
      - jules 16y ago
        "Stalin brutally optimizes."
  - ced 16y ago
    The question was intentionally vague. I'm looking for interesting threads of thought. Thanks for your post. libFirm is the only compiler which does not deconstruct SSA form I thought that continuation-passing-style compilers didn't use SSA, and that most Scheme implementations were CPS. No?
    - beza1e1 16y ago
      SSA and CPS is equivalent: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.6773 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.67... In SSA form most operations (add,sub,...) are side-effect free and the rest (load,store,call,...) can be understood as using something like a "Memory Monad".
  - sb 16y ago
    I think at least worth mentioning in this list is the milepost project: * http://ctuning.org/wiki/index.php/CTools:MilepostGCC http://ctuning.org/wiki/index.php/CTools:MilepostGCC Smalltalk JITs are pretty darn good, e.g., the Strongtalk project is known to be pretty fast. As of 2006, Sun released the Strongtalk source code. Its publication record is relatively weak (aside of type system related publications), but it contains a wealth of relevant optimizations and I am sure the interested reader/programmer will find something valuable in there. (http://www.strongtalk.org http://www.strongtalk.org) Eliot Miranda has been implementing Smalltalk VMs for quite a while, and I think his recent addition ("Cog") to the Squeak implementation is probably the most recent addition to JIT compilers for Smalltalk VMs. Given his in-depth experience and expertise (particularly with inline caching), this could probably serve as a blueprint for other (Smalltalk) JITs. V8 for Javascript is supposedly very fast (interesting side information: Robert Griesemer is working on V8, but worked on the Strongtalk interpreter before), but I don't know about the involved benchmarks, and how they stack up against each other--particularly since the TraceMonkey trace-based JITs came along. Mike Pall's LuaJIT is a very interesting project (only one-man JIT project I know of), too. PS: I am sorry for the overly long post...
CountHackulus 16y ago
Surprisingly, compilers already do much of these optimization, particularly profile directed feedback (basically a static JIT), and the mixing of high-level and low-level optimizations. Now while, LLVM may not do this, it's far from the only compiler on the block; especially in the non-open-source world. The IR argument is a non-argument. Certain optimizations work better with certain IRs than others, that's just the way it is. It's unlikely that there will be one to rule them all. More likely, we'll convert between them to use the optimal one. Superoptimizers are an interesting case, it's kind of like having a database of optimality. While it may not give much speedup compared to time invested, if you're desperate for that last little bit of performance, it's a great tool. Plus it should make itself faster over time. Could even locate it in the cloud, such that a compiler send its hottest methods over to a remote machine, and it'll use its massive database of optimality to optimize it as best as possible. Verifiable transformations are great in theory, but it's true, it's extremely hard to implement currently. The author definitely has a point about AOT/JIT compilers being the future of optimization. Static compilers have been done to death, while dynamic compilers are still (comparatively) new and fresh.
- ced 16y ago
  Now while, LLVM may not do this, it's far from the only compiler on the block; especially in the non-open-source world. Non-open-source compilers don't get much press around here. Could you point out the most interesting ones?
  - larsberg 16y ago
    Visual C++ has had things like profile-guided optimization for over a decade internally to MSFT and nearly that long shipping externally (http://blogs.msdn.com/b/vcblog/archive/2008/11/12/pogo.aspx http://blogs.msdn.com/b/vcblog/archive/2008/11/12/pogo.aspx). In general, the Microsoft and Intel C++ compilers have pretty incredible performance on the x86 platform. The last time I talked to the Intel folks, they didn't really consider GCC to be competitive. It's possible things have changed in the last five years on that front; apologies if I'm misrepresenting the state of GCC optimization quality. The PGI Fortran folks are pretty incredible in the parallel space. On embedded platforms, most serious companies seem to buy the Green Hills C++ compiler. One of the program-management types from the Visual C++ team could probably do this much better justice than my quickly-fading memories. But, I think the HN crowd would be quite shocked by the market share that commercial compilers have, even on *NIX platforms.
beza1e1 16y ago
I think he emphasizes the joining of verification and optimization too much. No doubt verification may get easier, if they use the IR and all analysis info the compiler already did. SSA makes this stuff easier for example. Just tell me what optimization could learn from verification? Everything verification does is too slow to do within a compiler. Sure, you can produce better code, if you are allowed to use NP algorithms, but in reality i have never seen any algorithm more complex than O(n^2) in a compiler. Usually O(nlogn) is the most one can afford.
- JoachimSchipper 16y ago
  A deeper understanding of the program - which is what verification brings to the table - may be useful; even if it is too slow for most code, it can occasionally be used to detect bugs/speed up the most critical parts. It would also be rather useful, although probably quite a bit of work, to have a "verify the optimizations you did" mode. While most errors aren't compiler errors, gcc has been known to optimize bugs into programs...
- namin 16y ago
  Arguably, types are a form of verification, and they already lead to better optimizations.
  - beza1e1 16y ago
    Types were invented for optimization and used for verification later, weren't they?

80 points by dochtman 16y ago

sb 16y ago

Excellent post. Aside from the very interesting and important (hence many PLDI publications) work of Sorin Lerner, there is a workshop which deals with the first point of Prof. Regehr: Compiler Optimization meets Compiler Verification, which is a satellite workshop for ETAPS. So for interested people, this might very well be the point to start digging for relevant publications.

ced 16y ago

What is the most advanced compiler, across all high-level (not C/C++) languages? The GHC?

ori_b 16y ago
From what I've heard, probably MLton.
- ced 16y ago
  Can you explain why? Neither their webpage nor Wikipedia goes much beyond "produces fast executables".
  - jules 16y ago
    I found this description of the passes and intermediate languages used in mlton: http://mlton.org/CompilerOverview http://mlton.org/CompilerOverview Another candidate for the most advanced compiler is Stalin.
beza1e1 16y ago
What do you mean by "most advanced"? * LLVM is probably the Open-Source compiler which fits your intention most. * GCC has man-years of efforts for little bit/byte tweaks, which no other compiler does. This is not advanced, but tedious. * libFirm is the only compiler which does not deconstruct SSA form. This is advanced in a mostly academic sense. * GHC is probably the best functional (CPS) compiler. * Sun JVM is probably the best Hotspot (online) compiler. * I'm not sure which compiler is "most advanced" for dynamically typed code. Some Smalltalk or Javascript compiler? PyPy?
- jules 16y ago
  The most advanced dynamically typed code compiler is either Self or Stalin.
  - borisk 16y ago
    Intresting - http://en.wikipedia.org/wiki/Stalin_(Scheme_implementation) http://en.wikipedia.org/wiki/Stalin_(Scheme_implementation) When do we expect Hitler, Churchill and Roosevelt?
    - jules 16y ago
      "Stalin brutally optimizes."
- ced 16y ago
  The question was intentionally vague. I'm looking for interesting threads of thought. Thanks for your post. libFirm is the only compiler which does not deconstruct SSA form I thought that continuation-passing-style compilers didn't use SSA, and that most Scheme implementations were CPS. No?
  - beza1e1 16y ago
    SSA and CPS is equivalent: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.6773 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.67... In SSA form most operations (add,sub,...) are side-effect free and the rest (load,store,call,...) can be understood as using something like a "Memory Monad".
- sb 16y ago
  I think at least worth mentioning in this list is the milepost project: * http://ctuning.org/wiki/index.php/CTools:MilepostGCC http://ctuning.org/wiki/index.php/CTools:MilepostGCC Smalltalk JITs are pretty darn good, e.g., the Strongtalk project is known to be pretty fast. As of 2006, Sun released the Strongtalk source code. Its publication record is relatively weak (aside of type system related publications), but it contains a wealth of relevant optimizations and I am sure the interested reader/programmer will find something valuable in there. (http://www.strongtalk.org http://www.strongtalk.org) Eliot Miranda has been implementing Smalltalk VMs for quite a while, and I think his recent addition ("Cog") to the Squeak implementation is probably the most recent addition to JIT compilers for Smalltalk VMs. Given his in-depth experience and expertise (particularly with inline caching), this could probably serve as a blueprint for other (Smalltalk) JITs. V8 for Javascript is supposedly very fast (interesting side information: Robert Griesemer is working on V8, but worked on the Strongtalk interpreter before), but I don't know about the involved benchmarks, and how they stack up against each other--particularly since the TraceMonkey trace-based JITs came along. Mike Pall's LuaJIT is a very interesting project (only one-man JIT project I know of), too. PS: I am sorry for the overly long post...

CountHackulus 16y ago

Surprisingly, compilers already do much of these optimization, particularly profile directed feedback (basically a static JIT), and the mixing of high-level and low-level optimizations. Now while, LLVM may not do this, it's far from the only compiler on the block; especially in the non-open-source world. The IR argument is a non-argument. Certain optimizations work better with certain IRs than others, that's just the way it is. It's unlikely that there will be one to rule them all. More likely, we'll convert between them to use the optimal one. Superoptimizers are an interesting case, it's kind of like having a database of optimality. While it may not give much speedup compared to time invested, if you're desperate for that last little bit of performance, it's a great tool. Plus it should make itself faster over time. Could even locate it in the cloud, such that a compiler send its hottest methods over to a remote machine, and it'll use its massive database of optimality to optimize it as best as possible. Verifiable transformations are great in theory, but it's true, it's extremely hard to implement currently. The author definitely has a point about AOT/JIT compilers being the future of optimization. Static compilers have been done to death, while dynamic compilers are still (comparatively) new and fresh.

ced 16y ago
Now while, LLVM may not do this, it's far from the only compiler on the block; especially in the non-open-source world. Non-open-source compilers don't get much press around here. Could you point out the most interesting ones?
- larsberg 16y ago
  Visual C++ has had things like profile-guided optimization for over a decade internally to MSFT and nearly that long shipping externally (http://blogs.msdn.com/b/vcblog/archive/2008/11/12/pogo.aspx http://blogs.msdn.com/b/vcblog/archive/2008/11/12/pogo.aspx). In general, the Microsoft and Intel C++ compilers have pretty incredible performance on the x86 platform. The last time I talked to the Intel folks, they didn't really consider GCC to be competitive. It's possible things have changed in the last five years on that front; apologies if I'm misrepresenting the state of GCC optimization quality. The PGI Fortran folks are pretty incredible in the parallel space. On embedded platforms, most serious companies seem to buy the Green Hills C++ compiler. One of the program-management types from the Visual C++ team could probably do this much better justice than my quickly-fading memories. But, I think the HN crowd would be quite shocked by the market share that commercial compilers have, even on *NIX platforms.

beza1e1 16y ago

I think he emphasizes the joining of verification and optimization too much. No doubt verification may get easier, if they use the IR and all analysis info the compiler already did. SSA makes this stuff easier for example. Just tell me what optimization could learn from verification? Everything verification does is too slow to do within a compiler. Sure, you can produce better code, if you are allowed to use NP algorithms, but in reality i have never seen any algorithm more complex than O(n^2) in a compiler. Usually O(nlogn) is the most one can afford.

JoachimSchipper 16y ago
A deeper understanding of the program - which is what verification brings to the table - may be useful; even if it is too slow for most code, it can occasionally be used to detect bugs/speed up the most critical parts. It would also be rather useful, although probably quite a bit of work, to have a "verify the optimizations you did" mode. While most errors aren't compiler errors, gcc has been known to optimize bugs into programs...
namin 16y ago
Arguably, types are a form of verification, and they already lead to better optimizations.
- beza1e1 16y ago
  Types were invented for optimization and used for verification later, weren't they?