4 ms·
What about superoptimization? For instance, Stoke (http://stoke.stanford.edu/ http://stoke.stanford.edu/) or Souper (https://github.com/google/souper https://gi
by programLyrique 6y ago
What about superoptimization?
For instance, Stoke (http://stoke.stanford.edu/ http://stoke.stanford.edu/) or Souper (https://github.com/google/souper https://github.com/google/souper). They will not find all optimizations of course, and program equivalence is undecidable indeed, but they are a good shot at optimal compilation, I would say.
- adrianN 6y agoJust because a problem is undecidable that doesn't mean that you can't in fact solve it for a large set of interesting instances (maybe all instances you care about).
- MaxBarraclough 6y agoIt's decidable provided the problem-space is finite, right?
- adrianN 6y agoEvery finite problem is decidable in linear time because you can hardcode the solution.
- MaxBarraclough 6y agoRight, meaning decidability isn't an issue for superoptimisation of many kinds of problems.
- FartyMcFarter 6y agoWhat does that mean in practice though? I can say that every finite computational problem can be solved in O(1), so if the universe is finite, all real problems can be solved in O(1). This sounds great until you realise that the constant factors involved would overwhelm any practical instance of this strategy.
- MaxBarraclough 6y ago> What does that mean in practice though? It means the idea isn't necessarily wholly impractical. That's not nothing. I imagine superoptimisers scale extremely poorly, but that's a different question. I imagine they're best suited to bit-twiddling problems rather than, say, figuring out the best assembly code to implement a parallel Timsort. I have to admit ignorance here though, I know almost nothing about superoptimisers.