 The Future of Compilers
started 12/8/2001; 2:44:04 AM - last post 12/15/2001; 6:59:07 AM
|
|
Noel Welsh - The Future of Compilers 
12/8/2001; 2:44:04 AM (reads: 2363, responses: 7)
|
|
| The Future of Compilers |
|
Proebsting's Law states that compiler technology doubles in power every 18 years, a direct analog to Moore's famous 18 month rule. This suggests increasing programmer productivity is a better research field though other contend that evidence does not support Proebsting's Law.
Regardless of the validity of Proebstring's Law it is interesting to ponder the future of compilers, since they affect all programming activities. Some say more effort should be spend optimising higher level code, to increase programmer productivity with out harming runtime performance. No doubt LtU readers are familiar with efforts in this area, exemplified by the ML and Haskell compilers. In fact higher level languages offer more opportunities for optimisation due to two properties. Firstly, they tend to have much cleaner semantics and are therefore easier to reason about within a compiler. Secondly, there isn't such a direct mapping to CPU operations as there is in portable assembly like C or C++ so there is more room for the compiler to try different options. I'll return to this point later.
It is interesting to look at novel ways of increasing program performance. The Dynamo project has created an on-line compiler that complements traditional off-line optimisations by concentrating on optimising the things that are hard to get right off-line: branch prediction and code placement. The results are impressive showing 20% speedups over code compiled at -O4, and even improving code compiled on the basis of profile information. In addition to the technical reports there is a nice overview at ArsTechnica and the usual grab-bag at Slashdot.
The Haskell compiler GHC takes a different approach based on two observations: Firstly, there are infinitely many optimisations Secondly, most optimisations are application specific. The conclusion is to let users specify the optimisations in the form of rewrite rules. (As a Scheme hacker I must point out that Lisp has had this since the beginning of time in the form of compiler macros.) This approach offers great potential for high-level optimisations though it remains to be seen how effective it is in practice.
The final point I'd like to raise gets back to the 'more-wriggle-room' argument above. It has been suggested that future compilers should incorporate AI techniques to search for the best optimisations for a given program. Traditional compilers don't adapt their optimisations to the program. Smarter compiler will, but the complexities in this approach are formidable. Heavily optimising compilers (e.g. Vortex and Stalin) already have long compile times. Imagine what could happen if you then allow the compiler to search through different representations. There are undoubtably some challenges to solve with this approach but there is room for great gains as well.
Posted to implementation by Noel Welsh on 12/8/01; 2:49:43 AM
|
|
|
|
Ehud Lamm - Re: The Future of Compilers
12/8/2001; 3:38:59 AM (reads: 1187, responses: 0)
|
|
|
Indeed the borderline between compilation and interpretation is getting more and more blurred, while the empahsis is on providing REPLs to enhance programmer productivity.
|
|
andrew cooke - Re: The Future of Compilers
12/8/2001; 10:22:51 AM (reads: 1182, responses: 2)
|
|
|
It would be nice if languages could be implemented with a variety of approaches. I was recently asking around for suggestions on real-time (ish) programming - I've plumped for Standard ML because there's three different compilers available - one (MLKit) with "nice" GC behaviour, and two with different degrees of support and optimisation (SML/NJ and MLTon) that might be good enough real-time, with better performance overall. I guess this is just saying that as the compiler becomes more complex, it will also need to offer more control (if you think of those three implementations as different compile-time options for a single language).
|
|
Ehud Lamm - Re: The Future of Compilers
12/9/2001; 12:09:44 PM (reads: 1216, responses: 1)
|
|
|
Languages are implemented in a variety of approaches. You have Scheme interpreters, native compilers, bytecode compilers, etc. etc.
Still, I am not sure it is appropriate to compare this with optimizatin levels. Seems to me the two are orthogonal.
|
|
andrew cooke - Re: The Future of Compilers
12/9/2001; 2:37:20 PM (reads: 1261, responses: 0)
|
|
|
Languages are implemented in a variety of approaches. You have Scheme interpreters, native compilers, bytecode compilers, etc. etc.
I gave examples for ML too. But why not have them as different aspects of one compiler? The original post was talking about selecting particular optimisations. Why not selectable memory management strategies? (or, better, selectable "high-level" targets for optimisation: real-time, small memory footprint, high-speed, etc etc)
Still, I am not sure it is appropriate to compare this with optimizatin levels. Seems to me the two are orthogonal.
Does "this" refer to compiled v interpreted implemntations? For many languages I thought this distinction was connected quite strongly with optimisation. Perhaps I'm using "interpretation" too loosely, but I'm thinking of the difference between using a "top-level loop" and doing some kind of whole-program analysis. Rather than being orthogonal, optimisation and "interactivity" seem to be strongly (negatively) correlated.
|
|
Noel Welsh - Re: The Future of Compilers
12/10/2001; 7:41:34 AM (reads: 1137, responses: 1)
|
|
|
Firstly apologies for taking up so much space on the front-page. I expected only the first paragraph to be displayed!
The line between programming language and (virtual) OS is being increasingly blurred and it is entirely reasonable to expect the compiler to operate offline and online.
Anyway, I agree with Andrew's point. As I get more into the 'compiler is just another program' viewpoint championed by SICP I find myself wanting more communication with the compiler. The Common Lisp Python compiler (CMUCL) offers hints when it encounters code that it can't optimise well. It would be nice to be able to talk back!
Perhaps this is another role for types (as Henry Baker suggests in a paper about linear types). Types are used to calculate data size - perhaps they should also represent data use. Ok, there is the start of this in Haskell and Clean - monads and linear types. It would be interesting to see how much further this could go.
|
|
Ehud Lamm - Re: The Future of Compilers
12/10/2001; 11:05:22 AM (reads: 1173, responses: 0)
|
|
|
Your original post was perfectly fine for the home page.
|
|
Frank Atanassow - Re: The Future of Compilers
12/15/2001; 6:59:07 AM (reads: 1087, responses: 0)
|
|
Types are used to calculate data size - perhaps they should also represent data use. Ok, there is the start of this in Haskell and Clean - monads and linear types.
Clean doesn't have linear types; it has unique types. They seem to be related, but the connection is not clear.
Haskell doesn't have linear types either. I hear that in GHC there is a linear usage analysis pass, but I think it has been shut down for a long time, pending further work.
In Haskell you can more or less define and use comonads, though, and (non-)linearity is modeled by a certain kind of comonad. (There is a paper on this by Richard Kieburtz. [1]) Haskell is already non-linear, though, so to get the sort of expressive power you have in intuitionistic linear logic, monads are what you want.
[1] Available here: http://www.cse.ogi.edu/~dick/dick.html
|
|
|
|