Comment by drpixie

2 years ago

Can you give an example?

In general, searching any significant space is very slow, applying heuristics is much quicker.

6 comments

drpixie

Reply
azakai  2 years ago

I'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...

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  2 years 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.

    • gumby  2 years ago

      I 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.

      1 reply →