1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> 2<html> 3<!-- This file documents the gprof profiler of the GNU system. 4 5Copyright (C) 1988-2021 Free Software Foundation, Inc. 6 7Permission is granted to copy, distribute and/or modify this document 8under the terms of the GNU Free Documentation License, Version 1.3 9or any later version published by the Free Software Foundation; 10with no Invariant Sections, with no Front-Cover Texts, and with no 11Back-Cover Texts. A copy of the license is included in the 12section entitled "GNU Free Documentation License". 13 --> 14<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ --> 15<head> 16<title>GNU gprof: Cycles</title> 17 18<meta name="description" content="GNU gprof: Cycles"> 19<meta name="keywords" content="GNU gprof: Cycles"> 20<meta name="resource-type" content="document"> 21<meta name="distribution" content="global"> 22<meta name="Generator" content="makeinfo"> 23<meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 24<link href="index.html#Top" rel="start" title="Top"> 25<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents"> 26<link href="Call-Graph.html#Call-Graph" rel="up" title="Call Graph"> 27<link href="Line_002dby_002dline.html#Line_002dby_002dline" rel="next" title="Line-by-line"> 28<link href="Subroutines.html#Subroutines" rel="previous" title="Subroutines"> 29<style type="text/css"> 30<!-- 31a.summary-letter {text-decoration: none} 32blockquote.smallquotation {font-size: smaller} 33div.display {margin-left: 3.2em} 34div.example {margin-left: 3.2em} 35div.indentedblock {margin-left: 3.2em} 36div.lisp {margin-left: 3.2em} 37div.smalldisplay {margin-left: 3.2em} 38div.smallexample {margin-left: 3.2em} 39div.smallindentedblock {margin-left: 3.2em; font-size: smaller} 40div.smalllisp {margin-left: 3.2em} 41kbd {font-style:oblique} 42pre.display {font-family: inherit} 43pre.format {font-family: inherit} 44pre.menu-comment {font-family: serif} 45pre.menu-preformatted {font-family: serif} 46pre.smalldisplay {font-family: inherit; font-size: smaller} 47pre.smallexample {font-size: smaller} 48pre.smallformat {font-family: inherit; font-size: smaller} 49pre.smalllisp {font-size: smaller} 50span.nocodebreak {white-space:nowrap} 51span.nolinebreak {white-space:nowrap} 52span.roman {font-family:serif; font-weight:normal} 53span.sansserif {font-family:sans-serif; font-weight:normal} 54ul.no-bullet {list-style: none} 55--> 56</style> 57 58 59</head> 60 61<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000"> 62<a name="Cycles"></a> 63<div class="header"> 64<p> 65Previous: <a href="Subroutines.html#Subroutines" accesskey="p" rel="previous">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> 66</div> 67<hr> 68<a name="How-Mutually-Recursive-Functions-Are-Described"></a> 69<h4 class="subsection">5.2.4 How Mutually Recursive Functions Are Described</h4> 70<a name="index-cycle"></a> 71<a name="index-recursion-cycle"></a> 72 73<p>The graph may be complicated by the presence of <em>cycles of 74recursion</em> in the call graph. A cycle exists if a function calls 75another function that (directly or indirectly) calls (or appears to 76call) the original function. For example: if <code>a</code> calls <code>b</code>, 77and <code>b</code> calls <code>a</code>, then <code>a</code> and <code>b</code> form a cycle. 78</p> 79<p>Whenever there are call paths both ways between a pair of functions, they 80belong to the same cycle. If <code>a</code> and <code>b</code> call each other and 81<code>b</code> and <code>c</code> call each other, all three make one cycle. Note that 82even if <code>b</code> only calls <code>a</code> if it was not called from <code>a</code>, 83<code>gprof</code> cannot determine this, so <code>a</code> and <code>b</code> are still 84considered a cycle. 85</p> 86<p>The cycles are numbered with consecutive integers. When a function 87belongs to a cycle, each time the function name appears in the call graph 88it is followed by ‘<samp><cycle <var>number</var>></samp>’. 89</p> 90<p>The reason cycles matter is that they make the time values in the call 91graph paradoxical. The “time spent in children” of <code>a</code> should 92include the time spent in its subroutine <code>b</code> and in <code>b</code>’s 93subroutines—but one of <code>b</code>’s subroutines is <code>a</code>! How much of 94<code>a</code>’s time should be included in the children of <code>a</code>, when 95<code>a</code> is indirectly recursive? 96</p> 97<p>The way <code>gprof</code> resolves this paradox is by creating a single entry 98for the cycle as a whole. The primary line of this entry describes the 99total time spent directly in the functions of the cycle. The 100“subroutines” of the cycle are the individual functions of the cycle, and 101all other functions that were called directly by them. The “callers” of 102the cycle are the functions, outside the cycle, that called functions in 103the cycle. 104</p> 105<p>Here is an example portion of a call graph which shows a cycle containing 106functions <code>a</code> and <code>b</code>. The cycle was entered by a call to 107<code>a</code> from <code>main</code>; both <code>a</code> and <code>b</code> called <code>c</code>. 108</p> 109<div class="smallexample"> 110<pre class="smallexample">index % time self children called name 111---------------------------------------- 112 1.77 0 1/1 main [2] 113[3] 91.71 1.77 0 1+5 <cycle 1 as a whole> [3] 114 1.02 0 3 b <cycle 1> [4] 115 0.75 0 2 a <cycle 1> [5] 116---------------------------------------- 117 3 a <cycle 1> [5] 118[4] 52.85 1.02 0 0 b <cycle 1> [4] 119 2 a <cycle 1> [5] 120 0 0 3/6 c [6] 121---------------------------------------- 122 1.77 0 1/1 main [2] 123 2 b <cycle 1> [4] 124[5] 38.86 0.75 0 1 a <cycle 1> [5] 125 3 b <cycle 1> [4] 126 0 0 3/6 c [6] 127---------------------------------------- 128</pre></div> 129 130<p>(The entire call graph for this program contains in addition an entry for 131<code>main</code>, which calls <code>a</code>, and an entry for <code>c</code>, with callers 132<code>a</code> and <code>b</code>.) 133</p> 134<div class="smallexample"> 135<pre class="smallexample">index % time self children called name 136 <spontaneous> 137[1] 100.00 0 1.93 0 start [1] 138 0.16 1.77 1/1 main [2] 139---------------------------------------- 140 0.16 1.77 1/1 start [1] 141[2] 100.00 0.16 1.77 1 main [2] 142 1.77 0 1/1 a <cycle 1> [5] 143---------------------------------------- 144 1.77 0 1/1 main [2] 145[3] 91.71 1.77 0 1+5 <cycle 1 as a whole> [3] 146 1.02 0 3 b <cycle 1> [4] 147 0.75 0 2 a <cycle 1> [5] 148 0 0 6/6 c [6] 149---------------------------------------- 150 3 a <cycle 1> [5] 151[4] 52.85 1.02 0 0 b <cycle 1> [4] 152 2 a <cycle 1> [5] 153 0 0 3/6 c [6] 154---------------------------------------- 155 1.77 0 1/1 main [2] 156 2 b <cycle 1> [4] 157[5] 38.86 0.75 0 1 a <cycle 1> [5] 158 3 b <cycle 1> [4] 159 0 0 3/6 c [6] 160---------------------------------------- 161 0 0 3/6 b <cycle 1> [4] 162 0 0 3/6 a <cycle 1> [5] 163[6] 0.00 0 0 6 c [6] 164---------------------------------------- 165</pre></div> 166 167<p>The <code>self</code> field of the cycle’s primary line is the total time 168spent in all the functions of the cycle. It equals the sum of the 169<code>self</code> fields for the individual functions in the cycle, found 170in the entry in the subroutine lines for these functions. 171</p> 172<p>The <code>children</code> fields of the cycle’s primary line and subroutine lines 173count only subroutines outside the cycle. Even though <code>a</code> calls 174<code>b</code>, the time spent in those calls to <code>b</code> is not counted in 175<code>a</code>’s <code>children</code> time. Thus, we do not encounter the problem of 176what to do when the time in those calls to <code>b</code> includes indirect 177recursive calls back to <code>a</code>. 178</p> 179<p>The <code>children</code> field of a caller-line in the cycle’s entry estimates 180the amount of time spent <em>in the whole cycle</em>, and its other 181subroutines, on the times when that caller called a function in the cycle. 182</p> 183<p>The <code>called</code> field in the primary line for the cycle has two numbers: 184first, the number of times functions in the cycle were called by functions 185outside the cycle; second, the number of times they were called by 186functions in the cycle (including times when a function in the cycle calls 187itself). This is a generalization of the usual split into non-recursive and 188recursive calls. 189</p> 190<p>The <code>called</code> field of a subroutine-line for a cycle member in the 191cycle’s entry says how many time that function was called from functions in 192the cycle. The total of all these is the second number in the primary line’s 193<code>called</code> field. 194</p> 195<p>In the individual entry for a function in a cycle, the other functions in 196the same cycle can appear as subroutines and as callers. These lines show 197how many times each function in the cycle called or was called from each other 198function in the cycle. The <code>self</code> and <code>children</code> fields in these 199lines are blank because of the difficulty of defining meanings for them 200when recursion is going on. 201</p> 202<hr> 203<div class="header"> 204<p> 205Previous: <a href="Subroutines.html#Subroutines" accesskey="p" rel="previous">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> 206</div> 207 208 209 210</body> 211</html> 212