Re: optimizing compiler against average assembly programmer.

Jerry Leichter wrote:
>The superoptimizer does a fairly dumb choice over all possible code
>sequences and chooses the one that is "best" according to some measure.


It is not as dumb as you may think. It does consider things like
register liveness information (it avoids instructions which overwrite
previously computed results or using registers with undefined
contents), which reduce the complexity from depending on the number of
different instruction words to depeding on the actual number of
possible operations (that is my understanding from looking at the
source code).


I will dare to sneak a good (IMHO) example for optimized assembly code
into this thread: George Woltman's optimized Lucas-Lehmer test based
Mersenne prime checker beats even heavily optimized Fortran programs
by a considerable amount (a factor 2, at least). I consider this a
good example, because it is a problem where this kind of effort
actually pays off: the program is not very complex and maintainable by
a single knowledgeable person, and hardly any features have to be
added in the future.


On the other hand, for a different class of problems, hand-optimized
code is easily "beaten": consider (run-time) specialization by partial
evaluation of an algorithm with regard to some input. Hand-coding the
specialized algorithm for every input is not a good idea. Since this
is what a compiler does (if you allow me to view the compiler as the
part of a fictitious interpreter responsible for specialization - a
somewhat arbitrary notion), this leads to the interesting(?)
conclusion that using a compiler is always superior to performing the
code generation manually, but as far as practicality is concerned, we
already knew that. This sounds like a no-op argument, but the bottom
line is: if your input (source code, algorithm) is constant, it may be
practical to perform the compiler's job manually (if you can be
expected to do as well or better). If it isn't, forget it (a
simplified, but applicable view).


Re-iterating this argument yields a slightly different result: even if
the program you have just hand-optimized uses a fixed algorithm, it
may be worth it to specialize it with regard to its input. For
example, the aforementioned primality test program typically runs for
several days to test a single prime candidate. Would a specialized
version for this number perform better than the general algorithm?
Very likely. Would a specialized version of, say, the Fortran version
perform better than the general but assembly- optimized version?
Maybe, but how long would it take to specialize the program?


For the question of whether a compiler will/can do better than an
average or expert assembly programmer, it's probably a good idea to
state the question clearly first. My (biased) opinion is that a
compiler will always be superior, as long as 1) the programmer is
willing to and not restricted by the language from specifying the same
amount of information about the program, and 2) the compiler is able
to use all of that information. (would anyone in *this* newsgroup
disagree?)


There are various other arguments in favour of compilers, like the
philosophical argument ("a general solution is always better than a
solution for a single case"), or the evolutionary argument ("if
assembly programming's value, all costs considered, were higher, why
are most people using compilers?"), but I feel I may have stressed
this topic enough already.


-nino
--
Marinos Yannikos, Dept. for Programming Languages and Compiler Construction
TU Wien - University of Technology, Vienna, Austria.
--

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