5 ms·

Compiler Optimizations Should Pay for Themselves (1994) [pdf]

35 points by networked 9y ago

nickcw 9y ago
This sounds very similar to the criteria used by the Go team as to whether to add compiler optimizations or not, namely the optimization should speed up the compiler by at least an amount that the extra computation of the optimization takes. I don't think the go team worry about the size of the object as much though.
- david-gpu 9y ago
  Imagine using that yardstick to guide what optimizations to implement on a FORTRAN compiler -- it would be absurd! Most workloads don't have a lot in common with a compiler.
  - tzar 9y ago
    Imagine advertising FORTRAN as a developer-friendly language with fast compilation times! I'm sure the Go folks are using this metric because it's compatible with their goals, which aren't everyone's.
    - weberc2 9y ago
      The Go team has a whole bunch of benchmarks besides compiler performance by which they judge the language. Certainly maintaining good compiler performance means giving up some low-value optimizations, but it doesn't mean compiler performance is their only benchmark.
    - kwhitefoot 9y ago
      Last time I used a Fortran compiler my impression was that it was faster than compilers for most other common languages. And if you are developing scientific software I suspect that it is as developer friendly as most currently common languages.
- bjourne 9y ago
  I doubt that because it is only possible for the most trivial of compiler optimizations. For example, most compilers perform loop hoisting which speeds up unhoisted code. But if you are writing performance sensitive code to be used in a compiler, you would have hoisted your variables manually anyway! Other examples include register allocation which you can either do slow using graph coloring or fast using linear scan. Graph coloring leads to better code, but much slower compilation times. The compiler optimization that "pays for itself" is like a holy graal, it doesn't exist. :) No such thing as a free lunch. In the article they admit that, but argues that the somewhat slower compile times is worth it.
throwaway613834 9y ago
This only works for compilers written in the same languages as the ones they compile...?
- to3m 9y ago
  Better than that - it only really works for languages that are only used to write their own compiler ;)
moomin 9y ago
This is the “the compiler represents a typical workload” fallacy.
- tzar 9y ago
  Having read only the first paragraph of the paper, I feel I already disagree: > Trying to make an optimizing compiler as simple as possible and yet as powerful as necessary requires, before all else, a measurement standard, by which both simplicity and power can be judged. The goal is not to use the compiler as a proxy for runtime performance of other compiled programs, but rather a benchmark of a particular value (or maxim). You may not share that value, but I think you've mistaken the motivation.
  - sarah180 9y ago
    Having read the second paragraph of the paper, they propose that the time and size cost of self-compilation is a useful benchmark for whether the additional complexity of a compiler feature is justified by its benefits. I agree with moomin that accepting this benchmark carries an implicit assumption that self-compilation is a representative workload. The paper doesn't argue "you should have some benchmark": it argues for this particular one.
    - tzar 9y ago
      If it were merely used as a representative workload, one would apply a discount to the complexity and size of the compiler since it can be assumed that compiling a larger and more complicated program should take longer (i.e. the measurement would be something like loc/s). But that's not the case here, because the value of simplicity and size is pitted against performance. I think the delta of agreement here is small; I just mean to note that “justified” here includes the value of the simplicity of the compiler. I have a personal bias towards the paper of course, because I would love to be downstream of a fallacy that gave me the development ergonomics of any of the Wirth or Wirth-like languages.
- chrisseaton 9y ago
  Similarly, I think one reason that the programming-language community likes functional programming more than most people is that a compiler is fundamentally one big pure function.
CalChris 9y ago
This article was written in 1994 and its advice seems appropriate. For 1994. In 1993, the SPARCstation ZX had a maximum of 96 MB of memory. So code size was important back then. My iPhone has 2GB of DRAM now. You can get a 4.19TB EC2 instance [1]. Yeah, this might have been wise in 1994 but this is just spectacularly bad advice now. [1] https://techcrunch.com/2017/09/14/aws-now-offers-a-virtual-machine-with-over-4tb-of-memory/ https://techcrunch.com/2017/09/14/aws-now-offers-a-virtual-m...
gralx 9y ago
"Don't make impossible things" may be a helpful guideline to some, but I've never made an impossible thing in my life. It's something I have a peculiar genius for.
aseipp 9y ago
Chez Scheme essentially follows this rule, and has since its inception, and it is an incredibly impressive project IMO. It can compile itself in just a few seconds and has a fairly simple architecture (despite having 30+ distinct IR languages in the compilation pipeline, and Scheme being a relatively high level language already, on a ~100k(?) codebase) and it has very good overall performance for generated code that "scales well". It tries not to be too good at the expense of other things, or bad/unwieldly in others. The goal is more that "results are predictable and not fragile", but in practice it means you apply rules like this. It's like putting a monetary budget on feature creep, to me. Chez is a very pleasurable Scheme to work with. Apparently the only time they really violated this rule was when rearchitecting their compiler from using 5-6 distinct IR languages to over 30 of them using the "Nanopass" approach. So I assume the compile time simply went from "a few seconds" to "a few more seconds", but that's probably OK to do once over ~30 years, I guess. :) I was told once (by one of the developers of) the Microsoft C# compiler team followed a similar rule where they never made a release that regressed their internal compiler benchmarks, i.e. they were only allowed to get faster. Obviously the .NET runtime does a huge amount of heavy lifting in terms of a C# programs performance, making the compiler a bit simpler, but it still means things like optimizations must pay off in speed and effectiveness. They even rewrote the compiler from C++ to C# at one point and still met this goal somehow, apparently, and once you're at that point -- bootstrapping yourself -- you begin the virtuous cycle of self-improvement. I'd be interested to know if any C# developers have seen the Microsoft .NET compiler get slower -- everything I've heard is that it's very fast and nice to use.

