5 ms·
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.
by BeeOnRope 2y ago
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.
- jonjojojon 2y agoI 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 https://blog.regehr.org/archives/2578
- kaba0 2y agoIt 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.
- fooker 2y agoIt scales well enough. You can apparently run Souper on SQLite in 24 hours with a beefy machine, according to a talk I recently attended, by one of the developers.
- kaba0 2y agoThat’s a cool data point, thanks! Though mind that it is a superoptimizer on LLVM bitcode, not on machine code itself, avoiding all the combinatorial explosion of register allocations and probably a bunch of more, but I don’t know enough about the program.
- almostgotcaught 2y ago> 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.
- drpixie 2y agoCan you give an example? In general, searching any significant space is very slow, applying heuristics is much quicker.
- azakai 2y agoI'm not sure there is a clear separation between applying heuristics and searching a space. Often in compilers you search a subset of a space using heuristics, and you can adjust those to control how much of the space you cover. For example, here is a pass that reorders WebAssembly globals in the Binaryen optimizer: https://github.com/WebAssembly/binaryen/blob/main/src/passes/ReorderGlobals.cpp https://github.com/WebAssembly/binaryen/blob/main/src/passes... We have a simple criteria for the quality of a solution - how big the binary size is with an order - but the space of possible orders is huge (every permutation that keeps every global after its dependencies). What we do is a targeted search of that space using some heuristics using parameters that work well enough and aren't too slow in practice.
- almostgotcaught 2y ago> I'm not sure there is a clear separation between applying heuristics There is and it's quite simple: if your heuristic reduces the size of your search space faster than it takes to perform the search (ie try solutions) then you have a real algo on your hands. Otherwise you're just searching. This is basically the border between P and NP and it's just that in compilers most of the problems are NP hard so none of the heuristics are really that good.
- deleted 2y ago[deleted]
- gumby 2y agoI disagree with this part of your comment: > then you have a real algo on your hands To me an algorithm is closed, while a heuristic (aka rule of thumb) is just a fast way to probably get a better solution / subset of the solution space at the cost of possibly missing the optimal result or even ending up in a pessimal corner case. With an NP complete problem you'd rather have some solution rather than use up your lifetime searching for the best.
- gumby 2y agoI understand the compiler Microsoft uses to build release versions of Windows, Office etc is like this and can take days to run.
- deleted 2y ago[deleted]
- flamedoge 2y agoand well worth the cost
- deleted 2y ago[deleted]