3 ms·
A compiler is a combinatorial optimizer (think bin-packing). In general, optimizers/solvers basically search for the best solution. Most production compilers do
by almostgotcaught 2y 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".
- BeeOnRope 2y agoModern 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 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]