Optimal Optimizations: A Very Preliminary Report

[Scott Robert Ladd]

Diego Novillo wrote:
> I haven't visited your site, but from this message you seem to
> concentrate on one axis of the problem: the combination of the different
> optimization options.

I don't have much about this on the site yet. I'm making some design 
changes to reflect past tests, and am also looking for feedback from the 
GCC community (such as you've provided).

> As I see it, the problem has at least three dimensions:
> 
>      1. Selection of optimization options
>      2. Ordering of the different passes
>      3. Programs used as benchmarks

My test is looking at dimensions 1 and 3; my goal is to find the best 
optimization options for a half-dozen programs that employ a variety of 
algorithms.

> There may even be a 4th dimension: input language.  There are
> optimizations that are language specific that help certain languages but
> not others (escape analysis, dispatch table optimizations).

And the 5th dimension is platform; what works on ia32 may not work on 
SPARC or PPC.

Anyone have a spare PPC machine they can toss my way? I promise eternal 
gratitude! ;)

As for languages: I'm testing two, C and C++ (which, of course, have two 
different dynamics). What has surprised me most is how different the 
performance is between C and C++, even when the corresponding programs 
are "the same."

> In any case, I think what you're doing is great and I'm very interested
> in the results.  What are the applications that you're using for your
> study?

I'm writing benchmarks from scratch, pulling time-intensive code from 
several of my personal/business projects. Right now, I have a three very 
different numerical tests, an implementation of Huffman encoding, a 
b-tree (in memory) algorithm, and an OCR test.

My genetic algorithm has specific requirements for timing reports from 
benchmarks; I also need to benchmarks to run in a reasonably short 
period of time (say, 30-60 seconds per run), just for practical 
purposes. And the applications need to avoid being I/O bound...

In my experience, the performance of most programs is predicated on the 
speed of specific code segments; good profiling can identify such 
sections, which can then be analyzed with my genetic algorithm to find 
the "best" optimizations. I'm also finding some general trends that 
affect all my benchmarks.

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing