4 ms·

I'm not a compiler engineer, but I think it's a diminishing returns issue. Modern optimising compilers are already impressive, and they get more impressive year

I'm not a compiler engineer, but I think it's a diminishing returns issue. Modern optimising compilers are already impressive, and they get more impressive year on year, but only quite slowly. We don't see compilers producing code that runs 30% faster than the code generated last year, for instance. Such improvements can happen with compiler updates, but not when the starting point is a compiler that's already of decent quality. I recall some GPU driver updates from ATi (years ago) delivered pretty drastic performance improvements, but I believe that's because the original drivers were rather primitive. (Perhaps a drastic improvement to autovectorisation could give a 30% boost, or better, but this would apply only to certain programs.) You could grant a compute budget 100x the typical build set-up, but no one has built a production-ready compiler to take advantage of that, and if they did I suspect the improvements would be unimpressive. They may also run into a 'complexity ceiling' issue, as the compiler would presumably be even more complex than today's ordinary optimising compilers, which are already enormous. As Filligree says, superoptimisers tend to only be practical for very short programs. They can't be applied to monstrous codebases like Chromium.

alserio 3y ago
But maybe you can superoptimize some hot sections, and encode the superoptimizer findings somewhere. Then the compiler can validate the optimizations and apply them to the particular piece of code for the rest of the program life, untill the preconditions hold.
- MaxBarraclough 3y ago
  As I understand it they just aren't very practical. Perhaps you could use a superoptimizer in a targeted way, assuming that: 1. The codebase has hot loops of very short sequences (or can be automatically reshaped into this patten) 2. The superoptimising compiler can produce code that significantly outperforms the code generated by ordinary optimising compilers 3. A practical superoptimising compiler exists I can imagine these assumptions may not hold in practice. > the compiler can validate the optimizations A compiler transforms code from one representation to another, it doesn't validate arbitrary transformations. It's not easy to prove that a given fragment of source-code corresponds to some given assembly code. I've heard of only one instance of this being done. [0] > untill the preconditions hold I'm not sure what you mean by this. [0] https://entropy2018.sciencesconf.org/data/myreen.pdf https://entropy2018.sciencesconf.org/data/myreen.pdf
thesz 3y ago
The ability of compilers to make code faster is 12 (twelve) times slower than Moore's law: they double the program's speed in 18 years [1]. [1] https://proebsting.cs.arizona.edu/law.html https://proebsting.cs.arizona.edu/law.html This might seem discouraging, but it is not - one can still reap the benefits of code optimization twelve times as long after Moore's law stops working.
MaxBarraclough 3y ago
Something I missed: compilers are a mix of clever theoretical work and hard graft in implementation. Even if you somehow implement a practical compiler that exhausts the state of the art in compiler theory (a multi-million-dollar project in itself), you might still not be where you want to be in terms of optimisation.

alserio 3y ago

But maybe you can superoptimize some hot sections, and encode the superoptimizer findings somewhere. Then the compiler can validate the optimizations and apply them to the particular piece of code for the rest of the program life, untill the preconditions hold.

MaxBarraclough 3y ago
As I understand it they just aren't very practical. Perhaps you could use a superoptimizer in a targeted way, assuming that: 1. The codebase has hot loops of very short sequences (or can be automatically reshaped into this patten) 2. The superoptimising compiler can produce code that significantly outperforms the code generated by ordinary optimising compilers 3. A practical superoptimising compiler exists I can imagine these assumptions may not hold in practice. > the compiler can validate the optimizations A compiler transforms code from one representation to another, it doesn't validate arbitrary transformations. It's not easy to prove that a given fragment of source-code corresponds to some given assembly code. I've heard of only one instance of this being done. [0] > untill the preconditions hold I'm not sure what you mean by this. [0] https://entropy2018.sciencesconf.org/data/myreen.pdf https://entropy2018.sciencesconf.org/data/myreen.pdf

thesz 3y ago

The ability of compilers to make code faster is 12 (twelve) times slower than Moore's law: they double the program's speed in 18 years [1]. [1] https://proebsting.cs.arizona.edu/law.html https://proebsting.cs.arizona.edu/law.html This might seem discouraging, but it is not - one can still reap the benefits of code optimization twelve times as long after Moore's law stops working.

MaxBarraclough 3y ago

Something I missed: compilers are a mix of clever theoretical work and hard graft in implementation. Even if you somehow implement a practical compiler that exhausts the state of the art in compiler theory (a multi-million-dollar project in itself), you might still not be where you want to be in terms of optimisation.