Compiler Optimisation?

Compiler Optimisation?

[Iain Bate]

I am looking for some specific information on compiler optimisation
and I was wondering if anyone could help. Basically, I would like to
get some idea how much faster code executes due to optimisation. I am
looking for the information at two levels:

1. How much faster code executes due to the overall optimisation
process?
2. How much faster code executes due to specific optimisation stages,
e.g. the speed-up due to the peephole stage?

I realise there are some quite large variations in the type of
optimisation algorithms that are used, but I am simply looking for
some typical figures - if these exist.

I would be very grateful for any help that people can provide in terms
of actual information or guidance of where to look (I'm sure there
must be loads of data on this subject). Also, is there any chance any
replies can be copied directly to me at iain.bate@cs.york.ac.uk since
I will read it faster that way

Thanks in Advance

Iain
[The answer to both questions is "somewhat, usually, depending on the
application and the compiler" but perhaps some people can offer some rules
of thumb. -John]

Re: Compiler Optimisation?

[Marin David Condic]

Iain Bate wrote:
> 
> I am looking for some specific information on compiler optimisation
> and I was wondering if anyone could help. Basically, I would like to
> get some idea how much faster code executes due to optimisation. I am
> looking for the information at two levels:
> 
> 1. How much faster code executes due to the overall optimisation
> process?
> 2. How much faster code executes due to specific optimisation stages,
> e.g. the speed-up due to the peephole stage?
> 
If you get an answer to this, it is almost certainly going to be
compiler dependent and probably misleading. Consider that if a compiler
generates really crappy code in non-optimized mode, the optimization
could show a huge delta in performance. Whereas another compiler may
generate very tight code in non-optimized mode and hence get a much
smaller delta in optimization. So almost any quote you get ("Our
optimizer results in 50% improvement in performance! - by taking out all
the no-ops we stuck in there in the code generation...") is bound to be
misleading.

Your best bet is to get a representative sample of code for your
particular applications and run some timing studies comparing one
compiler to another at wound-full-out optimization. Almost anything else
is not going to provide you with much useful information.

MDC

-- 
Marin D. Condic
Real Time & Embedded Systems, Propulsion Systems Analysis
United Technologies, Pratt & Whitney, Large Military Engines
M/S 731-95, P.O.B. 109600, West Palm Beach, FL, 33410-9600
Ph: 561.796.8997         Fx: 561.796.4669

"The reasonable man adapts himself to the world; the unreasonable one
persists in trying to adapt the world to himself. Therefore all progress
depends on the unreasonable man."

        --  G.B. Shaw

Re: Compiler Optimisation?

[Ray Dillinger]

Iain Bate wrote:
>
> I am looking for some specific information on compiler optimisation
> and I was wondering if anyone could help. Basically, I would like to
> get some idea how much faster code executes due to optimisation. I am
> looking for the information at two levels:
>
> 1. How much faster code executes due to the overall optimisation
> process?

Depends on the language semantics among other things.  in LISP and its
cousins for example, optimization consists in large part of proving
that it's safe to eliminate symbol table checks and type lookups that
simply aren't required by the semantics of most languages -- as a
result, optimization of a LISP yields a much higher marginal return
than, say, optimization of Pascal.

> 2. How much faster code executes due to specific optimisation stages,
> e.g. the speed-up due to the peephole stage?

The speed-up due to the peephole stage in my experience runs between
ten and twenty percent of overall speed -- Although, of course, it
depends on what you put into the "peephole" stage.  I've purposefully
*not* done optimization in other stages that could be put off for the
peephole optimizer, which tends to make it seem a lot more important.

				Ray

Re: Compiler Optimisation?

[dewarr]

  Ray Dillinger <bear@sonic.net> wrote:
> The speed-up due to the peephole stage in my experience runs between
> ten and twenty percent of overall speed -- Although, of course, it
> depends on what you put into the "peephole" stage. ...

This is misleading. Many compilers do MUCH more extensive
peephole optimization. In particular gcc gets a FAR more
significant improvement from peephole optimization.

Re: Compiler Optimisation?

[Stefan Monnier]

>>>>> "dewarr" == dewarr  <dewarr@my-dejanews.com> writes:
> This is misleading. Many compilers do MUCH more extensive
> peephole optimization. In particular gcc gets a FAR more
> significant improvement from peephole optimization.

This often reflects the fact that optimisations interact and that they
are often designed based on their interactions.  In the SML/NJ example
mentioned by someone else, the `contraction' phase is relied upon by
many other optimisations (which end up just restructuring the code,
which in a first step makes it bigger and slower but exposes further
opportunities to the contraction phase).


	Stefan

Re: Compiler Optimisation?

[Ray Dillinger]

Ray Dillinger <bear@sonic.net> wrote:
> > The speed-up due to the peephole stage in my experience runs between
> > ten and twenty percent of overall speed -- Although, of course, it
> > depends on what you put into the "peephole" stage. ...

dewarr@my-dejanews.com wrote:
> This is misleading. Many compilers do MUCH more extensive
> peephole optimization. In particular gcc gets a FAR more
> significant improvement from peephole optimization.

Um.  True.  There are too many ways to interpret what I said.

Okay -- let me be a little more concrete.

Scheme (a LISP dialect), directly translated with optimizations
off, takes about 60 seconds to do something.

After LISP-specific optimizations (redundant-typecheck
elimination and constant folding of procedures) the resulting
code takes about 30 seconds to do something.

This is the rough equivalent of *unoptimized code* in most
imperative languages.

After various algorithmic optimizations such as constant
folding of variables, lifetime analysis, register assignment
analysis, inlining of constant functions, etc, the resulting
code takes about ten seconds to do something.

Finally we get to the peephole stage, and the resulting code
now takes about 5 seconds to run.

Total:  Of my original 60-second runtime, about 55 seconds
has gone away from the scheme program, ten percent or so of
which (5 seconds) was due to the peephole optimization.

But if I hadn't had to do LISP-specific optimizations, I'd
have started with a runtime of about 30 seconds and lost about
25 seconds of it -- about 20% of which (5 seconds) would have
been due to peephole optimization.

And this is what I meant when I said,

"The speed-up due to the peephole stage in my experience
runs between ten and twenty percent of overall speed."

But as dewarr pointed out, the sentence is darned ambiguous,
because I didn't say what I meant by "overall speed", which
is crucial.

In both cases, the code would take about twice as long to run
if no peephole optimizations had been done. In both cases,
it cut about 5 seconds from the total runtime.

				Ray

Re: Compiler Optimisation?

[Thomas W. Christopher]

How much faster does optimized code run for different optimizations?

I believe Daniel Bidwell ( http://www2.andrews.edu/~bidwell/ ) worked
on that question in his PhD dissertation, as well as how much do the
optimizations cost.

As I recall, he found that "folding," performing constant arithmetic at
compile time, not only makes the compiled code run faster, but also the
compiler.

--
Thomas W. Christopher -- tc@charlie.cns.iit.edu , tc@toolsofcomputing.com
Principal, Tools of Computing LLC. -- http://www.toolsofcomputing.com
Associate Prof., Illinois Inst. of Tech. -- http://www.iit.edu/~tc

Re: Compiler Optimisation?

[Mike Albaugh]

Thomas W. Christopher (tc@charlie.cns.iit.edu) wrote:
: How much faster does optimized code run for different optimizations?

: I believe Daniel Bidwell ( http://www2.andrews.edu/~bidwell/ ) worked
: on that question in his PhD dissertation, as well as how much do the
: optimizations cost.

: As I recall, he found that "folding," performing constant arithmetic at
: compile time, not only makes the compiled code run faster, but also the
: compiler.

	Perennial grump here. :-) In at least one case (gcc from at
least 1.31 to when I stopped bothering to look, 2.mumble) "folds"
structure member accesses inapropriately, so that "letting a function
know" what the value of a structure pointer is can produce much worse
code.  I would expect that if they don't fix this and start in-lining
really aggressively, code performance could deteriorate unexpectedly
as the inliner "gets smarter" and enlarges the scope of "knowledge".

	In case I have been too terse, what I'm talking about is:

static struct foo {
	int a;
	int b;
	int c;
} myfoo;

int foosum() {

	struct foo *myfp = &myfoo;

	return myfp->a + myfp->b + myfp->c;
}

gcc (often) generates code as if that last line was:

	return myfoo.a + myfoo.b + myfoo.c;

(or more pedantically, as if the whole expression was "flattened" into
a nasty mess of casts to int pointers with constant offsets)

	In the _best_ case, this simply turns a pointer-load and three
(base+disp) instructions into three 32-bit-address instructions.  On
some machines, it gets even worse. In theory, the compiler _could_
recognize the common expression and re-generate the pointer form, but
a) it apparently doesn't and b) to do so would take time, so the
folding, at least in this case, would not be making the compiler
itself faster.

	Not to say that "folding is bad", but rather "Optimizations
can interact, there is no free lunch" :-)
						Mike
| albaugh@agames.com, speaking only for myself

Re: Compiler Optimisation?

[John F Carr]

Thomas W. Christopher <tc@charlie.cns.iit.edu> wrote:
>As I recall, he found that "folding," performing constant arithmetic at
>compile time, not only makes the compiled code run faster, but also the
>compiler.

On AIX 3.1, I found that "gcc -O -c" was often faster than "gcc -c"
because the assembler was so slow.  Apparently IBM didn't use it much
internally (or adb, the assembly-level debugger which was also slow
and buggy).  It was faster for gcc to optimize the code than it was
for as to process the extra instructions in unoptimized code.

--
    John Carr (jfc@mit.edu)

Re: Compiler Optimisation?

[Andy Gaynor]

I recall an interesting section in "Compiling with Continuations"
by Appel in which he explores the effects of enabling and disabling
specific optimizations in an ML compiler.  Good reading.