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