5 ms·
On the topic of compiler optimization, Peter Seibel's interview with Fran Allen, a Turing Award recipient for her "pioneering contributions to the theory and pr
by danso 12y ago
On the topic of compiler optimization, Peter Seibel's interview with Fran Allen, a Turing Award recipient for her "pioneering contributions to the theory and practice of optimizing compiler techniques", is a good read:
http://books.google.com/books?id=nneBa6-mWfgC&lpg=PA9&pg=PA501#v=onepage&q&f=false http://books.google.com/books?id=nneBa6-mWfgC&lpg=PA9&pg=PA5...
She considers the development of C to be a "big blow", saying that "C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers...are basically not taught much anymore in the colleges and universities"
Her whole interview is great...in fact the whole book is fantastic, one of the best books about programming I've ever read.
- DannyBee 12y agoFran is right in the sense that C is a very very hard language to do these things for. But she's wrong in the sense that it caused massive amounts of funding to be poured into trying to make it happen anyway. It's like saying Itanium was a complete failure for compiler optimization. It is in the sense that they couldn't get compilers that produced good enough code for it (well, the could, just not compilers that ran fast). But the amount of research and funding used to try to make it happen actually did advance the state of the art in compilers. The techniques we learned weren't all useless, and we discovered a lot about the limits of what can be done. Fran, btw, is one of the smartest people you'll ever meet. Just last year I discovered, through some IBM Research colleagues, a really great algorithm that she came up with for region analysis, that solves a lot of the problems of common ones, cleanly, and nobody has rediscovered it in 35 years yet. (Sadly, this falls into the "i wish they had published more papers on stuff" area)
- Elzair 12y agoCan you share this algorithm?
- DannyBee 12y agoIt was given to me by Kenny Zadeck in the form of an an unpublished chapter of a book that they had been working on. I was asked not to reshare it because of that, so i haven't. The book, sadly, still has not been published.
- beagle3 12y ago> It is in the sense that they couldn't get compilers that produced good enough code for it (well, they could, just not compilers that ran fast). Can you elaborate on that? My last update is from 2002, from an Intel guy who was working on it and said they couldn't. I was under the impression that no much has changed since - but perhaps I am wrong? (and perhaps I misunderstood him in 2002)?
- DannyBee 12y agoThey could do it by ~2005. In any case, it's always been possible. At worst, you make large integer linear programming based models of what you want to happen, and solve them. You can do optimal register allocation and scheduling, etc. You can basically shove everything you want into the ILP model. It's just going to take a ridiculous amount of memory and time to solve.
- Animats 12y ago"C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine." She's right. As I occasionally point out on why C programs are so buggy, the three big problems in C are "how big is it", "who owns it", and "who locks it". The language doesn't help with any of those. Those problems also inhibit optimization. One optimization that's been lost to history is optimizing subscript checking. This was done in some Pascal compilers, and about 95% of subscript checks can be optimized out. Where there's a loop involved, it's often possible to make one check at loop entry, rather than a check at every reference. Sometimes that one check can be proven true from FOR statement bounds, and can be eliminated. This is usually the case for numeric matrix work, where it really matters. I had a talk with one of the designers of Rust about this last Wednesday. They're not optimizing subscript checks yet. They hope to do so. They're currently limited by being a front-end to LLVM, which doesn't really comprehend subscript checks. The Go compiler does some subscript check optimizations, but only on FOR statements of restricted form. C, Go, and Rust all lack multidimensional arrays. This prevents a whole range of array-related optimizations which FORTRAN compilers have had all the way back to Backus's first FORTRAN compiler in 1956. This is part of why the supercomputer crowd still uses FORTRAN. I was trying to push the Go crowd towards multidimensional arrays. People in love with the slicing syntax wanted to extend it to multidimensional arrays. There were long arguments over how far to take that. Should you be able to slice out an arbitrary sub-hypercube of an N-dimensional array? If you allow that, you have to have a slice representation which is general but inefficient. After much discussion, nothing happened. Meanwhile, the number-crunching crowd is trying to compile Matlab, which has multi-dimensional arrays but not much else.
- CyberDildonics 12y agoJulia is definitely worth a look as it has taken on some of these issues (multi-dimensional arrays, slicing, some bounds checking). Now that it has a good garbage collector its remaining achilles heals are multi-threading (there are multiple processes that can send messages though) and long start up times for some modules (no JIT caching yet). It does make a lot of really good decisions at the language level though and is faster than many native languages while being more flexible than many scripting languages.