4 ms·

This article provides an excellent overview of the latest in speed of optimizer vs quality of optimization. In particular, copy-and-patch compilation is still

This article provides an excellent overview of the latest in speed of optimizer vs quality of optimization. In particular, copy-and-patch compilation is still the fastest approach because it uses pre-compiled code, though leaves little room for optimization. Cranelift uses e-graphs to represent equivalence on the IR. This allows for more optimizations than the copy-and-patch approach. Of course, the most optimized output is going to come from a more traditional compiler toolchain like LLVM or GCC. But for users who want to get "fast enough" output as quickly as possible, newer compiler techniques provide a promising alternative.

weinzierl 3y ago
From what I understand, the big advantage of the e-graphs approach is, that the quality of the output is (within limits) a function the time and memory given. The more memory, the more nodes can be generated in the e-graph and the more time for search, the better the selected node. It might never be as fast as copy-and-patch or as good as LLVM or GCC, but this flexibility is a value in itself.
- thechao 3y ago
  When we first reviewed the equality saturation paper, we thought there was one major pro, and one major con: [pro] phase-ordering invariant; [con] at the time there was no (believable) way to extract the transformed graph in a non-hand-wavy-way. Personally, I think e-graphs should be combined with Massalin superoptimization — they're natural "duals" — and just turn the whole exercise into a hill-climbing process. You can tune the total effort by the set of passes used, the amount of time to drive the graph to saturation, and the method (and time) for graph extraction.
  - vlovich123 3y ago
    Can you memoize across invocations so that the time spent optimizing is cumulative across all builds?
    - fwip 3y ago
      Speaking as an e-graph rookie - I believe so, with caveats. You can certainly store the chosen extractions/optimizations and re-use any that don't change. For example, if a long chain of rewrites yields A ==> B ==> ... ==> Z, you could short-circuit that and assume that Z is still what you want to replace A with. Perhaps each time you compiled, you could only rewrite the 'changed' sections of the program, along with a randomly selected portion to explore for greater-optimization. (Although, you may just want to go all the way and write a tool that constantly adds to your equivalence DB in the background, with compilation just a matter of running your extraction heuristics.) You probably wouldn't want to store every possible rewrite, though, as the space complexity or retrieval cost is likely a bigger deal than the time complexity (you wouldn't load 2+2=4 from a database, you'd just do the addition). But, if you restore only a subset of equivalencies that are known to be useful, there's not a simple way to keep the optimization from re-exploring the "rejected candidates" (without shutting off the eclass entirely) - and, it's even not clear to me that you'd want to, as changing program context may end up meaning that M becomes a better replacement candidate for A than Z. (Boring prerequisites for this approach also include: consistent serialization of terms, avoiding storage of infinite equivalencies, like `A => A + 0 => A + 0 + 0 ==> ...` (and possibly of exponential equivalencies like the kind associativity rules can produce), and strong heuristics to capture "high-value" equivalencies that are both useful and cheaper to lookup than re-derive.)
      - thechao 3y ago
        I always thought that it'd be nice to build an expository version of eq-sat that just operated on straight-line code, and didn't try to use the complicated e-graph structure (does it still use pi-nodes? I've not looked at the paper in a decade). The major complexity of eq-sat is in the novel extraction heuristics, and the complicated data-structures only mask that. EDIT: Right. Blech. Theta & Phi nodes.
- cfallin 3y ago
  We actually take a fairly unconventional approach to e-graphs: we have a few linear passes and we do all rewrites eagerly, so we use them to provide a general framework for the fixpoint problem into which we plug in all our rewrites, but we don't have the usual "apply as much CPU time as you want to get better results" property of conventional equality saturation. I gave a talk about this approach, aegraphs (acyclic e-graphs), here: slides (https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf), video (https://vimeo.com/843540328 https://vimeo.com/843540328) (disclosure: Cranelift tech lead 2020-2022 and main author of the e-graphs mid-end, as well as regalloc, isel and its custom DSL, and other bits, along with the excellent team)
  - scoopr 3y ago
    I found the video to be great! Informative and understandable even when I'm just casually interested in compilers, with not a lot of real world experience writing them.
kapilsinha 3y ago
Agree, especially when developing, I'd assume speed of optimizer matters more than quality of optimization. I wonder though if LLVM spent less time on that "phase ordering" problem, what is the tradeoff between these two factors?
- boomanaiden154 3y ago
  LLVM doesn’t spend really any runtime solving the phase ordering problem since the pass pipelines are static. There have been proposals to dynamically adjust the pipeline based on various factors, but those are a ways out from happening.
vsnf 3y ago
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.

weinzierl 3y ago

From what I understand, the big advantage of the e-graphs approach is, that the quality of the output is (within limits) a function the time and memory given. The more memory, the more nodes can be generated in the e-graph and the more time for search, the better the selected node. It might never be as fast as copy-and-patch or as good as LLVM or GCC, but this flexibility is a value in itself.

thechao 3y ago
When we first reviewed the equality saturation paper, we thought there was one major pro, and one major con: [pro] phase-ordering invariant; [con] at the time there was no (believable) way to extract the transformed graph in a non-hand-wavy-way. Personally, I think e-graphs should be combined with Massalin superoptimization — they're natural "duals" — and just turn the whole exercise into a hill-climbing process. You can tune the total effort by the set of passes used, the amount of time to drive the graph to saturation, and the method (and time) for graph extraction.
- vlovich123 3y ago
  Can you memoize across invocations so that the time spent optimizing is cumulative across all builds?
  - fwip 3y ago
    Speaking as an e-graph rookie - I believe so, with caveats. You can certainly store the chosen extractions/optimizations and re-use any that don't change. For example, if a long chain of rewrites yields A ==> B ==> ... ==> Z, you could short-circuit that and assume that Z is still what you want to replace A with. Perhaps each time you compiled, you could only rewrite the 'changed' sections of the program, along with a randomly selected portion to explore for greater-optimization. (Although, you may just want to go all the way and write a tool that constantly adds to your equivalence DB in the background, with compilation just a matter of running your extraction heuristics.) You probably wouldn't want to store every possible rewrite, though, as the space complexity or retrieval cost is likely a bigger deal than the time complexity (you wouldn't load 2+2=4 from a database, you'd just do the addition). But, if you restore only a subset of equivalencies that are known to be useful, there's not a simple way to keep the optimization from re-exploring the "rejected candidates" (without shutting off the eclass entirely) - and, it's even not clear to me that you'd want to, as changing program context may end up meaning that M becomes a better replacement candidate for A than Z. (Boring prerequisites for this approach also include: consistent serialization of terms, avoiding storage of infinite equivalencies, like `A => A + 0 => A + 0 + 0 ==> ...` (and possibly of exponential equivalencies like the kind associativity rules can produce), and strong heuristics to capture "high-value" equivalencies that are both useful and cheaper to lookup than re-derive.)
    - thechao 3y ago
      I always thought that it'd be nice to build an expository version of eq-sat that just operated on straight-line code, and didn't try to use the complicated e-graph structure (does it still use pi-nodes? I've not looked at the paper in a decade). The major complexity of eq-sat is in the novel extraction heuristics, and the complicated data-structures only mask that. EDIT: Right. Blech. Theta & Phi nodes.
cfallin 3y ago
We actually take a fairly unconventional approach to e-graphs: we have a few linear passes and we do all rewrites eagerly, so we use them to provide a general framework for the fixpoint problem into which we plug in all our rewrites, but we don't have the usual "apply as much CPU time as you want to get better results" property of conventional equality saturation. I gave a talk about this approach, aegraphs (acyclic e-graphs), here: slides (https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf https://cfallin.org/pubs/egraphs2023_aegraphs_slides.pdf), video (https://vimeo.com/843540328 https://vimeo.com/843540328) (disclosure: Cranelift tech lead 2020-2022 and main author of the e-graphs mid-end, as well as regalloc, isel and its custom DSL, and other bits, along with the excellent team)
- scoopr 3y ago
  I found the video to be great! Informative and understandable even when I'm just casually interested in compilers, with not a lot of real world experience writing them.

kapilsinha 3y ago

Agree, especially when developing, I'd assume speed of optimizer matters more than quality of optimization. I wonder though if LLVM spent less time on that "phase ordering" problem, what is the tradeoff between these two factors?

boomanaiden154 3y ago
LLVM doesn’t spend really any runtime solving the phase ordering problem since the pass pipelines are static. There have been proposals to dynamically adjust the pipeline based on various factors, but those are a ways out from happening.

vsnf 3y ago

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.