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

Beware the simple, elegant solution.

[Thinkit3]

Toss around terms like genetic algorithm and neural networks, and some are dazzled by the elegance and simplicity of it. Well, then there's reality, which is often neither elegant nor simple. In Go, there is a computer player that utilizes neural networks, yet it is near the middle of the pack.

A good dose of skepticism should accompany any examination of the dazzingly elegant solution.

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.

Re:Beware the simple, elegant solution.

[Anonymous Coward]

THERE IS NO GENERAL SOLUTION to THE GLOBAL OPTIMIZATION PROBLEM!!!

There simply is no general way to find the "best" of something. I would actually argue that genetic algorithms are in fact not the most elegeant, but rather the most brute force way to find a solution. But this is often quite appropriate. For the code optimization case, you can either optimize your code from first principles, and hope to untangle all the implications of your choices to find the best combination of compiler flags, or you can brute force your way through the combinations using genetic principles to propagate better choices (and hope you don't get stuck in local minima...) The former analysis may give you better results, but it is probably not general enough to work on anyones code.

For another of example, take the Slashdot lameness filter. It should have filtered my yelling, but it didn't. Can you see why? Malda and co. could have used a (genetic|bayesian|stochastic) algorithm to characterize their filter!

(Sorry about the yelling)

Re:Beware the simple, elegant solution.

[vv2]

Alternatively:- Add up the number of hours spent running optimisations on compiler flags, deduct actual time savings, times hourly rate and then see if it would be cheaper to add (scrounge) some more processors....

Re:Beware the simple, elegant solution.

[Hard_Code]

Pretty attractive if the first best solution takes longer than the age of the universe to compute, I'd say.

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.

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

[Animats]

Actually, I meant to say hill-climbing rather than gradient ascent. True gradient ascent implies you can evaluate the local gradient, i.e. you can compute the derivatives which represent the local slope direction. You can't do that for discrite problems like this one. Gradient ascent is more appropriate to problems expressed as differential equations. (Although, having struggled with nonlinear differential equation solving in high-dimensional spaces for several years, I can report that it's no panacea.)

By "broad-front search" I mean one where you're searching the surface defined by the objective function from multiple starting points. GAs, neural nets, and simulated annealing all effectively do this. All three approaches are really special cases of a more general search operation. Because partisans of each approach use such different terminology, (much of it borrowed from biology) it's not obvious that this is the case.

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.

Re:Shortcomings

[psavo]

a full build of our main product takes over 12 hours on an 8 CPU machine

Err.. ever heard of rule that 5% of code does 99% percent of work?

If your application does 'diverse' kind of things (you mention DB's), then most probably when optimizing one module, you're hurting others. The obvious solution is to optimize module by module. Starting from the most abysmally slow, your build environment.

Fix the Compilers

[Gothmolly]

The compiler ought to optimize this stuff anyway! How about "set suck=(yes|no)" and "prefer=(speed|size)" as options. Let the compiler and its designers come up with what is required to meet (or approach) a programmer's wishes.

Re:GAs wrong tool for the job

[GlassHeart]

Why couldn't he just measure performance with and without each optimization and see which had the greatest improvement? Yes, this might not take into account interactions between different optimizations, but to the extent such interactions occur, it would probably be specific to his test cases anyway.

That's exactly the point. The goal is not to find a set of gcc switches that will work best on any program on any supported platform. The goal is to find the set that works best with this particular input, without human guidance.

10% or 20% improvements in compiler performance are of largely academic interest only these days most software's time is spent waiting on user input, disk IO, or network activity anyway?

First of all, what if you can get the 10% or 20% basically for free? That is, simply run your compile for a few unattended days to get the optimization? What is not worth human tweaking time can easily be worth machine time. Gentoo, although I do not use it myself, appears to be a vibrant Linux distribution based exactly on this point.

Secondly, most existing software are running on small CPUs all around you, not on your desktop. The constraints of memory usage and CPU power are still very real for them.

Finally, consider also that more efficient software may result in more idle hardware and lower power consumption. Imagine if all PCs in the world can get by with 5% less electrical power.

The Golden Rule of Optimization

[rhysweatherley]

Never forget the Golden Rule of Optimization: a quicksort compiled with no optimization will invariably beat the pants off a bubblesort compiled with the best optimizer in the universe.

Optimizers change the constants in the algorithm running time. They cannot change the algorithm's order.

With the exception of high-performance computing, no one needs a super-optimizing compiler any more. Instead, they need to (re-)learn basic algorithm and data structure theory.

Re:The Golden Rule of Optimization

[hh10k]

Perhaps you should re-learn basic algorithm and data structure theory, because bubblesort can beat the pants off quicksort when the data set is small enough. Anyway, if you're going to implement quicksort, don't you want a 20-30% faster quicksort?

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.

And your point?

[devphil]

While I don't disagree with your observations, I'm confused as to what they have to do with Ladd's project and the results shown.

Okay, find, I've written my decent quicksort. I know my basic algorithms and data structures. Now I would very much like to squeeze every last drop out of them. Here's a project that will tell me a good combination of options to use as a starting point. Don't tell me that I should just ignore all that and go re-re-re-learn basic algorithms. GCC is used by more than students.

More than that, it will tell the GCC maintainers which options should be on by default which currently might not be, and vice versa.

Good solution to the wrong problem

[WayneConrad]

There are domains where squeezing every last cycle out of the code matters. Many of us no longer work in those domains. Most of the code I've written in the last 4 years was developed and executed in an environment with essentially unlimited cycles, memory, and disk. The only exception was one project that got database bound, and compiler optimization won't help that.

For programmers who are no longer resource limited, using a language that optimizes for the human rather than the computer is a good idea. A language with garbage collection, low syntactic sugar, functional constructs like closures, and no separate compile phase make for happy code and happy programmers.

An interesting benefit of working in a humane language is that it can becomes easier to use a better algorithm. Many algorithms depend upon data structures that are difficult to implement in the land of DIY memory management, but a breeze in a more humane language. This can make a solution in the apparently unoptimal language outperform the solution in the optimal language. Of course, we *could* go faster using C or C++, but only if we have the extra time it takes to write the code.

Don't optimize for the computer unless the computer is the critical constraint. And, even then, only optimize the part that is the actual constraint.

Otherwise, optimize for the human. We're more important than the computer these days.