| <!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, 1992, 1997, 1998, 1999, 2000, 2001, 2003, |
| 2007, 2008, 2009 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> |
