Genetic Algorithms and Compiler Optimizations

mfago writes "Scott Robert Ladd has written an enlightening article and accompanying software package that utilizes genetic algorithms to optimize the optimization flags fed to a compiler. Those who have tried to squeeze the last drop of performance from a code know that it can be very difficult to determine the set of optimization flags beyond -O3 (with gcc for example) that yields the best performance. Lots of background links included in the article."

Comments

Re:Beware the simple, elegant solution.

[Anonymous Coward]

Yes, a good dose of skepticism should accompany such things... however, this particular example is one in which the search-space is finite, and you're using a genetic algorithm to cleverly navigate this space.

Neural networks are good when there is a massive amount of unknowns to deal with, and you're better off handling any patterns you can detect, but this is just a simple case of using a new(-ish) method to compare runs with (nearly?) all parameters. Nothing to be skeptical about, really.

How bumpy is the problem? Do you need a GA?

[Animats]

You could probably get equally good results with plain hill-climbing. Turn on all the optimizations. Then turn them off one at a time and see if things get better. Repeat until no improvement is observed.

Any time you consider using a broad-front search algorithm like a GA, a neural net, or simulated annealing, try plain-hill climbing first. If you try any broad-front search, compare it with plain-hill climbing. Only if the space being searched is dominated by local maxima (but not too many of them) do the broad-front algorithms help. And they're always slower.

If this guy had demonstrated that a GA did better than a plain hill-climber, he'd have an interesting result. But he hasn't demonstrated that.

Shortcomings

[hibiki_r]

Having worked on applying GAs to multi-objective optimization, I don't belive that this technique can be used effectively to optimize most programs.

The main issue is to compare the individuals generated by the genetic algorithm. To do so, we need to both compile the program under the specified settings, and then to be able to benchmark its performance. In my current job, a full build of our main product takes over 12 hours on an 8 CPU machine. Using a pretty conservative estimate, 100 generations with 100 individuals each, we'd be talking about more than a year of CPU time for a single run of the algorithm!

Even if we could ignore the amount of time required for compilation, we still have a second, more important flaw: Most programs out there are not really that easy to benchmark automatically. Database applications might need to go back to a known DB state to be able to run the benchmark faily. Also, server apps need to have the exact same load for every test if we want to be able to compare two executables fairly. This problem is increased when many compiler options will just create a 1% performance improvement or so. A poorly run system could lead the comparison function to just pick the wrong executable if the two executables didn't run in the exact same conditions.

I see how using GE for this task has a high coolness factor, and how it might even be usable for applications that are by nature easier to benchmark, but don't expect this technique to be applicable to enterprise-sized server applications, or even most GUI based apps any time soon.

Reliability, and porting to Macintoshes...

[billstewart]

Doing lots of Pentium-specific tweaks in your code may be zero or negative help when somebody wants to run it on a Macintosh....

More importantly, tweaking code for heavy optimization is not usually a good job for humans. It's fine if you've got a piece of hardware that you have to tweak the last few percent performance out of for an application that will run for many CPU-years, but you're almost always much better off if you

• Pick good algorithms
• Leave bit-bashing loop-twiddly optimization tricks to the compiler, and
• Put your human creativity skills to work on the next revision of your code, or on your next project if this one is done.