Slashdot Mirror
Genetic Algorithms for GCC Optimization
captain igor writes "For the power users in the house that enjoy taking the time to squeeze every last drop of performance out of their programs, here's an interesting little program I ran across today call Acovea. Out since 2003, Acovea's main function is using genetic algorithms to determine an optimal set off Gcc optimization flags to squeeze the most performance out of a given program. Certainly an interesting concept, definitely worth a look. Some nice results on a P4 and Opteron can be found here "
In the article the author mentioned that the flags toggled by the -O options were unknown.
;)) and the -v flag to see the information.
I know that the listings in the manual are fairly accurate, not perfect though. If you want to know exactly what flags are activated when you compile you use the -Q flag (undocumented, AFAIK
gcc -v -Q file.c
Output:
[...]
options enabled: -fpeephole -ffunction-cse -fkeep-static-consts
-freg-struct-return -fgcse-lm -fgcse-sm -fsched-interblock -fsched-spec
-fbranch-count-reg -fcommon -fgnu-linker -fargument-alias -fident
-fmath-errno -ftrapping-math -m80387 -mhard-float -mno-soft-float
-malign-double -mieee-fp -mfp-ret-in-387 -mstack-arg-probe -mcpu=pentium
-march=i386
[...]
One thing I noticed with one of my GCCs is that -fomit-frame-pointer was not activated on -O3, even though the manual says it is...
That's a bit unfair, another EP idea is to refactor endlessly, always improving the code as much as possible. In the situations where EP is good, the alternative is "code something, anything, until you think your hack does what the customer/boss wants done within an hour, and besides it did work with the two things you tried out, so let's put it live". In that sort of environment (taken from my job...), your description of EP would be a marked improvement.
But anyway, this isn't about EP. My opinion of genetic algorithms is "something you try when you don't understand the problem". Instead of solving the problem you try out a bunch of randomly generating tries, slightly systematically, and hope it works out. It's applicable to situations with a lot of variation in different elements, where you don't know much about relations between the choices for different elements, etc.
So I'd say it's a bad idea in theory, but even so it sometimes works when you can't find a solution by thinking.
And the idea that finding the right command line options for gcc is somehow a good problem domain for these things, well... :-)
I believe posters are recognized by their sig. So I made one.
#include "coucou.h"
Unsafe "optimizations" don't deserve to be called optimizations and should never be enabled by a tool like this.
Ah, but the problem is the fact that certain optimization settings that are optimal for one piece of code can be very bad for other code. To make things worse: the target architecture is also part of the equation.
To sum it up: there is no single set of optimal compiler flags that result in the best performance in every situation. (If there was, then it would most certainly have been made the default setting).
"Oooh, does that mean we get to kick some puffy white mad zionist butt?"
I'm not sure you really understand how Genetic Algorithms (GA's) work. While they do contain a random element, they follow an evolutionary process that produces improved solutions in each "generation", based on genetic operations such as 'mutation'. So rather than just selecting "some" flags, the algorithm gradually proceeds toward an optimal combination. These algorithms are already commonly used in the analysis of medical and engineering data, so their use in compiler optimisation is hardly a major risk.
I can actually see GA's being quite effective for this purpose, as improvement in terms of performance measure by profiling would be very useful in identifying the best combination of GCC flags for a given set of code.
As for your suggestion that the developer should be able to make optimisation decisions manually, should that apply to all the other optimisation techniques already employed by modern compilers?
There's good reason for that, GCC can make code with '-mfpmath=sse,387' but it's not been 'modeled' properly, nor can GCC properly predict the outcome of trying to use registers that might be shared or step on each other. I'd run SCREAMING from that flag, '-mfpmath=sse' gets you properly-formed code for a fact, and that's what we're all looking for.
"Sometimes, I think Trent just needs a cup of hot chocolate and a blankie." -Tori Amos on Nine Inch Nails
I think that optimisation would first come from analyzing individual programmatic constructs (patterns) rather than the huge conglomerates that are whole applications. But then again I'm an embedded developer so I tend to think small.
Nothing in the world is more dangerous than sincere ignorance and conscientious stupidity.
...I strongly agree. No other compiler in history has this many knobs and dials. They interact in strange and unpredictable ways. Even worse, the -f (functionality/features) options can't be tested with all the possible -m (machine-specific) ones due to the number of platforms required. So we get bug reports complaining that -ffoo combined with -mbar on the Foonly 3000 causes random explosions killing a busload of nuns, and all we can do is shrug and say, "the -ffoo designers didn't have a Foonly, so just Don't Do That."
One of the things I'm pushing for GCC 4.x is to take an axe to the -f switches. It won't get consensus, of course, but it'll raise interesting discussion.
There's an insult in there somewhere, but I'm not sure what you're trying to attack.
Optimization options have always been a murky problem space in GCC. No other compiler targets as many processors as we do. The Right Thing on one chip will not be the Right Thing on another; that's why we have this mess.
As for what you call "peudo-random hill-climbing stuff," probably with little Dogbert-like waves of your hand, I suggest you take some formal courses in evolutionary algorithms. For solving non-linear discontinuous problem spaces, they are extremely effective, and go well beyond "hill climbing stuff."
One of the original goals of Acovea was to find better combinations of switches for popular platforms, and then make those the default for future major versions. I haven't followed the project as closely as I'd wished, so I can't say whether that's still the goal. Hope so.
You cannot apply a technological solution to a sociological problem. (Edwards' Law)
I have an application which I tried with sse,387 and the speed was slightly worse than sse. But on top of that I got random errors which I tracked down to an if () ... else ... block being exectuted where neither the if nor the else part was taken. A compiler bug for sure.