Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!dcl-cs!aber-cs!pcg
From: pcg@aber-cs.UUCP (Piercarlo Grandi)
Newsgroups: comp.lang.misc
Subject: Re: Common subexpression optimization
Message-ID: <1625@aber-cs.UUCP>
Date: 9 Feb 90 20:11:49 GMT
Reply-To: pcg@cs.aber.ac.uk (Piercarlo Grandi)
Organization: Dept of CS, UCW Aberystwyth
	(Disclaimer: my statements are purely personal)
Lines: 85

In article <48942@ricerca.UUCP> David Chase <chase@orc.olivetti.com> writes:
    >About the "good enough" I am somewhat skeptical (especially about
    >the register allocators -- but then again, many modern machines
    >have more registers than variables...). Also, most of the time
    >these optimizations are irrelevant.
    
    Interesting assertion -- do you have references to support this?

Plenty. Several sources, most recently J. Mashey discussing
exception handling on the MIPS in comp.arch, state that it is
rare to find that you need more than 24-28 registers to cache
*all* variables (a particularly funny example is the Pyramid,
that has over fifty registers, and some researcher found that
in all programs they tried never more than half could be used).

Some references (the DEC WRL ones for the Titan) demonstrate
that if you do cache only frequently *used* variables the knee
of the curve is at the 8-12 registers level at most.

There are many papers that confirm the idea that most
(traditionally 80%) of a program has a negligible or small
enough effect on the total running time that optimizing it is
irrelevant, either by hand or mechanically.

    Especially, do you have evidence that vectorization is usually
    irrelevant?

I never said so. On the other hand I think that vectorization is
a program tranformation problem, and the 'compiler' proper
should have nothing to do with it. Vectorization is an issue
only because for historical reasons people want to continue
using 'implementation' languages as 'application' ones. 

Dusty decks rule the waves, unfortunately. On the other hand,
Knuth's observations on this problem, in Vol. 1 of the Art of
Comp. Prog. are still valid, I think (shortly: rewrite!).

    (1) Large costly compilers are only "bad news" if few programs are
    developed -- once a compiler is widely used, the extra time spent in
    its development is paid back many times over.  (Of course, first you
    have to get the compiler into wide use.)

First you have to get the compiler generating correct code. I
may be wrong :-), but the number of bugs in a complicated piece
of software grows more than linearly with its size. A compiler
is possibly one of the most critical components of your
toolset.

I am a (young) fogey, and tend to think that in these cases
prudence advises against getting such a crucial component as
complex as your address space allows you to.
    
    (2) Why do you assume that "precise coding" is good?  Does
    it get a program written more quickly, or make the program
    more maintainable, or more likely to be correct, or
    increase its portability?  In general, the answers are NO,
    NO, NO, and NO.

Let me differ. A program that requires the reader to second
guess the author is not going to be very maintainable, is not
very likely to be correct, is not likely to be very portable.
It may be *coded* more quickly, oh yes :-(.

Making obvious, documenting in the program text (comments can
be dangerous) all your assumptions is one of the tenets of
disciplined software engineering. I used to like the 'lint'
directive (e.g. /* NOTREACHED */) approach, for example. A
great aid, both for lint and for the human reader.

    Some programmers aren't that thoughtful -- would you
    trust such a person to hand-optimize code?

If you reckon that your optimizing compiler is less buggy and
more intelligent than your programmer, all that I say blows up.
I have to admit that this is usually the case, though. On the
other hand, I think that the problem is better solved thru
programmer training (but we all know about the realities of
deskilling) or via programmer's assistants, which should not be
made parts of the compiler -- for the same reason for which
'lint' as not part of the compiler. I would dearly love to have
an "active" lint like tool.
-- 
Piercarlo "Peter" Grandi           | ARPA: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth        | UUCP: ...!mcvax!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk