Open tdeneau opened 5 years ago
Given the type of techniques used that will make stochastic changes and follow gradients in the data, convergence speed is primarily a function of the difficulty of the search space, not its absolute size. As an example, a 2-dimensional flat plateau which provides no gradient and has a single outlier optimal point is far more difficult to search than a 100-dimensional bowl-shaped search space where you can easily follow the slope from any point to the optimal one. This is not true for all search techniques. For example, an exhaustive search would likely not work on the 100-dimensional space given its size.
Duplicating the default choice in GCC distorts the search space such that 2/3rds of the space are the choice the compiler writer thought should be the default and 1/3rd is the other option. This makes OpenTuner more likely to pick the default value and, assuming the writers of GCC chose good defaults, produces an average point in the search space that is more fit.
OK that makes a lot of sense. Some questions:
Are there easy ways to do the same thing for IntegerParameters? i.e., make it more likely the tuner would pick something close to the default? (but still allow the whole legal range of the integer parameter)
If for a boolean parameter, you wanted the weight for one choice to be more than 2/3 should you add additional enums that map to that choice, or is there a cleaner way to do this?
Implementing a WeightedIntegerParameter or WeightedEnum/Boolean would be easy to do. You would implement it with a projection from the unweighted space to a weighted space inside the parameter. You could look at the log scaled group of parameters as example of that.
In the gcc example writeup in Section 3.1 of the paper , I see
Why would including the default value speed up convergence? I would naively think that it would enlarge the search space and increase time to convergence.