6 ms·

Is there any literature or guidelines on what to do if I'm willing to spend effectively unlimited CPU cycles in return for a more optimized final output?

• thesz 3y ago
  Superoptimizers: https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization Also, program distillation: https://www.researchgate.net/publication/220989887_Distillation_Extracting_the_essence_of_programs https://www.researchgate.net/publication/220989887_Distillat...
  • mort96 3y ago
    Isn't it a bit weird that this isn't just the standard? Like imagine if Chrome was optimized with such a superoptimizer; let the optimizer spend a couple hours every month or so when cutting a new release. Surely that has to be worth it?
    • kibwen 3y ago
      Doing a full-fledged release-this-to-millions-of-users build of Chrome or Firefox already takes on the order of 24 hours (or at least it did when last I checked a few years ago).
    • remorses 3y ago
      I am pretty sure the existing release process already takes much more than 2 hours.
    • Filligree 3y ago
      Is it just a couple hours? Even just ordering the optimisation passes is already an NP-complete process, so I could easily imagine superoptimisers would take trillions of years for a large program...
    • MaxBarraclough 3y ago
      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
    • kccqzy 3y ago
      Chrome already uses PGO: https://blog.chromium.org/2020/08/chrome-just-got-faster-with-profile.html https://blog.chromium.org/2020/08/chrome-just-got-faster-wit...
    • Ericson2314 3y ago
      Yes, it is weird. One thing that would help is that if we explicitly reimagine programming is characterizing the search space for the compiler, just as the e-graphs stuff in the article talks about separating generating alternatives from finding the best alternative.
    • fwip 3y ago
      I think the wide variety of hardware and complexities of running on a real system sometimes make this problem more difficult. Even within a given processor microarchitecture (say, just Zen 2, or just Haswell), different CPUs will be running at different frequencies, have different cooling solutions, and be running different microcode releases, all of which will affect which program is the fastest. And this is without considering cache pressure or memory latency, which is also dependent on any other programs the user happens to be running. Running a superoptimizer for your linear algebra program that runs on your Cray supercluster can give clear gains. Doing the same for every combination of user hardware seems less feasible - you may find output that is a clear win for the machines you tested on, but it's often possible that it will lose out on other machines.
    • imtringued 3y ago
      Do you even understand what super compilation is? If you understood it, you wouldn't be thinking of a "couple hours every month". Supercompilation on Chrome would require more than a million hours of CPU time.
• sanxiyn 3y ago
  Have a look at Unison which uses constraint programming to do optimal code generation. https://unison-code.github.io/ https://unison-code.github.io/