User: Password:
Subscribe / Log in / New account

Rethinking optimization for size

Rethinking optimization for size

Posted Jan 31, 2013 21:25 UTC (Thu) by robert_s (subscriber, #42402)
Parent article: Rethinking optimization for size

Offtopic, but this article reminded me of some work a GHC developer did a few years ago using genetic algorithms to search for an optimal set and order of LLVM optimization flags for a particular program.

(Quite a commendation to LLVM that it allows this amount of control over optimization passes I suppose)

Wonder if anyone's done any further work on the subject.

(Log in to post comments)

Rethinking optimization for size

Posted Feb 1, 2013 16:20 UTC (Fri) by NAR (subscriber, #1313) [Link]

This occurred to me also while reading through the article - with a good benchmark finding the right optimization can be automated (to a degree).

Rethinking optimization for size

Posted Feb 4, 2013 18:38 UTC (Mon) by ssam (guest, #46587) [Link]

if you have the time then profile guided optimization (PGO) is worth a look. You compile, then run the code with a profiler so that you know which bits of code are used the most. Then the compiler can be selective about how different bits get optimized. At a simple level use -Os for rarely called functions and -O3 for repeatedly called ones.

Rethinking optimization for size

Posted Feb 4, 2013 23:29 UTC (Mon) by rgmoore (✭ supporter ✭, #75) [Link]

It seems like PGO is something that would only have to be run once in a while. The hot code paths are likely to stay hot unless you substantially rewrite your program. So you'd only need to run the profiling occasionally, then use that to optimize your choice of compiler flags, which could be written into the makefile. Everyone downstream could benefit from the improvements without having to do the profiling themselves.

Rethinking optimization for size

Posted Feb 5, 2013 19:10 UTC (Tue) by khim (subscriber, #9252) [Link]

PGO does not work this way. It does not change set of flags - it's totally orthogonal optimization.

Basically a lot of optimizations are tradeoffs (perhaps most): "if we unroll this loop and it's hot then we win because it'll be faster, but if it's cold then we lose because we increase memory pressure... and we can unroll it twice or four time or even hundred of times... what to do, what to do". Without PGO there are some heuristics ("if branch will probably be taken more often then else branch", etc), but with PGO you know if the given piece of code is hot or cold. And this makes all the same optimizations perform better.

That's why you can not reuse results of PGO runs: you need the exact some code compiled twice. Most changes will invalidate the results (tiny changes in code may mean significant changes in the parsed tree - especially in C++). Yes, you know that hot codepath is still somewhere in this function, but where exactly? That's the question.

Rethinking optimization for size

Posted Feb 8, 2013 14:12 UTC (Fri) by jdbrandmeyer (guest, #85840) [Link]

Other way around, actually. Acovea came well in advance of your LLVM example, and the target compiler was GCC.

Rethinking optimization for size

Posted Feb 8, 2013 17:56 UTC (Fri) by daglwn (guest, #65432) [Link]

Oh, this was done long before that. See for example:

And that's just a small sample. In addition, there are many papers using genetic algorithms to drive the heuristic decisions within various transformation passes.

Rethinking optimization for size

Posted Feb 8, 2013 22:20 UTC (Fri) by Shewmaker (subscriber, #1126) [Link]

The first project that I remember seeing that seriously pursued automatically optimizing for whatever architecture you compiled it on was the ATLAS linear algebra library. It was moderately successful, but it could be beat by Goto's BLAS.

I remember ACOVEA too, but it looks like it is no longer being maintained.

There is a current effort, Collective Tuning that goes beyond ACOVEA's intentions. They compare it to their Continuous Collective Compilation Framework

I don't know how it compares to the LLVM work.

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds