From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on ip-172-31-74-118.ec2.internal X-Spam-Level: * X-Spam-Status: No, score=1.8 required=3.0 tests=BAYES_50,TO_NO_BRKTS_PCNT autolearn=no autolearn_force=no version=3.4.5-pre1 Date: Fri, 28 Jun 91 21:39 GMT From: Frank Pappas <0004238973@mcimail.com> Subject: Program tuning Message-ID: <90910628213909/0004238973NC4EM@mcimail.com> List-Id: 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 ====================================================================