Re: optimizing compiler against average assembly programmer.

>>>>>>
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
--

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