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 "

Comments

Humm~~~

[Leffe]

In the article the author mentioned that the flags toggled by the -O options were unknown.

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 ;)) and the -v flag to see the information.

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

Re:Even more interesting for OSS

[!the!bad!fish!]

Imagine the pain of evolutionary algorithm optimized Gentoo installation. That'll beat the zealots.

Didn't do -mfpmath=sse,387

[wowbagger]

It does not look like he checked the value of using -mfpmath=sse,387 - only -mfpmath=sse.

I would question just using SSE for floating point if the code is written just using double values - IIRC SSE doesn't like doing doubles very well. Allowing the compiler to use both the 387 mathco registers as well as the SSE registers might be a win here.

The other point about using SSE for floating point would be to use simple floats and see what difference the math options make.

Re:Didn't do -mfpmath=sse,387

[MarcQuadra]

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.

Ouch

[Scarblac]

Q: How can you tell you have perhaps gone slightly overboard in making compiler optimization options available?

A: Your users have not just given up trying to reason out what they should do, or even brute forcing every possible combination, they're inventing fucking genetic algorithms to find out what works best.

Basically the act of "calling gcc from the command line" is know officially a murky problem space to attack with pseudo-random hill climbing stuff...

Re:Ouch

[GigsVT]

I just see this as an extension to the whole "extreme programming" idea of "code something, anything, until you get the output you want for your test cases, then stop coding".

It's a good idea in theory, but it seems much better to have a well thought out approach.

Re:Ouch

[Scarblac]

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... :-)

Re:Ouch

[RML]

I just see this as an extension to the whole "extreme programming" idea of "code something, anything, until you get the output you want for your test cases, then stop coding".

It's a good idea in theory, but it seems much better to have a well thought out approach.

Figuring out how different optimization passes interact is too complicated for humans to do correctly. The interactions tend to be subtle, unexpected, and sometimes completely counterintuitive. The only way to get it right is to run lots of real-world testcases with different combinations of optimizations and tune the defaults based on the results. Acovea just automates that for the nice folks working on gcc.

Performance by chance?

[MacroRex]

Using a GA basically means it randomly tries some flags. While this is nice and automated, I'd rather have the developer understand his/her code and the compiler to the extent that the best flags can be picked deterministically. Besides, the "optimizer" might very well pick flags that work with the test cases, but break the executable at some other place. At worst this might result in a some terribly hard-to-track security vulnerability.

Re:Performance by chance?

[shaka999]

I use GA's for circuit optimization all the time. They are very effective and often find things I wouldn't have thought of.

That said, you don't take their results and just run with it. I find you that once a solution is found I have to go back and understand what and why it did what it did. In the case of circuit optimization I need to make sure that the optimizer isn't just exploiting a modeling problem (this has happened a few times). In the case of optimizing for complier flags I'd imagine the same thing applies.

After the optimizer finishes selecting flags the developer should go back and make sure that all the flags make sense and aren't risky. Its at this point a developer can decide what he/she wants to use.

Gentoo

[motown]

It would be really cool if this technology could somehow be integrated into the Gentoo project.

Of course it would be unreasonable to have the each single ebuild compile and get benchmarked several times on each user's PC, but these genetical algorithms could be used to predetermine the optimal compiler settings for each architecture/ebuild-combination, store this information in a central database and have portage automatically select the optimal compiler setting from that database, each time it compiles an ebuild.

No more figuring out what the best compiler options are: the ebuild maintainers will take on that job for you! :)

Re:Gentoo

[motown]

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

Dupe ...

[dago]

yep, a pretty old one (18/11/2003), but still, here's the original story

PostgreSQL

[Earlybird]

PostgreSQL has been using genetic algorithm internally for some time, to optimize query plans.

A code optimizer seems like a natural application for GAs. If you can prove a piece of code's logical equivalence to another's, you can have a code generator produce random versions of the same code (functions, loops, blocks) and then run that as a GA to find the best-performing version. On the other hand, compilation might take ages to run.

Speaking as a GCC maintainer...

[devphil]

you have perhaps gone slightly overboard in making compiler optimization options available

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

now officially a murky problem space to attack with pseudo-random hill climbing stuff...

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.