Re: optimizing compiler against average assembly programmer.

rhyde@cs.ucr.edu (Randy Hyde)
4 Jul 1997 14:53:49 -0400

          From comp.compilers

Related articles
[5 earlier articles]
Re: optimizing compiler against average assembly programmer. walter@bytecraft.com (Walter Banks) (1997-06-30)
Re: optimizing compiler against average assembly programmer. gclind01@starbase.spd.louisville.edu (1997-06-30)
Re: optimizing compiler against average assembly programmer. norman@kbss.bt.co.uk (Norman Hilton) (1997-06-30)
Re: optimizing compiler against average assembly programmer. debray@cs.arizona.edu (1997-06-30)
Re: optimizing compiler against average assembly programmer. cef@geodesic.com (Charles Fiterman) (1997-07-04)
Re: optimizing compiler against average assembly programmer. vkarvone@raita.oulu.fi (1997-07-04)
Re: optimizing compiler against average assembly programmer. rhyde@cs.ucr.edu (1997-07-04)
Re: optimizing compiler against average assembly programmer. WStreett@shell.monmouth.com (1997-07-08)
Re: optimizing compiler against average assembly programmer. monnier+comp/compilers/news/@tequila.cs.yale.edu (Stefan Monnier) (1997-07-08)
Re: optimizing compiler against average assembly programmer. charles.marslett@tempe.vlsi.com (1997-07-08)
Re: optimizing compiler against average assembly programmer. leichter@smarts.com (Jerry Leichter) (1997-07-09)
Re: optimizing compiler against average assembly programmer. rhyde@cs.ucr.edu (1997-07-09)
Re: optimizing compiler against average assembly programmer. rhyde@cs.ucr.edu (1997-07-09)
[7 later articles]
| List of all articles for this month |

From: rhyde@cs.ucr.edu (Randy Hyde)
Newsgroups: comp.compilers,comp.lang.asm.x86
Date: 4 Jul 1997 14:53:49 -0400
Organization: UC Riverside, Dept. of Computer Science
References: 97-06-071 97-06-082 97-06-110 97-06-140
Keywords: performance

>>>>>>
With all the DeepBlue-vs.-Mankind hoopla that was going around not
long ago, I'm surprised no one saw fit to mention Massalin's work on
the superoptimizer in this thread. While this isn't the sort of thing
compilers do routinely, it's an excellent illustration of the sorts of
things computers and brute-force search are good at and people aren't:


    H. Massalin, "Superoptimizer: a look at the smallest program",
    Proc. ASPLOS II, 1987, pp. 122-127.
<<<<<


Probably because every time someone mentions the superoptimizer I slap
them on the wrists and send them away. Obvously you must be new to
this variant of the "forever running thread."


Here's what's wrong with the superoptimizer:


(1) As the title above suggests, the SO produces the *shortest* possible
        program. This is not always the same thing as the *fastest* possible
        program.
(2) Optimization is provably NP-Complete and that's how the SO runs.
        In the example above, the sample function they computed required
        40 hours to compile to three machine instructions. Granted, this was
        on a 1987 vintage 68K or x86 (8 MHz, if I recall), but anyone who
        knows what NP-Complete means realizes that 600 MHz Alphas won't improve
        things much. True optimization is an intractible problem.
(3) The superoptimizers that I have looked at only use a small subset of the
        available machine instructions. The example in the article above, for
        example, does not consider the use of conditional jump instructions.
        You really need to ask yourself, "how optimal can a program be that isn't
        allowed to use any conditional jumps?"


Please study the aforementioned article before using it as references
in this thread. If you'd actually read (and understood) the article,
and like articles since then, you'd realize that this is no proof of
machine superiority over humans with respect to optimization.


BTW, shortly after the article appeared (discussing the "signum"
function, as I recall). I rewrote the signum function in a different
fashion and it only took me about 18 hours to come up with my solution
(which was just as good, but obviously not better than, the
superoptimizer's).


Randy Hyde
--


Post a followup to this message

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