[Optimization: Conclusions from Evolutionary Analysis]

I'm cross-posting the message below (from GCC list) because I believe it
would (at some point) be very beneficial to build an evolutionary
optimization pass into LLVM. The idea would be to discover the perfect
set of optimizations for a given program by trying them all and
analyzing the execution times of each. This would be somewhat like
profile driven optimization except the profile is easier to gather: its
the whole program timing. I imagine a "mega pass" could be written that
tries all other passes in all their combinations to (eventually) arrive
at the right set for a given program. There's one big issue with this:
workload. Unlike profile-driven optimization, which can find parts of
the program to optimize based on data collected from a run or several
runs of the program, this evolutionary pass would need to run the exact
same workload multiple times to discover which optimizations to apply.
Obtaining a useful/typical workload for a given program will be
difficult. Its easy for compilers and the like, but not all programs
work that way (consider optimizing a web server this way). Probably the
right approach is to punt on the workload issue leaving it to the
programmer to invoke/drive the program in such a way that it finds a
consistent workload to execute.

I know its early in LLVM's life for something like this, but I thought
I'd mention it so it can be tucked away in the "think about this later"
file.

Reid.

This is a hot topic in the compiler research community, but the focus there is on
(a) choosing the right optimization sequences internally and transparently, rather than through combinations of options,
(b) performance prediction techniques so you don't actually have to run gazillion different choices, and perhaps can even avoid the problem of choosing representative inputs, as you talked about, and
(c) developing flexible internal representations so that you can dynamically generate appropriate code sequences.

We are actually involved in a project with IBM that aims to look at all of these issues. Needless to say, I'm hoping that they will use LLVM as one of the components of the infrastructure for this work :slight_smile: They do seem interested.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/

This is a hot topic in the compiler research community, but the focus
there is on
(a) choosing the right optimization sequences internally and
transparently, rather than through combinations of options,
(b) performance prediction techniques so you don't actually have to run
gazillion different choices, and perhaps can even avoid the problem of
choosing representative inputs, as you talked about, and

My experience with performance prediction (over a 20 year career) is
that its useless. The simulation world has long sought to be able to
predict outcomes, performance, scalability, etc. I haven't seen a model
yet that gets lower than a +/-50% error rate. In the general case, the
only *reliable* way to do it is through collecting actual data. Of
course, in the specific case of compiler output, it might be possible to
get higher levels of accuracy. It'll be interesting to follow this
research.

(c) developing flexible internal representations so that you can
dynamically generate appropriate code sequences.

Now THAT I agree with :slight_smile:

We are actually involved in a project with IBM that aims to look at all
of these issues. Needless to say, I'm hoping that they will use LLVM
as one of the components of the infrastructure for this work :slight_smile: They
do seem interested.

I hope so too .. great validation.

Reid.

This is a hot topic in the compiler research community, but the focus
there is on
(a) choosing the right optimization sequences internally and
transparently, rather than through combinations of options,
(b) performance prediction techniques so you don't actually have to run
gazillion different choices, and perhaps can even avoid the problem of
choosing representative inputs, as you talked about, and

My experience with performance prediction (over a 20 year career) is
that its useless. The simulation world has long sought to be able to
predict outcomes, performance, scalability, etc. I haven't seen a model
yet that gets lower than a +/-50% error rate.

We should probably take this discussion of this list, but here's a counterpoint :slight_smile: This is a paper that is to appear in ACM TOCS and describes a manual, analytical modeling technique that gets 0-10% prediction errors for complex, real-world parallel programs on real systems:
    Vikram S. Adve

My experience (after having done my Ph.D. thesis on performance prediction and then abandoned it) is that it is really hard to do comprehensive performance prediction for all aspects of program behavior, but much more tractable to do it for individual performance issues. Also certain issues (e.g., processor pipelines) are much harder than others.

But I think your other points below are quite valid:

In the general case, the
only *reliable* way to do it is through collecting actual data.

In fact, combining real data with models is what is often needed (and what we used).

Of
course, in the specific case of compiler output, it might be possible to
get higher levels of accuracy. It'll be interesting to follow this
research.

This can also make it more practical for programmers to actually use.

(c) developing flexible internal representations so that you can
dynamically generate appropriate code sequences.

Now THAT I agree with :slight_smile:

We are actually involved in a project with IBM that aims to look at all
of these issues. Needless to say, I'm hoping that they will use LLVM
as one of the components of the infrastructure for this work :slight_smile: They
do seem interested.

I hope so too .. great validation.

Reid.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/