198 Intermediate C Programming
f(4) f(3)
f(3) f(2) f(2) f(1)
f(2) f(1)
1 1 1
1 1
f(5)
+
+
+
+
FIGURE 13.4: Redraw Fig. 13.3. This looks like a “tree”: computing each value requires
the sum of two values.
(
f(n) = f (n − 1) + f(n − 2)
f(n − 1) = f (n − 2) + f (n − 3)
(13.4)
Therefore,
f(n) = f(n − 1) + f(n − 2)
= (f(n − 2) + f(n − 3)) + f(n − 2)
= 2f(n − 2) + f(n − 3).
(13.5)
Continuing this derivation for a few more steps we have:
f(n) = f(n − 1) + f (n − 2)
= 2f(n − 2) + f (n − 3)
= 2(f(n − 3) + f(n − 4)) + f (n − 3)
= 3f(n − 3) + 2f (n − 4)
= 3(f(n − 4) + f(n − 5)) + 2f (n − 4)
= 5f(n − 4) + 3f (n − 5)
= 5(f(n − 5) + f(n − 6)) + 3f (n − 5)
= 8f(n − 5) + 5f (n − 6)
= 8(f(n − 6) + f(n − 7)) + 5f (n − 6)
= 13f(n − 6) + 8f(n − 7).
(13.6)
Table 13.2 lists the coefficients for computing f(n). When comparing this table with
the values in Table 13.1, you may find that the coefficient of f (n − k) is actually f (k + 1).
Table 13.2 and Fig. 13.4 both express similar concepts. Fig. 13.4 computes f (5) so n is 5
and f (2) is f(n − 3). The coefficient for f(n − 3) is 3. If we count the occurrences of f (2)
in Fig. 13.4, we find that it is called three times.
The recursive method for calculating Fibonacci numbers is slower because it computes
the same value over and over again. When computing f (n − 1), it has to compute f(n − 2).
However, the recursive function in Section 13.6 does not remember the value for f(n − 2)
and then computes the value again later. As n becomes larger, the function performs more
and more redundant computations and becomes slower and slower. It is unclear why many
books use Fibonacci numbers to motivate the concept of recursion.
Recursive C Functions 199
function coefficient
f(n-1) 1 f(2)
f(n-2) 2 f(3)
f(n-3) 3 f(4)
f(n-4) 5 f(5)
f(n-5) 8 f(6)
f(n-6) 13 f(7)
TABLE 13.2: Coefficients for computing f (n).
Does this mean recursion is bad? Does this mean that recursion is slow? Why should we
even bother to learn recursion? The problem is not recursion, but the example. We cannot
generalize from a bad example to say that recursion is slow. Recursion can be used to good
advantage in some time-critical applications. If you have a nail and a knife, you will find
that hitting the nail with a knife is difficult. Does this mean a knife is bad? If you need to
hit a nail, you need a hammer. A knife is a bad tool for hitting a nail. If you want to cut
paper, a knife is better than a hammer. If you have a bolt, you need a wrench. A hammer
is not better than a wrench and a wrench is not better than a hammer. They are different.
One is better than the other in some scenarios. If a book tells you a hammer is better
than a wrench, you will say, “This doesn’t make sense. In some cases, a wrench is better.”
You cannot generalize this example and conclude that recursion is slower. Some books do
not explain that this particular top-down method is slower than this bottom-up method.
As a result some students mistakenly think recursion is slow by generalizing this example.
Some other books explain that this top-down method is slower than this bottom-up method
without further explanation. These books give students the strong impression that recursion
is slow. The truth is that recursion is a good approach for some problems, not all.
13.7 Performance Profiling with gprof
Many studies on software performance find that performance is generally dominated
by just a few factors. This is true for both simple and complex systems. A general rule of
thumb is “10% of the code consumes 90% of the time”. Improving the correct 10% of code
will have a noticeable impact on performance. Conversely, improving the other 90% of code
will have negligible impact. The question is how to find the 10% of interest. Guessing is not
a good approach. Even experienced programmers find it very hard to predict which parts
of a complex program cause performance bottlenecks.
Experienced programmers know that tools can help identify that 10% of the code. A
tool called gprof is designed specifically for this purpose. To use gprof, add -pg after gcc
and execute the program as usual. For example:
$ gcc -Wall -Wshadow -pg fib.c fib1.c fib2.c -o fibprog
Consider the Fibonacci functions referenced earlier. After running the program, a special
file called gmon.out is generated. This file stores the profiling information for running the
program and it is not readable using a text editor. Please use the gprof program to view
the content in gmon.out. The command is:
200 Intermediate C Programming
$ gprof fibprog
The output is something like this:
Flat p r o fi l e :
Each sample counts as 0.01 seconds .
% cumulat ive self self total
time seconds seconds calls us / call us / call name
92.23 8.89 8.89 2000000 4.45 4.45 fib
7.52 9.62 0.72
frame_ dummy
0.84 9.70 0.08 20 0 0 0 0 0 0.04 0.04 fib2
0.10 9.71 0.01 main
granul arity : each sample hit covers 2 byte ( s) f o r 0.10% of
9.71 s e con d s
index % time self children called name
< spontaneous >
[1] 92.5 0.01 8.97 main [1]
8.89 0.00 2 0 00000 /20000 00 fib [2]
0.08 0.00 2 0 00000 /20000 00 fib2 [4]
-- - --- --- --- --- --- --- - --- --- --- --- --- --- - --- ---
3538000 0 00 fib [2]
8.89 0.00 2 0 00000 /20000 00 main [1]
[2] 91.6 8.89 0.00 2 0 0000 0 +353 8 00000 0 fib [2]
3538000 0 00 fib [2]
-- - --- --- --- --- --- --- - --- --- --- --- --- --- - --- ---
< spontaneous >
[3] 7.5 0.72 0.00 f rame_dumm y [3]
-- - --- --- --- --- --- --- - --- --- --- --- --- --- - --- ---
0.08 0.00 2 0 00000 /20000 00 main [1]
[4] 0.8 0.08 0.00 2000000 fib2 [4]
-- - --- --- --- --- --- --- - --- --- --- --- --- --- - --- ---
This output says that 92.23% of the time is spent on the function fib and only 0.84%
time is spent on the function fib2. The main function calls fib 2000000 times (REPEAT ×
MAXN). In [2], the report says that fib is called itself 3538000000 times. In contrast, [4] says
that fib2 is called 2000000 times and it does not call itself.
How can we use this information to help identify the opportunities for improving perfor-
mance? First, the report says more than 90% time is spent on fib. This suggests that the
function should be carefully inspected for better performance. Second, the report says that
main calls fib 2000000 and fib calls itself 3538000000 times, much more than the 2000000
invocations by main. This also suggests that fib calls itself excessively and is a candidate
for performance improvement.
In this example, the program requires no inputs. Complex programs usually accept
inputs that specify the programs’ actions. Profiling a program effectively often requires
using representative inputs. If a particular line of code is not executed for a particular set
of inputs, gprof will contain no information about that line. Moreover, gprof is sampling
based. The top of the report says that the sampling rate is 0.01 seconds. If the execution
time of a program is too short, gprof will not be able to give accurate results.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.