Information Technology Reference
In-Depth Information
When performing a single numerical integration of a function
f.x/
with a “rea-
sonable”
n
, the computations will, on today's machines, be so fast and use so little
memory that this latter optimization has no practical advantage; you get the answer
immediately anyway. In fact, rewriting from (6.1)to(6.2) and then to Algorithm
6.2
just increases the probability of introducing errors. Nevertheless, if this integration
is used inside a huge scientific computing code and is called billions of times, even
a small speed improvement may be significant.
Example 6.1.
The payoff of the optimization depends heavily on the function
f.x/
.
If
f.x/
is complicated, say, an evaluation of
f
requires 100 multiplications (which
is relevant when
f
contains fundamental functions such as sin and log), saving a
multiplication by
h
can only improve the speed by 1%. To be specific, we tried to
integrate
f
1
.x/ D e
x
2
log
.1 C x
sin
x/
and
f
2
.x/ D 1 C x
from
a D 0
to
b D 2
with
n D 1;000
, repeated 10,000 times. In Fortran 77 imple-
mentations of Algorithms
6.1
and
6.2
there were no differences between the two
versions of the algorithms when integrating
f
1
.x/
. Even with
f
2
.x/
, Algorithm
6.2
was only slightly faster than Algorithms
6.1
. On the other hand, the total execution
time increased by a factor of 10 when we switched from the simple
f
2
function to
the more complicated
f
1
function.
Rely on Compiler Optimization Technology
Why was the benefit of our hand optimizations so small in the previous example?
Administering the loop
i D 1;:::;n 1
and calling a function are expensive oper-
ations in computer programs, so saving a couple of multiplications inside a loop
can drown in other tasks. Nevertheless, a much more important explanation why the
benefit was so small has to do with compiler optimization technology. We turned
on the maximum optimization of the GNU Fortran 77 compiler when compiling the
codes corresponding to Algorithms
6.1
and
6.2
. The Fortran compiler has 50 years
of experience with optimizing loops involving mathematical expressions. Loops of
the very simple type encountered in the present example can probably be analyzed
to the fullest extent by most compilers. This means that the compiler will detect
when we perform unnecessary multiplications by
h
. The compiler will probably
also see that the function evaluation
f.aC
ih
/
can be optimized, as we did by
hand. These assertions are supported by compiling the codes without optimization;
the CPU times
4
of Algorithms
6.1
and
6.2
differed by a factor of almost 2, when
integrating
f
2
. Negligible differences arose when integrating
f
1
, since the function
evaluations dominate in this case.
