Programmer 7500/MAX_PROGRAMMERS.iso/PASCAL/TPOPTIMZ.ZIP/OPTIM.DOC

Text File | 1987-02-01 | 15.7 KB | 402 lines

     This  file   is  a  summary/outline  of   the  technical  article
     "Optimization Techniques" by Dr. Richard Reese which is one in
     a colletion   of   articles   entitled:

           "Turbo   Pascal  Advanced Applications"
             edited by Judie Overbeek
            published by Rockland Publishing
            190 Sullivan Crossroad
            Columbia Falls, MT

     You  can contact  Rockland for  a free  brochure about  the
     book.

     I  would  like  to  thank  the  publishers  at  Rockland for
     allowing me to summarize the key points and include excerpts
     from their  publication for educational purposes in the
     Borland Programmer's Forum Online Seminar: "Optimizing
     Turbo Pascal programs" :

     I like this article because it has some interesting and well
     thought-out  code  optimization  techniques  (at  the Pascal
     level) and feel it is  a good framework for discussion. This
     summary is not all inclusive,  I spent more time on sections
     I found  instructive  and  new,  and  briefly  (or failed to
     mention  at all)  sections which  refer to  issues that have
     appeared in a variety of publications, such as, how to set a
     pointer to an array type to save data space. I encourage you
     to get this book and read  the entire article as well as the
     other excellent articles in the journal.

     I have  thrown in  my  own  comments and  embellishments and
     attempt to make the distinction  between the article andthe
     asides clear. If  I am unclear in this  regard, my apologies
     to the author. If you have any questions send them to me Joe
     Schrader [76703,4161] in the Online Seminar in section 2 (or
     in section 4 after the seminar concludes).

     Optimization Issues : Speed versus Size, and Suboptimization

     Dr.  Reese  begins  by  stating  that  Turbo  Pascal  is  an
     efficient compiler but  there are limits to what  a compiler
     can do and a programmer  can perform techniques that improve
     the performance  of a program   by an order  of magnitude or
     better. Ok sounds promising.

     His most  important point in   the first section  is that a
     program's  performance is  measured  in  terms of  speed AND
     size.  In  addition  "there  is  almost  always  a trade-off
     between the  execution speed of   a program and  the size it
     requires." He points out that his emphasis in the article is
     speed optimization, which is  usually most talked about, but
     we  cannot  entirely  overlook  size  optimation. With Turbo
     Pascal's  64K  limit,  some  algorithms  require  the use of
     pointers  to  data  structures.  Since  pointer accesses are
     slower than  regular variable references, a  program that is
     not   optimized  for   size  can   have  a   degraded  speed
     performance.

     Programming has been characterized  as the use of algorithms
     and data  structures. Reese indicates  that when you  try to
     decide  between  data  structures  and  the algorithmns that
     manipulate them, there may be  some operations within a data
     structure which are efficient and other operations which are
     inefficient.  He  illustrates  this  point  by comparing the
     performance  of an  array implementation  of lists  versus a
     pointer  implementation. Some  operations are  quick on  the
     array  implementation  and  others  faster  in  the  pointer
     version.  The  key  is to  base design decisions  on  the
     operations your program will do  most often. Since you don't
     always  know how  your program  is going  to be  used, these
     types of design decisions are not always clear-cut.


     Optimization Techniques

     Dr. Reese lists three major classes of optimization techniques
     (listed in order of importance):

       1) Algorithm/Data structure optimization
       2) Code optimization
       3) Hardware optimization

     Algorithm/Data Structure Optimization

     The choice  of a good  formula and data  structure obviously
     has the greatest  impact on the speed of the  program but as
     someone in the Seminar pointed out, there is not really much
     to say about this topic. We can go through some classic sort
     and search examples and refer to classic texts on algorithms
     but in the  general case all you can say  is think the thing
     through  and   pick  the  best-suited  algorithm   and  data
     structure  before you  commit yourself  to writing  a lot of
     code which may become obsolete.

     Hardware Optimization

     Once again, a hard disk  or a math co-processor will improve
     performance  depending on  the nature  of your  program. But
     what more can be said?

     When to optimize, and Save the old code

     This is  not a section   in the article,  but the sentiments
     exist throughout. It  is important to get a  program working
     to specifications  first, then optimize  it (if the  project
     schedule  permits). There  are several  reasons listed below
     (some of  which have been  pointed out by  others) which can
     save many hours of frustration.

     The  first reason for not prematurely optimizing a routine
     pretty much sums up the rest:

       1) Don't optimize a routine  that that may be thrown away.
       Until  a program  is completed  you cannot  really be sure
       that a  routine will be   used unchanged -  so don't waste
       time optimizing code that may not be used.

       2) In  general, concerns about  how fast a  procedure runs
       can get in the way of  the development process. Just as it
       is  usuallly faster  to write  a program  in a  high-level
       language than  in assembler, you should  be thinking about
       solving  the problem  with a  well-structured approach and
       not burden yourself with optimization issues at this stage
       in development. There are  exceptions to this, however: If
       the problem requires say a lot  of memory or must occur in
       real  time,   it  may  be  impossible   to  abstract  from
       optimization concerns.  I would say this  is the exception
       rather than the rule, however.

       3) Optimized routines are often difficult to debug and cut
       down on code-readability.

       4) An optimized routine may not necessarily be general. If
       you  build routines  that will   end up  in libraries  for
       several programs, make sure to  keep a copy of the general
       solution before you scrap it for a speeded up version.

       Here  is  an  example  of  a  strip  of  code  that can be
       optimized:

         ...

       repeat
         BlockRead(F, Buf, SizeOf(Buf), BlocksRead);
         ...
       until BlocksRead = 0;

       Obviously,  you  can  cut  down  on  the  time it takes to
       execute  this code  by replacing  the call  to SizeOf(Buf)
       with a  constant or a  variable reference. But,  if I say,
       change  the size  of the  variable during  the development
       process, this could lead to a nasty bug if I do not change
       the  constant. I  can also   use this  routine in  several
       programs and  not worry about changing  anything. Flexible
       routines  may not  always be  the fastest  running but are
       useful in the development phase.

       5) It can  be more difficult to port  an optimized routine
       to another language or machine.  This factor is of varying
       importance to people.  But, the principle is, save  a copy
       of the slow code.


    Code Optimization

     Now that you have decided  you want to optimize your program
     (despite all  of the above  warnings), Dr. Reese  points out
     that  your time  is best   spent by  first optimizing  those
     routines where your program is spending the most time. (This
     makes a lot  of sense because the time you  have alloted for
     optimization a  project is probably  almost nil). It  is not
     always  obvious where  your program  spends its  time so you
     should  get or  write a  profiler. (Ask  for information  on
     available Turbo Pascal profilers in the online seminar).

     This  is the  most interesting   section of  the article.  I
     especially like the  examples that show you how  to optimize
     code  without  going  to  inline  code  or external assembly
     language routines.

     While  high-level programming  decisions can  have the  most
     effect on the performance of a program, code optimization is
     important, and,  best of all,  there are GENERAL  techniques
     that can  be applied to  your programs. In  this section Dr.
     Reese shows  how to optimize simple  sequences of statements
     as well as control structures  which, he points out, provide
     many opportunities  for optimization. Note, that  with these
     techniques  we are  optimizing for   speed and  much of  the
     "optimized" code  will take more  code space. So  you should
     measure  these   trade-offs  before  applying  any   of  the
     techniques to your program (don't try this at home kids).


      Simple Sequences of Programming Statements
      (this  starts   on  page  10   of  Turbo  Pascal   Advanced
      Applications in case you are reading along)

      Duplication or Effort

         A1 := B1 * C[i]*10;
         A2 := B2 * C[i]*10;

      We can cut out the duplication of C[i]*10 with:

        T := C[i] * 10;
        A1 := B1 * T;
        A2 := B2 * T;

     It seems strange that  converting two programming statements
     to three actually  saves execution time. But, let's  look at
     what we've  done: We have  converted two calculations  of an
     arithmetic  expression  to  one  calculation  and  added two
     variable  references. Since,  in this  case (and  most), the
     variable reference  takes much less processor  time than the
     calculation, we have optimized this code for speed.

     This  technique, of  course, is  not  limited  to arithmetic
     examples. Here is  a common example (at least  for me) using
     strings. It uses a function  StripExt which removes the file
     extension from a file name.

        BackFileName := StripExt(FileName) + '.BAK';
        ErrorFileName := StripExt(FileName) + '.ERR';

     We here we  are calling the function StripExt  a second time
     unnecessarily. Optimize it to this:

        RootName := StripExt(FileName);
        BackFileName := RootName + '.BAK';
        ErrorFileName := RootName + '.ERR';

     Here it is clearer why we save time with the second piece of
     code. We  have cut two calls  to a function down  to one and
     the time this saves  obviously outweighs the extra statement
     in the code.


     Reduction in Strength

     Reese's  point here  is  that  operations of  lower strength
     execute faster, so replace

      j := i * 2;

    with

     j := i + i;

     Once again, it seems a  little odd that 2 variable references
     on  the right  side of  the second  example, versus  1 in the
     first, does  not   offset  the   time  difference   of  the
     calculation, but it does.

     Another common  optimization technique alluded to  here (and
     in many  other places) is that  SHL and SHR are  faster than
     the equivalent multiplication operations.  We can go through
     some  examples and  benchmarks in  the seminar  if anyone is
     interested.

     Control Structures - Loop Constructs

     Duplication or Effort revisted

     It is plain  to see that the techniques  shown above produce
     more dramatic  results when used inside  of loop constructs,
     such  as, for,  repeat and   while loops.  Those of  you who
     looked ahead probably saw that the earlier BlockRead example
     can be optimized with the following:

         ...
       NumBytes := SizeOf(Buf);
       repeat
         BlockRead(F, Buf, NumBytes, BlocksRead);
         ...
       until BlocksRead = 0;

     We have cut down duplication of effort by moving the call to
     SizeOf outside  of the loop, or  as Dr. Reed says  "move the
     invariant computations outside the body of the loop."

     Loop unrolling

     This is an  interesting technique that I would  not think of
     doing unless I really needed to  tighten a loop. The idea is
     to cut down  on the number of branches and  comparisons in a
     loop by doing twice the work with each iteration.

     Here is the example Dr. Reese shows on page 11:

     i := 1;
     while i <= 1000 do
     begin
       Sum := Sum + A[i];
       i :=  i + 1;  { Oh come on we know that i := succ(i) is }
                     { faster by now }
     end;

     the  following  contortion  cuts  the  #  of comparisons and
     branches in half:

     i := 1;
     while i <= 1000 do
     begin
       Sum := Sum + A[i];
       Sum := Sum + A[i + 1];
       i :=  i + 2;
     end;

     In general, this would be difficult for me to do without the
     risk of bringing in incideous, off-by-one errors. But, if you
     like  this  type  of  thinking,  all  the  better. Dr. Reese
     goes on  to give more  interesting examples of  this type of
     technique.

     The Sentinel

     This  technique  is  more  to  my  liking.  It  is  used for
     searching  arrays for  a given  value. There  may be  a more
     general application  of the technique,  but in any  event, I
     like this type of thinking. Here is the code to be optimized
     (it will probably look familiar):

    BEFORE

    i := 1;
    while (A[i] <> Target) and (i <= Max) do
      i := i + 1;
    if i <= max then
      { Target Found }
    else
      { Target not found }

    AFTER

    A[0] := target;
    i := Max;
    while A[i] <> Target do
      i := i - 1;  {  How about i := pred(i)   }
    if i = 0 then
      { Target not found }
    else
      { Target found }

     The  "extra code"  here is  the check  (i <=  Max) in  every
     iteration of the while loop. To  get around this, we put the
     target  value in  the unused  0th element  of the  array (we
     change the  type declaration to   make it 0  based) and loop
     until the target is found, which is guaranteed to happen. We
     are also sure that the code will  not go out of bounds so we
     can cut our comparisons in half.

     Dr. Reese states  that for loops are faster  than repeat and
     while loops, so, I will usually hack out a different method:

    for i := 1 to Max do
      if A[i] = Target then
        Exit;

   ... in the calling routine

    if i <= max then
      { Target Found }
    else
      { Target not found }


    Control Structures - Selection statements

    These are the if and case statements (with possible GOTO's
    thrown in).  I will just mention a few of Dr. Reese's
    points:

      - Use  a case statement  rather than an  if/else when there
        are three or more choices. (Good, since this is also when
        you should use a case statement to improve readability).

      - Put selections in a case or if/else statement in the
        order of frequency you estimate they will be selected.


 Conclusion

     This  article  goes  into  many  other  techniques  that can
     improve  the performance  of a  program. However, techniques
     such  as  the  use   of:  inline  code,  external  routines,
     blockread  for file  I/O, pointers  to arrays  to save  data
     space, etc.,  have appeared in other  publications and their
     value in optimizing programs is obvious.

     I  hope Dr.  Reese's thought-provoking  article will promote
     discussion in the Online Seminar.

     "See you there!"

        Joe