Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!rutgers!cmcl2!yale!mfci!colwell
From: colwell@mfci.UUCP (Robert Colwell)
Newsgroups: comp.arch
Subject: Re: quest for breakthroughs (long)
Message-ID: <647@m3.mfci.UUCP>
Date: 15 Feb 89 16:01:52 GMT
References: <740@tetons.UUCP> <76700063@p.cs.uiuc.edu>
Sender: colwell@mfci.UUCP
Reply-To: colwell@mfci.UUCP (Robert Colwell)
Organization: Multiflow Computer Inc., Branford Ct. 06405
Lines: 64

In article <76700063@p.cs.uiuc.edu> gillies@p.cs.uiuc.edu writes:
>
>O.k., here is an idea, perhaps based on a fallacy -----
>
>"Currently, the quality of the code from several commercial compilers
>and hand-optimization for the same machine (e.g. 68000) might vary
>tremendously.  The best (compiled or hand-optimized) code might easily
>be X (X >= 10?)  times faster than the worst.  What is this constant
>X, for most commercial compilers?  Why do compilers vary so much?
>Clearly, reducing X bootstraps the performance of *all*
>compilers/architectures.  Here's a plan:

I propose that part of the reason is that there is a lot of money
chasing compiler solutions for part of the "compilation space", and 
not much chasing it in other parts.  So a skew develops between how
good the compiler is in some parts of that space and how good it is
in other parts.  Handcoders are reasonably adept in all parts of the
space.  An example is how well compilers can vectorize code these days
vs. how well they do on garbage/serial code.

>1.  Discover X
>
>2.  Discover the three contributors to X with the most variance.
>    ...
>3.  Propose a technical solution for the top-3 contributers to the
>    variance of X.

To even have a prayer of getting anything reasonably interesting from
this line of inquiry, I suggest you need to focus on one architecture,
one language, and maybe even just a few benchmarks.  If you did that
the problem would be more tractable, and you'd have the opposite 
problem of extrapolating your results back out to other machines
and other languages at the end.  But at least you'd have something
concrete to say.

>Also, I've always wondered if we could design a simple architecture +
>language, from a theoretical standpoint, for which provably optimal
>code could be generated.
>
>You can perhaps start with some ultra-simple architecture (Turing
>Machine), and simple language (Turing Machine Language), and try
>abstracting the two farther apart to see how far you can get.

Nah, at that low a level, you could do what Henry Massalin did with
the "Superoptimizer" he built at Columbia (ASPLOS-II proceedings).
(His program tried every instruction sequence combination up to 
sequences of several instructions to find the ones that computed a
given function the quickest, including use of side-effects and
bizarre uses for carry bits and the like.  Fascinating experiment.)

But you could micro-optimize the entire program and still end up with slower
code than a handcoder or a good compiler for various reasons.  For instance,
the handcoder might have recognized some trig identity inherent to the
algorithm that wouldn't make economic sense to wire into the compiler's
knowledge base (since it doesn't come along often enough, and there's always
bigger fish to fry).  On the other hand, the compiler might recognize a code
transformation that entirely removes the section of code you were planning
to micro-optimize.  I think the problem is a lot bigger than your message
implies.

Bob Colwell               ..!uunet!mfci!colwell
Multiflow Computer     or colwell@multiflow.com
175 N. Main St.
Branford, CT 06405     203-488-6090