0004238973@MCIMAIL.COM (Frank Pappas) (06/29/91)
Some recent postings mentioned program optimization (which I prefer
to call program tuning). I thought it might be useful to post a few
paragraphs from two books that discuss this topic.
M. A. Jackson's Principles of Program Design, published by Academic
Press, is fairly old and uses COBOL as the example language, so I
don't know if many programmers still read the book. The chapter on
optimization begins:
The word optimization is ill-chosen. Its Latin derivation
implies that to optimize a program is to make it as good as
it can be; but what we mean by an optimized program is one
which is as small or as fast as it can be. In making it
small or fast, or, if we can, both, we are liable to make
it bad in various ways: it may be harder to understand,
harder to maintain and more prone to error.
In short, optimization costs money. We may define our
basic attitude to optimization in two rules:
Rule 1: Don't do it.
Rule 2: Don't do it yet.
The first rule tells us that we need a positive
quantified justification before we optimize, and that often
the justification simply does not exist. There is no sense
in making a program run faster if the result is merely to
increase the proportion of unused CPU cycles. There is no
sense in making a program smaller if the result is merely
to increase the number of unused locations in a
standard-size partition of store. There is no sense in
reducing the execution time by 5% if the result is to
increase by 5% the likelihood of a production rerun due to
program error.
The second rule tells us that we must always begin with
an unoptimized design, even if we intend to optimize it
eventually. Only an unoptimized design can have the clarity
and simplicity that are necessary for full understanding:
and we must understand our program fully if we are to
optimize it without introducing logical errors. Anyone who
has worked on program maintenance knows how dangerous it is
to change a program which is less than transparently
simple: apparently innocuous changes can have surprising,
and disastrous, effects.
Writing Efficient Programs by Jon Bentley, published by
Prentice-Hall, is a book every programmer should read. Bentley does
an outstanding job of explaining how to determine when program tuning
is called for, the dangers of premature tuning, and effective
techniques for tuning. The examples are written in Pascal, but most
of the techniques are equally valid in C, C++, Ada, Modula-2, etc.
The book deals with sequential programming. In particular, it
doesn't consider realtime programming but many of the ideas are
equally valid in concurrent and realtime programming.
Bentley emphasizes that programmers shouldn't count on their
``intuition'' when determining if and when a program needs to be
tuned. He urges that programmers use program monitoring tools to
determine those small portions of a program that might benefit from
tuning. The following example from his book illustrates what can
happen when programmers rely on their intuition:
... Victor Vyssotsky enhanced a FORTRAN compiler in the
early 1960's under the design constraint that compilation
time could not be noticeably slower. A particular routine
in his program was executed rarely (he estimated during
design that it would be called in about one percent of the
compilations, and just once in each of those) but was very
slow, so Vyssotsky spent a week squeezing every last
unneeded cycle out of the routine. The modified compiler
was fast enough. After two years of extensive use the
compiler reported an internal error during compilation of a
program. When Vyssotsky inspected the code he found that
the error occurred in the prologue of the ``critical''
routine, and that the routine had contained this bug for
its entire production life. This implied that the routine
had never been called during more than 100,000
compilations, so the week that Vyssotsky put into
prematurely optimizing it was completely wasted.
I don't understand why so many programmers think they know where
their program needs tuning. I remember a Microsoft C programmer who
was getting ready to write a DOS graphics program. He was going to
use the ROM BIOS directly rather than use the Microsoft Graphics
library because he already knew that using the graphics library would
make his program too slow. When I asked him how he knew that, he
said by looking at some generated code and seeing all these registers
being saved. He ``knew'' that by using the ROM BIOS he would save
only the registers that needed to be saved, thereby speeding up the
program. I lost contact with this programmer shortly after, so I
never did find out how the program turned out, but I pity the person
that has to maintain the program or port it to another platform.
Getting back to Bentley, he works out a really nice example of a
Pascal program that uses the nearest neighbor heuristic for the
traveling salesman problem. He starts with a straightforward
solution, tuning it using the techniques in his book, and ultimately
writing it in assembly language.
Speaking of assembly language, that's not an unreasonable approach
to tuning a program, regardless of whether it is written in Ada, C or
Pascal. When I write an Ada program, I view C as a high level
assembly language. If I determine that an compiler is not generating
efficient code for a piece of critical Ada code, I look to C. If I
don't think C will help, or if I try C and it doesn't help, then I'll
look at assembler. Fortunately, only small sections of code need to
be rewritten at a lower level.
I try to take a practical view to using Ada, not a fanatical one.
Ada makes sense because of its software engineering support, but I
try to keep in mind that even a nice house is connected to a sewer,
and sometimes, somebody has to go down that sewer to fix a problem.
(And some sewers lead out to C.)
====================================================================
INTERNET: fpappas@mcimail.com PHONE: (215) 789-3206
====================================================================