<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
<html>
|
<!-- This file documents the gprof profiler of the GNU system.
|
|
Copyright (C) 1988-2016 Free Software Foundation, Inc.
|
|
Permission is granted to copy, distribute and/or modify this document
|
under the terms of the GNU Free Documentation License, Version 1.3
|
or any later version published by the Free Software Foundation;
|
with no Invariant Sections, with no Front-Cover Texts, and with no
|
Back-Cover Texts. A copy of the license is included in the
|
section entitled "GNU Free Documentation License".
|
-->
|
<!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
|
<head>
|
<title>GNU gprof: Cycles</title>
|
|
<meta name="description" content="GNU gprof: Cycles">
|
<meta name="keywords" content="GNU gprof: Cycles">
|
<meta name="resource-type" content="document">
|
<meta name="distribution" content="global">
|
<meta name="Generator" content="makeinfo">
|
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
|
<link href="index.html#Top" rel="start" title="Top">
|
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
|
<link href="Call-Graph.html#Call-Graph" rel="up" title="Call Graph">
|
<link href="Line_002dby_002dline.html#Line_002dby_002dline" rel="next" title="Line-by-line">
|
<link href="Subroutines.html#Subroutines" rel="prev" title="Subroutines">
|
<style type="text/css">
|
<!--
|
a.summary-letter {text-decoration: none}
|
blockquote.smallquotation {font-size: smaller}
|
div.display {margin-left: 3.2em}
|
div.example {margin-left: 3.2em}
|
div.indentedblock {margin-left: 3.2em}
|
div.lisp {margin-left: 3.2em}
|
div.smalldisplay {margin-left: 3.2em}
|
div.smallexample {margin-left: 3.2em}
|
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
|
div.smalllisp {margin-left: 3.2em}
|
kbd {font-style:oblique}
|
pre.display {font-family: inherit}
|
pre.format {font-family: inherit}
|
pre.menu-comment {font-family: serif}
|
pre.menu-preformatted {font-family: serif}
|
pre.smalldisplay {font-family: inherit; font-size: smaller}
|
pre.smallexample {font-size: smaller}
|
pre.smallformat {font-family: inherit; font-size: smaller}
|
pre.smalllisp {font-size: smaller}
|
span.nocodebreak {white-space:nowrap}
|
span.nolinebreak {white-space:nowrap}
|
span.roman {font-family:serif; font-weight:normal}
|
span.sansserif {font-family:sans-serif; font-weight:normal}
|
ul.no-bullet {list-style: none}
|
-->
|
</style>
|
|
|
</head>
|
|
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
|
<a name="Cycles"></a>
|
<div class="header">
|
<p>
|
Previous: <a href="Subroutines.html#Subroutines" accesskey="p" rel="prev">Subroutines</a>, Up: <a href="Call-Graph.html#Call-Graph" accesskey="u" rel="up">Call Graph</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>]</p>
|
</div>
|
<hr>
|
<a name="How-Mutually-Recursive-Functions-Are-Described"></a>
|
<h4 class="subsection">5.2.4 How Mutually Recursive Functions Are Described</h4>
|
<a name="index-cycle"></a>
|
<a name="index-recursion-cycle"></a>
|
|
<p>The graph may be complicated by the presence of <em>cycles of
|
recursion</em> 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 <code>a</code> calls <code>b</code>,
|
and <code>b</code> calls <code>a</code>, then <code>a</code> and <code>b</code> form a cycle.
|
</p>
|
<p>Whenever there are call paths both ways between a pair of functions, they
|
belong to the same cycle. If <code>a</code> and <code>b</code> call each other and
|
<code>b</code> and <code>c</code> call each other, all three make one cycle. Note that
|
even if <code>b</code> only calls <code>a</code> if it was not called from <code>a</code>,
|
<code>gprof</code> cannot determine this, so <code>a</code> and <code>b</code> are still
|
considered a cycle.
|
</p>
|
<p>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 ‘<samp><cycle <var>number</var>></samp>’.
|
</p>
|
<p>The reason cycles matter is that they make the time values in the call
|
graph paradoxical. The “time spent in children” of <code>a</code> should
|
include the time spent in its subroutine <code>b</code> and in <code>b</code>’s
|
subroutines—but one of <code>b</code>’s subroutines is <code>a</code>! How much of
|
<code>a</code>’s time should be included in the children of <code>a</code>, when
|
<code>a</code> is indirectly recursive?
|
</p>
|
<p>The way <code>gprof</code> 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.
|
</p>
|
<p>Here is an example portion of a call graph which shows a cycle containing
|
functions <code>a</code> and <code>b</code>. The cycle was entered by a call to
|
<code>a</code> from <code>main</code>; both <code>a</code> and <code>b</code> called <code>c</code>.
|
</p>
|
<div class="smallexample">
|
<pre class="smallexample">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]
|
----------------------------------------
|
</pre></div>
|
|
<p>(The entire call graph for this program contains in addition an entry for
|
<code>main</code>, which calls <code>a</code>, and an entry for <code>c</code>, with callers
|
<code>a</code> and <code>b</code>.)
|
</p>
|
<div class="smallexample">
|
<pre class="smallexample">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]
|
----------------------------------------
|
</pre></div>
|
|
<p>The <code>self</code> 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
|
<code>self</code> fields for the individual functions in the cycle, found
|
in the entry in the subroutine lines for these functions.
|
</p>
|
<p>The <code>children</code> fields of the cycle’s primary line and subroutine lines
|
count only subroutines outside the cycle. Even though <code>a</code> calls
|
<code>b</code>, the time spent in those calls to <code>b</code> is not counted in
|
<code>a</code>’s <code>children</code> time. Thus, we do not encounter the problem of
|
what to do when the time in those calls to <code>b</code> includes indirect
|
recursive calls back to <code>a</code>.
|
</p>
|
<p>The <code>children</code> field of a caller-line in the cycle’s entry estimates
|
the amount of time spent <em>in the whole cycle</em>, and its other
|
subroutines, on the times when that caller called a function in the cycle.
|
</p>
|
<p>The <code>called</code> 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.
|
</p>
|
<p>The <code>called</code> 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
|
<code>called</code> field.
|
</p>
|
<p>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 <code>self</code> and <code>children</code> fields in these
|
lines are blank because of the difficulty of defining meanings for them
|
when recursion is going on.
|
</p>
|
<hr>
|
<div class="header">
|
<p>
|
Previous: <a href="Subroutines.html#Subroutines" accesskey="p" rel="prev">Subroutines</a>, Up: <a href="Call-Graph.html#Call-Graph" accesskey="u" rel="up">Call Graph</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>]</p>
|
</div>
|
|
|
|
</body>
|
</html>
|