35 points by networked 9y ago

This sounds very similar to the criteria used by the Go team as to whether to add compiler optimizations or not, namely the optimization should speed up the compiler by at least an amount that the extra computation of the optimization takes. I don't think the go team worry about the size of the object as much though.

david-gpu 9y ago
Imagine using that yardstick to guide what optimizations to implement on a FORTRAN compiler -- it would be absurd! Most workloads don't have a lot in common with a compiler.
- tzar 9y ago
  Imagine advertising FORTRAN as a developer-friendly language with fast compilation times! I'm sure the Go folks are using this metric because it's compatible with their goals, which aren't everyone's.
  - weberc2 9y ago
    The Go team has a whole bunch of benchmarks besides compiler performance by which they judge the language. Certainly maintaining good compiler performance means giving up some low-value optimizations, but it doesn't mean compiler performance is their only benchmark.
  - kwhitefoot 9y ago
    Last time I used a Fortran compiler my impression was that it was faster than compilers for most other common languages. And if you are developing scientific software I suspect that it is as developer friendly as most currently common languages.
bjourne 9y ago
I doubt that because it is only possible for the most trivial of compiler optimizations. For example, most compilers perform loop hoisting which speeds up unhoisted code. But if you are writing performance sensitive code to be used in a compiler, you would have hoisted your variables manually anyway! Other examples include register allocation which you can either do slow using graph coloring or fast using linear scan. Graph coloring leads to better code, but much slower compilation times. The compiler optimization that "pays for itself" is like a holy graal, it doesn't exist. :) No such thing as a free lunch. In the article they admit that, but argues that the somewhat slower compile times is worth it.

throwaway613834 9y ago

This only works for compilers written in the same languages as the ones they compile...?

to3m 9y ago
Better than that - it only really works for languages that are only used to write their own compiler ;)

moomin 9y ago

This is the “the compiler represents a typical workload” fallacy.

tzar 9y ago
Having read only the first paragraph of the paper, I feel I already disagree: > Trying to make an optimizing compiler as simple as possible and yet as powerful as necessary requires, before all else, a measurement standard, by which both simplicity and power can be judged. The goal is not to use the compiler as a proxy for runtime performance of other compiled programs, but rather a benchmark of a particular value (or maxim). You may not share that value, but I think you've mistaken the motivation.
- sarah180 9y ago
  Having read the second paragraph of the paper, they propose that the time and size cost of self-compilation is a useful benchmark for whether the additional complexity of a compiler feature is justified by its benefits. I agree with moomin that accepting this benchmark carries an implicit assumption that self-compilation is a representative workload. The paper doesn't argue "you should have some benchmark": it argues for this particular one.
  - tzar 9y ago
    If it were merely used as a representative workload, one would apply a discount to the complexity and size of the compiler since it can be assumed that compiling a larger and more complicated program should take longer (i.e. the measurement would be something like loc/s). But that's not the case here, because the value of simplicity and size is pitted against performance. I think the delta of agreement here is small; I just mean to note that “justified” here includes the value of the simplicity of the compiler. I have a personal bias towards the paper of course, because I would love to be downstream of a fallacy that gave me the development ergonomics of any of the Wirth or Wirth-like languages.
chrisseaton 9y ago
Similarly, I think one reason that the programming-language community likes functional programming more than most people is that a compiler is fundamentally one big pure function.

CalChris 9y ago

This article was written in 1994 and its advice seems appropriate. For 1994. In 1993, the SPARCstation ZX had a maximum of 96 MB of memory. So code size was important back then. My iPhone has 2GB of DRAM now. You can get a 4.19TB EC2 instance [1]. Yeah, this might have been wise in 1994 but this is just spectacularly bad advice now. [1] https://techcrunch.com/2017/09/14/aws-now-offers-a-virtual-machine-with-over-4tb-of-memory/ https://techcrunch.com/2017/09/14/aws-now-offers-a-virtual-m...

gralx 9y ago

"Don't make impossible things" may be a helpful guideline to some, but I've never made an impossible thing in my life. It's something I have a peculiar genius for.

aseipp 9y ago

Chez Scheme essentially follows this rule, and has since its inception, and it is an incredibly impressive project IMO. It can compile itself in just a few seconds and has a fairly simple architecture (despite having 30+ distinct IR languages in the compilation pipeline, and Scheme being a relatively high level language already, on a ~100k(?) codebase) and it has very good overall performance for generated code that "scales well". It tries not to be too good at the expense of other things, or bad/unwieldly in others. The goal is more that "results are predictable and not fragile", but in practice it means you apply rules like this. It's like putting a monetary budget on feature creep, to me. Chez is a very pleasurable Scheme to work with. Apparently the only time they really violated this rule was when rearchitecting their compiler from using 5-6 distinct IR languages to over 30 of them using the "Nanopass" approach. So I assume the compile time simply went from "a few seconds" to "a few more seconds", but that's probably OK to do once over ~30 years, I guess. :) I was told once (by one of the developers of) the Microsoft C# compiler team followed a similar rule where they never made a release that regressed their internal compiler benchmarks, i.e. they were only allowed to get faster. Obviously the .NET runtime does a huge amount of heavy lifting in terms of a C# programs performance, making the compiler a bit simpler, but it still means things like optimizations must pay off in speed and effectiveness. They even rewrote the compiler from C++ to C# at one point and still met this goal somehow, apparently, and once you're at that point -- bootstrapping yourself -- you begin the virtuous cycle of self-improvement. I'd be interested to know if any C# developers have seen the Microsoft .NET compiler get slower -- everything I've heard is that it's very fast and nice to use.