GNU Info
(gprof.info)Cycles
How Mutually Recursive Functions Are Described
----------------------------------------------
The graph may be complicated by the presence of "cycles of
recursion" in the call graph. A cycle exists if a function calls
another function that (directly or indirectly) calls (or appears to
call) the original function. For example: if `a' calls `b', and `b'
calls `a', then `a' and `b' form a cycle.
Whenever there are call paths both ways between a pair of functions,
they belong to the same cycle. If `a' and `b' call each other and `b'
and `c' call each other, all three make one cycle. Note that even if
`b' only calls `a' if it was not called from `a', `gprof' cannot
determine this, so `a' and `b' are still considered a cycle.
The cycles are numbered with consecutive integers. When a function
belongs to a cycle, each time the function name appears in the call
graph it is followed by `<cycle NUMBER>'.
The reason cycles matter is that they make the time values in the
call graph paradoxical. The "time spent in children" of `a' should
include the time spent in its subroutine `b' and in `b''s
subroutines--but one of `b''s subroutines is `a'! How much of `a''s
time should be included in the children of `a', when `a' is indirectly
recursive?
The way `gprof' resolves this paradox is by creating a single entry
for the cycle as a whole. The primary line of this entry describes the
total time spent directly in the functions of the cycle. The
"subroutines" of the cycle are the individual functions of the cycle,
and all other functions that were called directly by them. The
"callers" of the cycle are the functions, outside the cycle, that
called functions in the cycle.
Here is an example portion of a call graph which shows a cycle
containing functions `a' and `b'. The cycle was entered by a call to
`a' from `main'; both `a' and `b' called `c'.
index % time self children called name
----------------------------------------
1.77 0 1/1 main [2]
[3] 91.71 1.77 0 1+5 <cycle 1 as a whole> [3]
1.02 0 3 b <cycle 1> [4]
0.75 0 2 a <cycle 1> [5]
----------------------------------------
3 a <cycle 1> [5]
[4] 52.85 1.02 0 0 b <cycle 1> [4]
2 a <cycle 1> [5]
0 0 3/6 c [6]
----------------------------------------
1.77 0 1/1 main [2]
2 b <cycle 1> [4]
[5] 38.86 0.75 0 1 a <cycle 1> [5]
3 b <cycle 1> [4]
0 0 3/6 c [6]
----------------------------------------
(The entire call graph for this program contains in addition an entry
for `main', which calls `a', and an entry for `c', with callers `a' and
`b'.)
index % time self children called name
<spontaneous>
[1] 100.00 0 1.93 0 start [1]
0.16 1.77 1/1 main [2]
----------------------------------------
0.16 1.77 1/1 start [1]
[2] 100.00 0.16 1.77 1 main [2]
1.77 0 1/1 a <cycle 1> [5]
----------------------------------------
1.77 0 1/1 main [2]
[3] 91.71 1.77 0 1+5 <cycle 1 as a whole> [3]
1.02 0 3 b <cycle 1> [4]
0.75 0 2 a <cycle 1> [5]
0 0 6/6 c [6]
----------------------------------------
3 a <cycle 1> [5]
[4] 52.85 1.02 0 0 b <cycle 1> [4]
2 a <cycle 1> [5]
0 0 3/6 c [6]
----------------------------------------
1.77 0 1/1 main [2]
2 b <cycle 1> [4]
[5] 38.86 0.75 0 1 a <cycle 1> [5]
3 b <cycle 1> [4]
0 0 3/6 c [6]
----------------------------------------
0 0 3/6 b <cycle 1> [4]
0 0 3/6 a <cycle 1> [5]
[6] 0.00 0 0 6 c [6]
----------------------------------------
The `self' field of the cycle's primary line is the total time spent
in all the functions of the cycle. It equals the sum of the `self'
fields for the individual functions in the cycle, found in the entry in
the subroutine lines for these functions.
The `children' fields of the cycle's primary line and subroutine
lines count only subroutines outside the cycle. Even though `a' calls
`b', the time spent in those calls to `b' is not counted in `a''s
`children' time. Thus, we do not encounter the problem of what to do
when the time in those calls to `b' includes indirect recursive calls
back to `a'.
The `children' field of a caller-line in the cycle's entry estimates
the amount of time spent _in the whole cycle_, and its other
subroutines, on the times when that caller called a function in the
cycle.
The `calls' field in the primary line for the cycle has two numbers:
first, the number of times functions in the cycle were called by
functions outside the cycle; second, the number of times they were
called by functions in the cycle (including times when a function in
the cycle calls itself). This is a generalization of the usual split
into non-recursive and recursive calls.
The `calls' field of a subroutine-line for a cycle member in the
cycle's entry says how many time that function was called from
functions in the cycle. The total of all these is the second number in
the primary line's `calls' field.
In the individual entry for a function in a cycle, the other
functions in the same cycle can appear as subroutines and as callers.
These lines show how many times each function in the cycle called or
was called from each other function in the cycle. The `self' and
`children' fields in these lines are blank because of the difficulty of
defining meanings for them when recursion is going on.
automatically generated by info2www version 1.2.2.9