Comment by almostgotcaught
2 years ago
A compiler is a combinatorial optimizer (think bin-packing). In general, optimizers/solvers basically search for the best solution. Most production compilers don't have solvers in them, they use heuristics instead, but even the best solvers use tons of heuristics. Naturally a computer will search/try heuristics faster and more thoroughly than you but sometimes you can do better because performant searching is all about "knowing where to look".
Modern compilers are not doing much searching in general. It's mostly apply some feed-forward heuristic to determine whether to apply a transformation or not.
I think a slower, search based compiler could have a lot of potential for the hottest parts you're willing to spend exorbitant time on a search.
I have heard search based compiler optimization called "superoptimization"[1]. It seems interesting, but as far as I know has not seen much industrial use.
1. https://blog.regehr.org/archives/2578
It simply doesn’t scale. You can only superoptimize very short runs of code, nowhere anywhere close to even smaller code bases, let alone big ones.
2 replies →
I understand the compiler Microsoft uses to build release versions of Windows, Office etc is like this and can take days to run.
and well worth the cost
1 reply →
> Modern compilers are not doing much searching in general.
This is false. Any compiler that does register allocation and instruction scheduling (all of them) is searching for an optimal (or just good enough) solution to an optimization problem.
Where things get fun is when two optimizations combine to make things worse. They never tell you about that in compiler class!
It's like designing a house. If you want the master closet bigger, the master bath has to shrink. Everything is a tradeoff.
1 reply →
Can you give an example?
In general, searching any significant space is very slow, applying heuristics is much quicker.
6 replies →