17.9 How to Optimize

Our matrix initialization function illustrates several optimizing strategies. These are:

Removing invariant code

Code that does not need to be put inside a loop should be put outside the loop. For example:

for (i = 0; i < 10; ++i) 
     matrix[i] = i + j * 10;

can be written as:

j_times_10 = j * 10;
for (i = 0; i < 10; ++i)
    matrix[i] = i + j_times_10;
for (i = 0; i < 10; ++i)

Most good optimizing compilers will do this work for you if possible.

Loop ordering

Nested loops should be ordered with the simplest loop outermost and the most complex loops innermost.

Reference parameters

Use constant reference parameters (const type&) instead of constant parameters for structures, unions, and classes.

Powers of two

Use a power of two when doing integer multiply or divide. Most compilers will substitute a shift for the operation.

Pointers

Using pointers to go through an array is generally faster using an index, but pointers are more tricky to use.

Inline functions

Using inline functions eliminates the overhead associated with a function call. It also can make the code bigger and a little more difficult to debug. (See the case study below.)

Reduction in strength

This is a fancy way of saying use cheap operations instead of expensive ones. Table 17-1 lists the relative cost of common operations.

Table 17-1. Relative cost of operations

Operation	Relative cost
File input and output (<< and >>), including the C functions printf and scanf	1,000
new and delete	800
Trigonometric functions (sin, cos, ...)	500
Floating point (any operation)	100
Integer divide	30
Integer multiply	20
Function call	10
assert[2]	8
Simple array index	6
Shifts	5
Add/subtract	5
Pointer dereference	2
Bitwise AND, OR, NOT	1
Logical AND, OR, NOT	1

^[2] The assert statement can be removed by using the compile time option -DNDEBUG. However, these statements should be removed with care, as they provide insurance against bad things happening in your program. Sometimes the fastest way is not the best.

The C++ I/O system and the C formatting functions called using std::scanf, std::printf, and std::sscanf are extremely costly because they have to go through the format string one character at a time looking for a format conversion character (%). They then have to do a costly conversion between a character string and a number. These functions should be avoided in time-critical sections of code.