Re: 'Superoptimizers'

nmm1@cus.cam.ac.uk (Nick Maclaren) writes:
> bill@amber.ssd.hcsc.com (Bill Leonard) writes:
> |> If someone wants a topic for research, here it is: Come up with a fast (and
> |> reliable) predictor of optimizations.
>
> The trouble is that it is a solved problem, and is equivalent to
> predicting whether a Turing machine will halt! At best, you can get
> it right most of the time.


That was my point: come up with a fast predictor that will usually be right.
Sorry if that wasn't clear.


> I would slightly dispute your statement that it is likely that there
> are few opportunities for optimisation - it is more usual that there
> are huge numbers, but insufficient information to decide which ones
> will do good, and which will do harm! But I rather doubt that you
> would classify such things as opportunities :-)


Right -- I don't. There are always large numbers of possible
transformations one might make, but we only want to make those
transformations that will, or at least appear to, make the program more
efficient. But the point is that the analysis required to find those
transformations that even *appear* to be profitable usually takes much
longer than the time to do the transformations themselves.


Just about every optimization I know about is at best a gamble -- you can't
*prove* it will make the program more efficient; there are just too many
variables. Many papers on optimization advertise proof of profitability,
but their definition of profitability is always limited to one or two of
the many variables. For instance, Partial Redundancy is provably
profitable if you assume that storing a previously computed result is
always more efficient than recomputing it. In practice, that is not always
true. I have seen several cases of common sub-expression elimination using
Partial Redundancy making the program slower!


--
Bill Leonard
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Bill.Leonard@mail.hcsc.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.