8.3 Issues in Optimization

The most important optimization principle is correctness. The meaning of a program can't be changed:

The task is to find frequently occurring code sequences, perform improvements to them, and forget the rest.

Sometimes the questions are asked: Why optimize? Can't programmers just be taught to write good code? The answer is (rarely) yes . For large programs which execute for many hours or days, programmers do rewrite them to make them as efficient as possible. The more common answer, however, is no. Programmers should be able to use the features of a language to implement an algorithm without worrying about its efficiency. They should be optimizing for readability and maintainability. Example 1 shows a common case

EXAMPLE 1 Two-dimensional arrays
	LOOP
	  A[I,J] := . . .
	  . . .
	  . . .
	   := A[I,J]
	  . . .
	ENDLOOP

An optimizing compiler is expected to optimize the high-level features.

Optimizations optimize most frequently for time. This is represented, syntactically (that is, it can be seen by looking at the code), by minimization of the number of operations and minimization of the number of memory accesses. Operations can be computed faster if their operands are in registers. Constants can be computed at compile-time.

Optimizations optimize next most frequently for space . Minimizing memory accesses may produce a smaller amount of code as well as code that executes faster since most machine code requires more bytes to reference memory.

There are also space-time tradeoffs. For example, replacing two instances of the same code by a subroutine may save code space, but takes more time because of the overhead of jumping to the subroutine, passing arguments and returning from the subroutine.

An optimization should speed up a program by a measurable amount. Also, we don't optimize in heavy debugging environments (student environments are heavy debugging environments). It takes too much compiler time for environments where a program is compiled many times (until it is correct) and run once or twice.

On the other hand, as we shall see, certain so-called peephole optimizations are so easy that they should be done by all compilers.

Send questions and comments to: Karen Lemone