6 ms·
The Death of Optimizing Compilers
- ufo 12y agoI'm only seeing the abstract here. Is there a link for the full tutorial?
- morcheeba 12y agoThe presentation hasn't happened yet. It will take place at ETAPS 2015: 11-18 April 2015, London, UK
- jeffreyrogers 12y agoFor those who aren't aware, this is an abstract for a talk to be given next month by Daniel Bernstein, who has written several very high quality C programs including qmail, daemontools, and djbfft, which is a very fast library for computing FFTs, so he presumably knows what he is talking about.
- danso 12y agoOn 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.
- mike_hearn 12y agoAnd the counter argument: http://www.chrisseaton.com/rubytruffle/cext/ http://www.chrisseaton.com/rubytruffle/cext/
- dalke 12y agoI read it, but I don't see the counter-argument. It seems to say that people who want a C extension for Ruby, for performance reasons over native Ruby, can use a system which dynamically compiles the C extension code. While this proposal seems to be that fewer and fewer programmers know how to optimize against the machine.
- mike_hearn 12y agoSo optimising compilers are becoming more important, not less, then. Edit: to clarify, the interesting thing about that blog is not the cross language interop magic, though that is pretty cool, it's that a smart compiler that can compile C and ruby together simultaneously can delete vast swathes of abstraction and overhead to produce radical speedups, just through better optimisation. So whilst things might not be moving very fast in the world of more traditional compilers, research compilers with a focus on dynamic languages are still showing big speedups. It's a bit early to proclaim the death of optimising compilers just yet, though perhaps I've just misunderstood the abstract. I'm not sure the latest hanging fruit for compiler developers is using more and more exotic machine instructions
- dalke 12y agoI view it as two different things. There are many optimizations which work on a simple machine model that hasn't changed much since the VAX. There's memory with constant time lookup, some registers, and assembly code. Real hardware changed long ago. As a simple example, on traditional hardware it's best to save and re-use intermediate values, but on modern hardware RAM lookup is so slow that it can be faster to recompute rather than doing a random lookup. An optimizing compiler isn't going to do much if the code wasn't designed to match the hardware, or expects a different hardware model. While lowering the impedance mismatch between two systems, whether it be two different languages as in your example, or serialization/deserialization, or call thunking, belongs to an old and well-understood set of optimizations which are nearly insensitive to the machine model. RAM lookup, and cache performance, and cache lines, are important for high performance code. Though as the abstract says, most people only work with "freezingly cold" code, so aren't aware of the limitations in the conceptual machine model vs. the actual machine. Fixing this almost always requires deep changes to the code, which an optimizing compiler can't do.
- Dewie 12y agoI don't have much faith in future processors if it really is impractical to make optimizing compilers for them.
- Animats 12y agoWell, that's happened in the past. Itanium and the Cell made it to volume production while presenting extremely hard problems for a compiler. I once met the group from HP who were trying to write an optimizing Itanium compiler. It wasn't going well at all. The Itanium could execute several instructions simultaneously, but the compiler had to block them together and specify this. About a hundred instructions at a time had to be scheduled together to get decent optimization.
- DannyBee 12y agoI'd be interested to see this talk, because as far as i know, it's pretty far off base. 1. He says" As computation has become cheaper, users have correspondingly expanded the volume of data that they are handling, and optimization remains a critical challenge for the occasional "hot spots" in the code."" Except, uh, a lot of people have applications whose profiles are mostly flat, because they've spent a lot of time optimizing them. We build optimizing compilers that can speed up these apps anyway. 2."Have compilers become so smart that they automatically turn clean high-level code for these hot spots into optimized code, removing the need for humans to be optimization experts? The reality, unfortunately, is very much the opposite: general-purpose "optimizing" compilers are falling farther and farther behind the actual capabilities of modern processors." This is just flat out wrong. That said, Daniel is a very smart (and obviously pretty opinionated :P) guy, so i'm really interested to see what he has to say.
- readerrr 12y agoOn 2.: Maybe he is talking about branch prediction vs lack of this feature in compilers. What do I mean by that is that optimizing compilers( at least in c ) don't optimize based on measurements from actual programs. A compiler that would run the program for a certain amount of time, to profile, could find the weak spots and optimize.
- mansr 12y agoGCC can do that.
- readerrr 12y agoYou are mistaken, unless you can prove me wrong. Care to elaborate?
- dalke 12y agoI assume mansr refers to profile guided optimizations in gcc and many other compilers. See http://en.wikipedia.org/wiki/Profile-guided_optimization http://en.wikipedia.org/wiki/Profile-guided_optimization.
- 101914 12y ago"...most users still spend time waiting for computers."
- amelius 12y agoI think what we need is a programming language that addresses performance orthogonally from correctness/functionality. What this means is that a programmer could write his code in a very easy-to-understand functional style (say), and then he could write a library of rewrite rules that allows the program to be executed more efficiently.
- Dewie 12y agoThat sounds like library writers being able to bake in optimizations (rewrite rules) into their libraries. Which makes sense; you distribute the optimizations to domain experts (like data structures) instead of just having general optimizations that the compiler writers had time to add.