1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> 4<title>5.�Cachegrind: a cache and branch-prediction profiler</title> 5<link rel="stylesheet" type="text/css" href="vg_basic.css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="index.html" title="Valgrind Documentation"> 8<link rel="up" href="manual.html" title="Valgrind User Manual"> 9<link rel="prev" href="mc-manual.html" title="4.�Memcheck: a memory error detector"> 10<link rel="next" href="cl-manual.html" title="6.�Callgrind: a call-graph generating cache and branch prediction profiler"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<div><table class="nav" width="100%" cellspacing="3" cellpadding="3" border="0" summary="Navigation header"><tr> 14<td width="22px" align="center" valign="middle"><a accesskey="p" href="mc-manual.html"><img src="images/prev.png" width="18" height="21" border="0" alt="Prev"></a></td> 15<td width="25px" align="center" valign="middle"><a accesskey="u" href="manual.html"><img src="images/up.png" width="21" height="18" border="0" alt="Up"></a></td> 16<td width="31px" align="center" valign="middle"><a accesskey="h" href="index.html"><img src="images/home.png" width="27" height="20" border="0" alt="Up"></a></td> 17<th align="center" valign="middle">Valgrind User Manual</th> 18<td width="22px" align="center" valign="middle"><a accesskey="n" href="cl-manual.html"><img src="images/next.png" width="18" height="21" border="0" alt="Next"></a></td> 19</tr></table></div> 20<div class="chapter"> 21<div class="titlepage"><div><div><h1 class="title"> 22<a name="cg-manual"></a>5.�Cachegrind: a cache and branch-prediction profiler</h1></div></div></div> 23<div class="toc"> 24<p><b>Table of Contents</b></p> 25<dl class="toc"> 26<dt><span class="sect1"><a href="cg-manual.html#cg-manual.overview">5.1. Overview</a></span></dt> 27<dt><span class="sect1"><a href="cg-manual.html#cg-manual.profile">5.2. Using Cachegrind, cg_annotate and cg_merge</a></span></dt> 28<dd><dl> 29<dt><span class="sect2"><a href="cg-manual.html#cg-manual.running-cachegrind">5.2.1. Running Cachegrind</a></span></dt> 30<dt><span class="sect2"><a href="cg-manual.html#cg-manual.outputfile">5.2.2. Output File</a></span></dt> 31<dt><span class="sect2"><a href="cg-manual.html#cg-manual.running-cg_annotate">5.2.3. Running cg_annotate</a></span></dt> 32<dt><span class="sect2"><a href="cg-manual.html#cg-manual.the-output-preamble">5.2.4. The Output Preamble</a></span></dt> 33<dt><span class="sect2"><a href="cg-manual.html#cg-manual.the-global">5.2.5. The Global and Function-level Counts</a></span></dt> 34<dt><span class="sect2"><a href="cg-manual.html#cg-manual.line-by-line">5.2.6. Line-by-line Counts</a></span></dt> 35<dt><span class="sect2"><a href="cg-manual.html#cg-manual.assembler">5.2.7. Annotating Assembly Code Programs</a></span></dt> 36<dt><span class="sect2"><a href="cg-manual.html#ms-manual.forkingprograms">5.2.8. Forking Programs</a></span></dt> 37<dt><span class="sect2"><a href="cg-manual.html#cg-manual.annopts.warnings">5.2.9. cg_annotate Warnings</a></span></dt> 38<dt><span class="sect2"><a href="cg-manual.html#cg-manual.annopts.things-to-watch-out-for">5.2.10. Unusual Annotation Cases</a></span></dt> 39<dt><span class="sect2"><a href="cg-manual.html#cg-manual.cg_merge">5.2.11. Merging Profiles with cg_merge</a></span></dt> 40<dt><span class="sect2"><a href="cg-manual.html#cg-manual.cg_diff">5.2.12. Differencing Profiles with cg_diff</a></span></dt> 41</dl></dd> 42<dt><span class="sect1"><a href="cg-manual.html#cg-manual.cgopts">5.3. Cachegrind Command-line Options</a></span></dt> 43<dt><span class="sect1"><a href="cg-manual.html#cg-manual.annopts">5.4. cg_annotate Command-line Options</a></span></dt> 44<dt><span class="sect1"><a href="cg-manual.html#cg-manual.mergeopts">5.5. cg_merge Command-line Options</a></span></dt> 45<dt><span class="sect1"><a href="cg-manual.html#cg-manual.diffopts">5.6. cg_diff Command-line Options</a></span></dt> 46<dt><span class="sect1"><a href="cg-manual.html#cg-manual.acting-on">5.7. Acting on Cachegrind's Information</a></span></dt> 47<dt><span class="sect1"><a href="cg-manual.html#cg-manual.sim-details">5.8. Simulation Details</a></span></dt> 48<dd><dl> 49<dt><span class="sect2"><a href="cg-manual.html#cache-sim">5.8.1. Cache Simulation Specifics</a></span></dt> 50<dt><span class="sect2"><a href="cg-manual.html#branch-sim">5.8.2. Branch Simulation Specifics</a></span></dt> 51<dt><span class="sect2"><a href="cg-manual.html#cg-manual.annopts.accuracy">5.8.3. Accuracy</a></span></dt> 52</dl></dd> 53<dt><span class="sect1"><a href="cg-manual.html#cg-manual.impl-details">5.9. Implementation Details</a></span></dt> 54<dd><dl> 55<dt><span class="sect2"><a href="cg-manual.html#cg-manual.impl-details.how-cg-works">5.9.1. How Cachegrind Works</a></span></dt> 56<dt><span class="sect2"><a href="cg-manual.html#cg-manual.impl-details.file-format">5.9.2. Cachegrind Output File Format</a></span></dt> 57</dl></dd> 58</dl> 59</div> 60<p>To use this tool, you must specify 61<code class="option">--tool=cachegrind</code> on the 62Valgrind command line.</p> 63<div class="sect1"> 64<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 65<a name="cg-manual.overview"></a>5.1.�Overview</h2></div></div></div> 66<p>Cachegrind simulates how your program interacts with a machine's cache 67hierarchy and (optionally) branch predictor. It simulates a machine with 68independent first-level instruction and data caches (I1 and D1), backed by a 69unified second-level cache (L2). This exactly matches the configuration of 70many modern machines.</p> 71<p>However, some modern machines have three or four levels of cache. For these 72machines (in the cases where Cachegrind can auto-detect the cache 73configuration) Cachegrind simulates the first-level and last-level caches. 74The reason for this choice is that the last-level cache has the most influence on 75runtime, as it masks accesses to main memory. Furthermore, the L1 caches 76often have low associativity, so simulating them can detect cases where the 77code interacts badly with this cache (eg. traversing a matrix column-wise 78with the row length being a power of 2).</p> 79<p>Therefore, Cachegrind always refers to the I1, D1 and LL (last-level) 80caches.</p> 81<p> 82Cachegrind gathers the following statistics (abbreviations used for each statistic 83is given in parentheses):</p> 84<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 85<li class="listitem"><p>I cache reads (<code class="computeroutput">Ir</code>, 86 which equals the number of instructions executed), 87 I1 cache read misses (<code class="computeroutput">I1mr</code>) and 88 LL cache instruction read misses (<code class="computeroutput">ILmr</code>). 89 </p></li> 90<li class="listitem"><p>D cache reads (<code class="computeroutput">Dr</code>, which 91 equals the number of memory reads), 92 D1 cache read misses (<code class="computeroutput">D1mr</code>), and 93 LL cache data read misses (<code class="computeroutput">DLmr</code>). 94 </p></li> 95<li class="listitem"><p>D cache writes (<code class="computeroutput">Dw</code>, which equals 96 the number of memory writes), 97 D1 cache write misses (<code class="computeroutput">D1mw</code>), and 98 LL cache data write misses (<code class="computeroutput">DLmw</code>). 99 </p></li> 100<li class="listitem"><p>Conditional branches executed (<code class="computeroutput">Bc</code>) and 101 conditional branches mispredicted (<code class="computeroutput">Bcm</code>). 102 </p></li> 103<li class="listitem"><p>Indirect branches executed (<code class="computeroutput">Bi</code>) and 104 indirect branches mispredicted (<code class="computeroutput">Bim</code>). 105 </p></li> 106</ul></div> 107<p>Note that D1 total accesses is given by 108<code class="computeroutput">D1mr</code> + 109<code class="computeroutput">D1mw</code>, and that LL total 110accesses is given by <code class="computeroutput">ILmr</code> + 111<code class="computeroutput">DLmr</code> + 112<code class="computeroutput">DLmw</code>. 113</p> 114<p>These statistics are presented for the entire program and for each 115function in the program. You can also annotate each line of source code in 116the program with the counts that were caused directly by it.</p> 117<p>On a modern machine, an L1 miss will typically cost 118around 10 cycles, an LL miss can cost as much as 200 119cycles, and a mispredicted branch costs in the region of 10 120to 30 cycles. Detailed cache and branch profiling can be very useful 121for understanding how your program interacts with the machine and thus how 122to make it faster.</p> 123<p>Also, since one instruction cache read is performed per 124instruction executed, you can find out how many instructions are 125executed per line, which can be useful for traditional profiling.</p> 126</div> 127<div class="sect1"> 128<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 129<a name="cg-manual.profile"></a>5.2.�Using Cachegrind, cg_annotate and cg_merge</h2></div></div></div> 130<p>First off, as for normal Valgrind use, you probably want to 131compile with debugging info (the 132<code class="option">-g</code> option). But by contrast with 133normal Valgrind use, you probably do want to turn 134optimisation on, since you should profile your program as it will 135be normally run.</p> 136<p>Then, you need to run Cachegrind itself to gather the profiling 137information, and then run cg_annotate to get a detailed presentation of that 138information. As an optional intermediate step, you can use cg_merge to sum 139together the outputs of multiple Cachegrind runs into a single file which 140you then use as the input for cg_annotate. Alternatively, you can use 141cg_diff to difference the outputs of two Cachegrind runs into a single file 142which you then use as the input for cg_annotate.</p> 143<div class="sect2"> 144<div class="titlepage"><div><div><h3 class="title"> 145<a name="cg-manual.running-cachegrind"></a>5.2.1.�Running Cachegrind</h3></div></div></div> 146<p>To run Cachegrind on a program <code class="filename">prog</code>, run:</p> 147<pre class="screen"> 148valgrind --tool=cachegrind prog 149</pre> 150<p>The program will execute (slowly). Upon completion, 151summary statistics that look like this will be printed:</p> 152<pre class="programlisting"> 153==31751== I refs: 27,742,716 154==31751== I1 misses: 276 155==31751== LLi misses: 275 156==31751== I1 miss rate: 0.0% 157==31751== LLi miss rate: 0.0% 158==31751== 159==31751== D refs: 15,430,290 (10,955,517 rd + 4,474,773 wr) 160==31751== D1 misses: 41,185 ( 21,905 rd + 19,280 wr) 161==31751== LLd misses: 23,085 ( 3,987 rd + 19,098 wr) 162==31751== D1 miss rate: 0.2% ( 0.1% + 0.4%) 163==31751== LLd miss rate: 0.1% ( 0.0% + 0.4%) 164==31751== 165==31751== LL misses: 23,360 ( 4,262 rd + 19,098 wr) 166==31751== LL miss rate: 0.0% ( 0.0% + 0.4%)</pre> 167<p>Cache accesses for instruction fetches are summarised 168first, giving the number of fetches made (this is the number of 169instructions executed, which can be useful to know in its own 170right), the number of I1 misses, and the number of LL instruction 171(<code class="computeroutput">LLi</code>) misses.</p> 172<p>Cache accesses for data follow. The information is similar 173to that of the instruction fetches, except that the values are 174also shown split between reads and writes (note each row's 175<code class="computeroutput">rd</code> and 176<code class="computeroutput">wr</code> values add up to the row's 177total).</p> 178<p>Combined instruction and data figures for the LL cache 179follow that. Note that the LL miss rate is computed relative to the total 180number of memory accesses, not the number of L1 misses. I.e. it is 181<code class="computeroutput">(ILmr + DLmr + DLmw) / (Ir + Dr + Dw)</code> 182not 183<code class="computeroutput">(ILmr + DLmr + DLmw) / (I1mr + D1mr + D1mw)</code> 184</p> 185<p>Branch prediction statistics are not collected by default. 186To do so, add the option <code class="option">--branch-sim=yes</code>.</p> 187</div> 188<div class="sect2"> 189<div class="titlepage"><div><div><h3 class="title"> 190<a name="cg-manual.outputfile"></a>5.2.2.�Output File</h3></div></div></div> 191<p>As well as printing summary information, Cachegrind also writes 192more detailed profiling information to a file. By default this file is named 193<code class="filename">cachegrind.out.<pid></code> (where 194<code class="filename"><pid></code> is the program's process ID), but its name 195can be changed with the <code class="option">--cachegrind-out-file</code> option. This 196file is human-readable, but is intended to be interpreted by the 197accompanying program cg_annotate, described in the next section.</p> 198<p>The default <code class="computeroutput">.<pid></code> suffix 199on the output file name serves two purposes. Firstly, it means you 200don't have to rename old log files that you don't want to overwrite. 201Secondly, and more importantly, it allows correct profiling with the 202<code class="option">--trace-children=yes</code> option of 203programs that spawn child processes.</p> 204<p>The output file can be big, many megabytes for large applications 205built with full debugging information.</p> 206</div> 207<div class="sect2"> 208<div class="titlepage"><div><div><h3 class="title"> 209<a name="cg-manual.running-cg_annotate"></a>5.2.3.�Running cg_annotate</h3></div></div></div> 210<p>Before using cg_annotate, 211it is worth widening your window to be at least 120-characters 212wide if possible, as the output lines can be quite long.</p> 213<p>To get a function-by-function summary, run:</p> 214<pre class="screen">cg_annotate <filename></pre> 215<p>on a Cachegrind output file.</p> 216</div> 217<div class="sect2"> 218<div class="titlepage"><div><div><h3 class="title"> 219<a name="cg-manual.the-output-preamble"></a>5.2.4.�The Output Preamble</h3></div></div></div> 220<p>The first part of the output looks like this:</p> 221<pre class="programlisting"> 222-------------------------------------------------------------------------------- 223I1 cache: 65536 B, 64 B, 2-way associative 224D1 cache: 65536 B, 64 B, 2-way associative 225LL cache: 262144 B, 64 B, 8-way associative 226Command: concord vg_to_ucode.c 227Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 228Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 229Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 230Threshold: 99% 231Chosen for annotation: 232Auto-annotation: off 233</pre> 234<p>This is a summary of the annotation options:</p> 235<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 236<li class="listitem"><p>I1 cache, D1 cache, LL cache: cache configuration. So 237 you know the configuration with which these results were 238 obtained.</p></li> 239<li class="listitem"><p>Command: the command line invocation of the program 240 under examination.</p></li> 241<li class="listitem"><p>Events recorded: which events were recorded.</p></li> 242<li class="listitem"><p>Events shown: the events shown, which is a subset of the events 243 gathered. This can be adjusted with the 244 <code class="option">--show</code> option.</p></li> 245<li class="listitem"> 246<p>Event sort order: the sort order in which functions are 247 shown. For example, in this case the functions are sorted 248 from highest <code class="computeroutput">Ir</code> counts to 249 lowest. If two functions have identical 250 <code class="computeroutput">Ir</code> counts, they will then be 251 sorted by <code class="computeroutput">I1mr</code> counts, and 252 so on. This order can be adjusted with the 253 <code class="option">--sort</code> option.</p> 254<p>Note that this dictates the order the functions appear. 255 It is <span class="emphasis"><em>not</em></span> the order in which the columns 256 appear; that is dictated by the "events shown" line (and can 257 be changed with the <code class="option">--show</code> 258 option).</p> 259</li> 260<li class="listitem"><p>Threshold: cg_annotate 261 by default omits functions that cause very low counts 262 to avoid drowning you in information. In this case, 263 cg_annotate shows summaries the functions that account for 264 99% of the <code class="computeroutput">Ir</code> counts; 265 <code class="computeroutput">Ir</code> is chosen as the 266 threshold event since it is the primary sort event. The 267 threshold can be adjusted with the 268 <code class="option">--threshold</code> 269 option.</p></li> 270<li class="listitem"><p>Chosen for annotation: names of files specified 271 manually for annotation; in this case none.</p></li> 272<li class="listitem"><p>Auto-annotation: whether auto-annotation was requested 273 via the <code class="option">--auto=yes</code> 274 option. In this case no.</p></li> 275</ul></div> 276</div> 277<div class="sect2"> 278<div class="titlepage"><div><div><h3 class="title"> 279<a name="cg-manual.the-global"></a>5.2.5.�The Global and Function-level Counts</h3></div></div></div> 280<p>Then follows summary statistics for the whole 281program:</p> 282<pre class="programlisting"> 283-------------------------------------------------------------------------------- 284Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 285-------------------------------------------------------------------------------- 28627,742,716 276 275 10,955,517 21,905 3,987 4,474,773 19,280 19,098 PROGRAM TOTALS</pre> 287<p> 288These are similar to the summary provided when Cachegrind finishes running. 289</p> 290<p>Then comes function-by-function statistics:</p> 291<pre class="programlisting"> 292-------------------------------------------------------------------------------- 293Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function 294-------------------------------------------------------------------------------- 2958,821,482 5 5 2,242,702 1,621 73 1,794,230 0 0 getc.c:_IO_getc 2965,222,023 4 4 2,276,334 16 12 875,959 1 1 concord.c:get_word 2972,649,248 2 2 1,344,810 7,326 1,385 . . . vg_main.c:strcmp 2982,521,927 2 2 591,215 0 0 179,398 0 0 concord.c:hash 2992,242,740 2 2 1,046,612 568 22 448,548 0 0 ctype.c:tolower 3001,496,937 4 4 630,874 9,000 1,400 279,388 0 0 concord.c:insert 301 897,991 51 51 897,831 95 30 62 1 1 ???:??? 302 598,068 1 1 299,034 0 0 149,517 0 0 ../sysdeps/generic/lockfile.c:__flockfile 303 598,068 0 0 299,034 0 0 149,517 0 0 ../sysdeps/generic/lockfile.c:__funlockfile 304 598,024 4 4 213,580 35 16 149,506 0 0 vg_clientmalloc.c:malloc 305 446,587 1 1 215,973 2,167 430 129,948 14,057 13,957 concord.c:add_existing 306 341,760 2 2 128,160 0 0 128,160 0 0 vg_clientmalloc.c:vg_trap_here_WRAPPER 307 320,782 4 4 150,711 276 0 56,027 53 53 concord.c:init_hash_table 308 298,998 1 1 106,785 0 0 64,071 1 1 concord.c:create 309 149,518 0 0 149,516 0 0 1 0 0 ???:tolower@@GLIBC_2.0 310 149,518 0 0 149,516 0 0 1 0 0 ???:fgetc@@GLIBC_2.0 311 95,983 4 4 38,031 0 0 34,409 3,152 3,150 concord.c:new_word_node 312 85,440 0 0 42,720 0 0 21,360 0 0 vg_clientmalloc.c:vg_bogus_epilogue</pre> 313<p>Each function 314is identified by a 315<code class="computeroutput">file_name:function_name</code> pair. If 316a column contains only a dot it means the function never performs 317that event (e.g. the third row shows that 318<code class="computeroutput">strcmp()</code> contains no 319instructions that write to memory). The name 320<code class="computeroutput">???</code> is used if the file name 321and/or function name could not be determined from debugging 322information. If most of the entries have the form 323<code class="computeroutput">???:???</code> the program probably 324wasn't compiled with <code class="option">-g</code>.</p> 325<p>It is worth noting that functions will come both from 326the profiled program (e.g. <code class="filename">concord.c</code>) 327and from libraries (e.g. <code class="filename">getc.c</code>)</p> 328</div> 329<div class="sect2"> 330<div class="titlepage"><div><div><h3 class="title"> 331<a name="cg-manual.line-by-line"></a>5.2.6.�Line-by-line Counts</h3></div></div></div> 332<p>There are two ways to annotate source files -- by specifying them 333manually as arguments to cg_annotate, or with the 334<code class="option">--auto=yes</code> option. For example, the output from running 335<code class="filename">cg_annotate <filename> concord.c</code> for our example 336produces the same output as above followed by an annotated version of 337<code class="filename">concord.c</code>, a section of which looks like:</p> 338<pre class="programlisting"> 339-------------------------------------------------------------------------------- 340-- User-annotated source: concord.c 341-------------------------------------------------------------------------------- 342Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 343 344 . . . . . . . . . void init_hash_table(char *file_name, Word_Node *table[]) 345 3 1 1 . . . 1 0 0 { 346 . . . . . . . . . FILE *file_ptr; 347 . . . . . . . . . Word_Info *data; 348 1 0 0 . . . 1 1 1 int line = 1, i; 349 . . . . . . . . . 350 5 0 0 . . . 3 0 0 data = (Word_Info *) create(sizeof(Word_Info)); 351 . . . . . . . . . 352 4,991 0 0 1,995 0 0 998 0 0 for (i = 0; i < TABLE_SIZE; i++) 353 3,988 1 1 1,994 0 0 997 53 52 table[i] = NULL; 354 . . . . . . . . . 355 . . . . . . . . . /* Open file, check it. */ 356 6 0 0 1 0 0 4 0 0 file_ptr = fopen(file_name, "r"); 357 2 0 0 1 0 0 . . . if (!(file_ptr)) { 358 . . . . . . . . . fprintf(stderr, "Couldn't open '%s'.\n", file_name); 359 1 1 1 . . . . . . exit(EXIT_FAILURE); 360 . . . . . . . . . } 361 . . . . . . . . . 362 165,062 1 1 73,360 0 0 91,700 0 0 while ((line = get_word(data, line, file_ptr)) != EOF) 363 146,712 0 0 73,356 0 0 73,356 0 0 insert(data->;word, data->line, table); 364 . . . . . . . . . 365 4 0 0 1 0 0 2 0 0 free(data); 366 4 0 0 1 0 0 2 0 0 fclose(file_ptr); 367 3 0 0 2 0 0 . . . }</pre> 368<p>(Although column widths are automatically minimised, a wide 369terminal is clearly useful.)</p> 370<p>Each source file is clearly marked 371(<code class="computeroutput">User-annotated source</code>) as 372having been chosen manually for annotation. If the file was 373found in one of the directories specified with the 374<code class="option">-I</code>/<code class="option">--include</code> option, the directory 375and file are both given.</p> 376<p>Each line is annotated with its event counts. Events not 377applicable for a line are represented by a dot. This is useful 378for distinguishing between an event which cannot happen, and one 379which can but did not.</p> 380<p>Sometimes only a small section of a source file is 381executed. To minimise uninteresting output, Cachegrind only shows 382annotated lines and lines within a small distance of annotated 383lines. Gaps are marked with the line numbers so you know which 384part of a file the shown code comes from, eg:</p> 385<pre class="programlisting"> 386(figures and code for line 704) 387-- line 704 ---------------------------------------- 388-- line 878 ---------------------------------------- 389(figures and code for line 878)</pre> 390<p>The amount of context to show around annotated lines is 391controlled by the <code class="option">--context</code> 392option.</p> 393<p>To get automatic annotation, use the <code class="option">--auto=yes</code> option. 394cg_annotate will automatically annotate every source file it can 395find that is mentioned in the function-by-function summary. 396Therefore, the files chosen for auto-annotation are affected by 397the <code class="option">--sort</code> and 398<code class="option">--threshold</code> options. Each 399source file is clearly marked (<code class="computeroutput">Auto-annotated 400source</code>) as being chosen automatically. Any 401files that could not be found are mentioned at the end of the 402output, eg:</p> 403<pre class="programlisting"> 404------------------------------------------------------------------ 405The following files chosen for auto-annotation could not be found: 406------------------------------------------------------------------ 407 getc.c 408 ctype.c 409 ../sysdeps/generic/lockfile.c</pre> 410<p>This is quite common for library files, since libraries are 411usually compiled with debugging information, but the source files 412are often not present on a system. If a file is chosen for 413annotation both manually and automatically, it 414is marked as <code class="computeroutput">User-annotated 415source</code>. Use the 416<code class="option">-I</code>/<code class="option">--include</code> option to tell Valgrind where 417to look for source files if the filenames found from the debugging 418information aren't specific enough.</p> 419<p>Beware that cg_annotate can take some time to digest large 420<code class="filename">cachegrind.out.<pid></code> files, 421e.g. 30 seconds or more. Also beware that auto-annotation can 422produce a lot of output if your program is large!</p> 423</div> 424<div class="sect2"> 425<div class="titlepage"><div><div><h3 class="title"> 426<a name="cg-manual.assembler"></a>5.2.7.�Annotating Assembly Code Programs</h3></div></div></div> 427<p>Valgrind can annotate assembly code programs too, or annotate 428the assembly code generated for your C program. Sometimes this is 429useful for understanding what is really happening when an 430interesting line of C code is translated into multiple 431instructions.</p> 432<p>To do this, you just need to assemble your 433<code class="computeroutput">.s</code> files with assembly-level debug 434information. You can use compile with the <code class="option">-S</code> to compile C/C++ 435programs to assembly code, and then assemble the assembly code files with 436<code class="option">-g</code> to achieve this. You can then profile and annotate the 437assembly code source files in the same way as C/C++ source files.</p> 438</div> 439<div class="sect2"> 440<div class="titlepage"><div><div><h3 class="title"> 441<a name="ms-manual.forkingprograms"></a>5.2.8.�Forking Programs</h3></div></div></div> 442<p>If your program forks, the child will inherit all the profiling data that 443has been gathered for the parent.</p> 444<p>If the output file format string (controlled by 445<code class="option">--cachegrind-out-file</code>) does not contain <code class="option">%p</code>, 446then the outputs from the parent and child will be intermingled in a single 447output file, which will almost certainly make it unreadable by 448cg_annotate.</p> 449</div> 450<div class="sect2"> 451<div class="titlepage"><div><div><h3 class="title"> 452<a name="cg-manual.annopts.warnings"></a>5.2.9.�cg_annotate Warnings</h3></div></div></div> 453<p>There are a couple of situations in which 454cg_annotate issues warnings.</p> 455<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 456<li class="listitem"><p>If a source file is more recent than the 457 <code class="filename">cachegrind.out.<pid></code> file. 458 This is because the information in 459 <code class="filename">cachegrind.out.<pid></code> is only 460 recorded with line numbers, so if the line numbers change at 461 all in the source (e.g. lines added, deleted, swapped), any 462 annotations will be incorrect.</p></li> 463<li class="listitem"><p>If information is recorded about line numbers past the 464 end of a file. This can be caused by the above problem, 465 i.e. shortening the source file while using an old 466 <code class="filename">cachegrind.out.<pid></code> file. If 467 this happens, the figures for the bogus lines are printed 468 anyway (clearly marked as bogus) in case they are 469 important.</p></li> 470</ul></div> 471</div> 472<div class="sect2"> 473<div class="titlepage"><div><div><h3 class="title"> 474<a name="cg-manual.annopts.things-to-watch-out-for"></a>5.2.10.�Unusual Annotation Cases</h3></div></div></div> 475<p>Some odd things that can occur during annotation:</p> 476<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 477<li class="listitem"> 478<p>If annotating at the assembler level, you might see 479 something like this:</p> 480<pre class="programlisting"> 481 1 0 0 . . . . . . leal -12(%ebp),%eax 482 1 0 0 . . . 1 0 0 movl %eax,84(%ebx) 483 2 0 0 0 0 0 1 0 0 movl $1,-20(%ebp) 484 . . . . . . . . . .align 4,0x90 485 1 0 0 . . . . . . movl $.LnrB,%eax 486 1 0 0 . . . 1 0 0 movl %eax,-16(%ebp)</pre> 487<p>How can the third instruction be executed twice when 488 the others are executed only once? As it turns out, it 489 isn't. Here's a dump of the executable, using 490 <code class="computeroutput">objdump -d</code>:</p> 491<pre class="programlisting"> 492 8048f25: 8d 45 f4 lea 0xfffffff4(%ebp),%eax 493 8048f28: 89 43 54 mov %eax,0x54(%ebx) 494 8048f2b: c7 45 ec 01 00 00 00 movl $0x1,0xffffffec(%ebp) 495 8048f32: 89 f6 mov %esi,%esi 496 8048f34: b8 08 8b 07 08 mov $0x8078b08,%eax 497 8048f39: 89 45 f0 mov %eax,0xfffffff0(%ebp)</pre> 498<p>Notice the extra <code class="computeroutput">mov 499 %esi,%esi</code> instruction. Where did this come 500 from? The GNU assembler inserted it to serve as the two 501 bytes of padding needed to align the <code class="computeroutput">movl 502 $.LnrB,%eax</code> instruction on a four-byte 503 boundary, but pretended it didn't exist when adding debug 504 information. Thus when Valgrind reads the debug info it 505 thinks that the <code class="computeroutput">movl 506 $0x1,0xffffffec(%ebp)</code> instruction covers the 507 address range 0x8048f2b--0x804833 by itself, and attributes 508 the counts for the <code class="computeroutput">mov 509 %esi,%esi</code> to it.</p> 510</li> 511<li class="listitem"><p>Sometimes, the same filename might be represented with 512 a relative name and with an absolute name in different parts 513 of the debug info, eg: 514 <code class="filename">/home/user/proj/proj.h</code> and 515 <code class="filename">../proj.h</code>. In this case, if you use 516 auto-annotation, the file will be annotated twice with the 517 counts split between the two.</p></li> 518<li class="listitem"><p>If you compile some files with 519 <code class="option">-g</code> and some without, some 520 events that take place in a file without debug info could be 521 attributed to the last line of a file with debug info 522 (whichever one gets placed before the non-debug-info file in 523 the executable).</p></li> 524</ul></div> 525<p>This list looks long, but these cases should be fairly 526rare.</p> 527</div> 528<div class="sect2"> 529<div class="titlepage"><div><div><h3 class="title"> 530<a name="cg-manual.cg_merge"></a>5.2.11.�Merging Profiles with cg_merge</h3></div></div></div> 531<p> 532cg_merge is a simple program which 533reads multiple profile files, as created by Cachegrind, merges them 534together, and writes the results into another file in the same format. 535You can then examine the merged results using 536<code class="computeroutput">cg_annotate <filename></code>, as 537described above. The merging functionality might be useful if you 538want to aggregate costs over multiple runs of the same program, or 539from a single parallel run with multiple instances of the same 540program.</p> 541<p> 542cg_merge is invoked as follows: 543</p> 544<pre class="programlisting"> 545cg_merge -o outputfile file1 file2 file3 ...</pre> 546<p> 547It reads and checks <code class="computeroutput">file1</code>, then read 548and checks <code class="computeroutput">file2</code> and merges it into 549the running totals, then the same with 550<code class="computeroutput">file3</code>, etc. The final results are 551written to <code class="computeroutput">outputfile</code>, or to standard 552out if no output file is specified.</p> 553<p> 554Costs are summed on a per-function, per-line and per-instruction 555basis. Because of this, the order in which the input files does not 556matter, although you should take care to only mention each file once, 557since any file mentioned twice will be added in twice.</p> 558<p> 559cg_merge does not attempt to check 560that the input files come from runs of the same executable. It will 561happily merge together profile files from completely unrelated 562programs. It does however check that the 563<code class="computeroutput">Events:</code> lines of all the inputs are 564identical, so as to ensure that the addition of costs makes sense. 565For example, it would be nonsensical for it to add a number indicating 566D1 read references to a number from a different file indicating LL 567write misses.</p> 568<p> 569A number of other syntax and sanity checks are done whilst reading the 570inputs. cg_merge will stop and 571attempt to print a helpful error message if any of the input files 572fail these checks.</p> 573</div> 574<div class="sect2"> 575<div class="titlepage"><div><div><h3 class="title"> 576<a name="cg-manual.cg_diff"></a>5.2.12.�Differencing Profiles with cg_diff</h3></div></div></div> 577<p> 578cg_diff is a simple program which 579reads two profile files, as created by Cachegrind, finds the difference 580between them, and writes the results into another file in the same format. 581You can then examine the merged results using 582<code class="computeroutput">cg_annotate <filename></code>, as 583described above. This is very useful if you want to measure how a change to 584a program affected its performance. 585</p> 586<p> 587cg_diff is invoked as follows: 588</p> 589<pre class="programlisting"> 590cg_diff file1 file2</pre> 591<p> 592It reads and checks <code class="computeroutput">file1</code>, then read 593and checks <code class="computeroutput">file2</code>, then computes the 594difference (effectively <code class="computeroutput">file1</code> - 595<code class="computeroutput">file2</code>). The final results are written to 596standard output.</p> 597<p> 598Costs are summed on a per-function basis. Per-line costs are not summed, 599because doing so is too difficult. For example, consider differencing two 600profiles, one from a single-file program A, and one from the same program A 601where a single blank line was inserted at the top of the file. Every single 602per-line count has changed. In comparison, the per-function counts have not 603changed. The per-function count differences are still very useful for 604determining differences between programs. Note that because the result is 605the difference of two profiles, many of the counts will be negative; this 606indicates that the counts for the relevant function are fewer in the second 607version than those in the first version.</p> 608<p> 609cg_diff does not attempt to check 610that the input files come from runs of the same executable. It will 611happily merge together profile files from completely unrelated 612programs. It does however check that the 613<code class="computeroutput">Events:</code> lines of all the inputs are 614identical, so as to ensure that the addition of costs makes sense. 615For example, it would be nonsensical for it to add a number indicating 616D1 read references to a number from a different file indicating LL 617write misses.</p> 618<p> 619A number of other syntax and sanity checks are done whilst reading the 620inputs. cg_diff will stop and 621attempt to print a helpful error message if any of the input files 622fail these checks.</p> 623<p> 624Sometimes you will want to compare Cachegrind profiles of two versions of a 625program that you have sitting side-by-side. For example, you might have 626<code class="computeroutput">version1/prog.c</code> and 627<code class="computeroutput">version2/prog.c</code>, where the second is 628slightly different to the first. A straight comparison of the two will not 629be useful -- because functions are qualified with filenames, a function 630<code class="function">f</code> will be listed as 631<code class="computeroutput">version1/prog.c:f</code> for the first version but 632<code class="computeroutput">version2/prog.c:f</code> for the second 633version.</p> 634<p> 635When this happens, you can use the <code class="option">--mod-filename</code> option. 636Its argument is a Perl search-and-replace expression that will be applied 637to all the filenames in both Cachegrind output files. It can be used to 638remove minor differences in filenames. For example, the option 639<code class="option">--mod-filename='s/version[0-9]/versionN/'</code> will suffice for 640this case.</p> 641<p> 642Similarly, sometimes compilers auto-generate certain functions and give them 643randomized names. For example, GCC sometimes auto-generates functions with 644names like <code class="function">T.1234</code>, and the suffixes vary from build to 645build. You can use the <code class="option">--mod-funcname</code> option to remove 646small differences like these; it works in the same way as 647<code class="option">--mod-filename</code>.</p> 648</div> 649</div> 650<div class="sect1"> 651<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 652<a name="cg-manual.cgopts"></a>5.3.�Cachegrind Command-line Options</h2></div></div></div> 653<p>Cachegrind-specific options are:</p> 654<div class="variablelist"> 655<a name="cg.opts.list"></a><dl class="variablelist"> 656<dt> 657<a name="opt.I1"></a><span class="term"> 658 <code class="option">--I1=<size>,<associativity>,<line size> </code> 659 </span> 660</dt> 661<dd><p>Specify the size, associativity and line size of the level 1 662 instruction cache. </p></dd> 663<dt> 664<a name="opt.D1"></a><span class="term"> 665 <code class="option">--D1=<size>,<associativity>,<line size> </code> 666 </span> 667</dt> 668<dd><p>Specify the size, associativity and line size of the level 1 669 data cache.</p></dd> 670<dt> 671<a name="opt.LL"></a><span class="term"> 672 <code class="option">--LL=<size>,<associativity>,<line size> </code> 673 </span> 674</dt> 675<dd><p>Specify the size, associativity and line size of the last-level 676 cache.</p></dd> 677<dt> 678<a name="opt.cache-sim"></a><span class="term"> 679 <code class="option">--cache-sim=no|yes [yes] </code> 680 </span> 681</dt> 682<dd><p>Enables or disables collection of cache access and miss 683 counts.</p></dd> 684<dt> 685<a name="opt.branch-sim"></a><span class="term"> 686 <code class="option">--branch-sim=no|yes [no] </code> 687 </span> 688</dt> 689<dd><p>Enables or disables collection of branch instruction and 690 misprediction counts. By default this is disabled as it 691 slows Cachegrind down by approximately 25%. Note that you 692 cannot specify <code class="option">--cache-sim=no</code> 693 and <code class="option">--branch-sim=no</code> 694 together, as that would leave Cachegrind with no 695 information to collect.</p></dd> 696<dt> 697<a name="opt.cachegrind-out-file"></a><span class="term"> 698 <code class="option">--cachegrind-out-file=<file> </code> 699 </span> 700</dt> 701<dd><p>Write the profile data to 702 <code class="computeroutput">file</code> rather than to the default 703 output file, 704 <code class="filename">cachegrind.out.<pid></code>. The 705 <code class="option">%p</code> and <code class="option">%q</code> format specifiers 706 can be used to embed the process ID and/or the contents of an 707 environment variable in the name, as is the case for the core 708 option <code class="option"><a class="xref" href="manual-core.html#opt.log-file">--log-file</a></code>. 709 </p></dd> 710</dl> 711</div> 712</div> 713<div class="sect1"> 714<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 715<a name="cg-manual.annopts"></a>5.4.�cg_annotate Command-line Options</h2></div></div></div> 716<div class="variablelist"> 717<a name="cg_annotate.opts.list"></a><dl class="variablelist"> 718<dt><span class="term"> 719 <code class="option">-h --help </code> 720 </span></dt> 721<dd><p>Show the help message.</p></dd> 722<dt><span class="term"> 723 <code class="option">--version </code> 724 </span></dt> 725<dd><p>Show the version number.</p></dd> 726<dt><span class="term"> 727 <code class="option">--show=A,B,C [default: all, using order in 728 cachegrind.out.<pid>] </code> 729 </span></dt> 730<dd><p>Specifies which events to show (and the column 731 order). Default is to use all present in the 732 <code class="filename">cachegrind.out.<pid></code> file (and 733 use the order in the file). Useful if you want to concentrate on, for 734 example, I cache misses (<code class="option">--show=I1mr,ILmr</code>), or data 735 read misses (<code class="option">--show=D1mr,DLmr</code>), or LL data misses 736 (<code class="option">--show=DLmr,DLmw</code>). Best used in conjunction with 737 <code class="option">--sort</code>.</p></dd> 738<dt><span class="term"> 739 <code class="option">--sort=A,B,C [default: order in 740 cachegrind.out.<pid>] </code> 741 </span></dt> 742<dd><p>Specifies the events upon which the sorting of the 743 function-by-function entries will be based.</p></dd> 744<dt><span class="term"> 745 <code class="option">--threshold=X [default: 0.1%] </code> 746 </span></dt> 747<dd> 748<p>Sets the threshold for the function-by-function 749 summary. A function is shown if it accounts for more than X% 750 of the counts for the primary sort event. If auto-annotating, also 751 affects which files are annotated.</p> 752<p>Note: thresholds can be set for more than one of the 753 events by appending any events for the 754 <code class="option">--sort</code> option with a colon 755 and a number (no spaces, though). E.g. if you want to see 756 each function that covers more than 1% of LL read misses or 1% of LL 757 write misses, use this option:</p> 758<p><code class="option">--sort=DLmr:1,DLmw:1</code></p> 759</dd> 760<dt><span class="term"> 761 <code class="option">--auto=<no|yes> [default: no] </code> 762 </span></dt> 763<dd><p>When enabled, automatically annotates every file that 764 is mentioned in the function-by-function summary that can be 765 found. Also gives a list of those that couldn't be found.</p></dd> 766<dt><span class="term"> 767 <code class="option">--context=N [default: 8] </code> 768 </span></dt> 769<dd><p>Print N lines of context before and after each 770 annotated line. Avoids printing large sections of source 771 files that were not executed. Use a large number 772 (e.g. 100000) to show all source lines.</p></dd> 773<dt><span class="term"> 774 <code class="option">-I<dir> --include=<dir> [default: none] </code> 775 </span></dt> 776<dd><p>Adds a directory to the list in which to search for 777 files. Multiple <code class="option">-I</code>/<code class="option">--include</code> 778 options can be given to add multiple directories.</p></dd> 779</dl> 780</div> 781</div> 782<div class="sect1"> 783<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 784<a name="cg-manual.mergeopts"></a>5.5.�cg_merge Command-line Options</h2></div></div></div> 785<div class="variablelist"> 786<a name="cg_merge.opts.list"></a><dl class="variablelist"> 787<dt><span class="term"> 788 <code class="option">-o outfile</code> 789 </span></dt> 790<dd><p>Write the profile data to <code class="computeroutput">outfile</code> 791 rather than to standard output. 792 </p></dd> 793</dl> 794</div> 795</div> 796<div class="sect1"> 797<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 798<a name="cg-manual.diffopts"></a>5.6.�cg_diff Command-line Options</h2></div></div></div> 799<div class="variablelist"> 800<a name="cg_diff.opts.list"></a><dl class="variablelist"> 801<dt><span class="term"> 802 <code class="option">-h --help </code> 803 </span></dt> 804<dd><p>Show the help message.</p></dd> 805<dt><span class="term"> 806 <code class="option">--version </code> 807 </span></dt> 808<dd><p>Show the version number.</p></dd> 809<dt><span class="term"> 810 <code class="option">--mod-filename=<expr> [default: none]</code> 811 </span></dt> 812<dd><p>Specifies a Perl search-and-replace expression that is applied 813 to all filenames. Useful for removing minor differences in paths 814 between two different versions of a program that are sitting in 815 different directories.</p></dd> 816<dt><span class="term"> 817 <code class="option">--mod-funcname=<expr> [default: none]</code> 818 </span></dt> 819<dd><p>Like <code class="option">--mod-filename</code>, but for filenames. 820 Useful for removing minor differences in randomized names of 821 auto-generated functions generated by some compilers.</p></dd> 822</dl> 823</div> 824</div> 825<div class="sect1"> 826<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 827<a name="cg-manual.acting-on"></a>5.7.�Acting on Cachegrind's Information</h2></div></div></div> 828<p> 829Cachegrind gives you lots of information, but acting on that information 830isn't always easy. Here are some rules of thumb that we have found to be 831useful.</p> 832<p> 833First of all, the global hit/miss counts and miss rates are not that useful. 834If you have multiple programs or multiple runs of a program, comparing the 835numbers might identify if any are outliers and worthy of closer 836investigation. Otherwise, they're not enough to act on.</p> 837<p> 838The function-by-function counts are more useful to look at, as they pinpoint 839which functions are causing large numbers of counts. However, beware that 840inlining can make these counts misleading. If a function 841<code class="function">f</code> is always inlined, counts will be attributed to the 842functions it is inlined into, rather than itself. However, if you look at 843the line-by-line annotations for <code class="function">f</code> you'll see the 844counts that belong to <code class="function">f</code>. (This is hard to avoid, it's 845how the debug info is structured.) So it's worth looking for large numbers 846in the line-by-line annotations.</p> 847<p> 848The line-by-line source code annotations are much more useful. In our 849experience, the best place to start is by looking at the 850<code class="computeroutput">Ir</code> numbers. They simply measure how many 851instructions were executed for each line, and don't include any cache 852information, but they can still be very useful for identifying 853bottlenecks.</p> 854<p> 855After that, we have found that LL misses are typically a much bigger source 856of slow-downs than L1 misses. So it's worth looking for any snippets of 857code with high <code class="computeroutput">DLmr</code> or 858<code class="computeroutput">DLmw</code> counts. (You can use 859<code class="option">--show=DLmr 860--sort=DLmr</code> with cg_annotate to focus just on 861<code class="literal">DLmr</code> counts, for example.) If you find any, it's still 862not always easy to work out how to improve things. You need to have a 863reasonable understanding of how caches work, the principles of locality, and 864your program's data access patterns. Improving things may require 865redesigning a data structure, for example.</p> 866<p> 867Looking at the <code class="computeroutput">Bcm</code> and 868<code class="computeroutput">Bim</code> misses can also be helpful. 869In particular, <code class="computeroutput">Bim</code> misses are often caused 870by <code class="literal">switch</code> statements, and in some cases these 871<code class="literal">switch</code> statements can be replaced with table-driven code. 872For example, you might replace code like this:</p> 873<pre class="programlisting"> 874enum E { A, B, C }; 875enum E e; 876int i; 877... 878switch (e) 879{ 880 case A: i += 1; break; 881 case B: i += 2; break; 882 case C: i += 3; break; 883} 884</pre> 885<p>with code like this:</p> 886<pre class="programlisting"> 887enum E { A, B, C }; 888enum E e; 889enum E table[] = { 1, 2, 3 }; 890int i; 891... 892i += table[e]; 893</pre> 894<p> 895This is obviously a contrived example, but the basic principle applies in a 896wide variety of situations.</p> 897<p> 898In short, Cachegrind can tell you where some of the bottlenecks in your code 899are, but it can't tell you how to fix them. You have to work that out for 900yourself. But at least you have the information! 901</p> 902</div> 903<div class="sect1"> 904<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 905<a name="cg-manual.sim-details"></a>5.8.�Simulation Details</h2></div></div></div> 906<p> 907This section talks about details you don't need to know about in order to 908use Cachegrind, but may be of interest to some people. 909</p> 910<div class="sect2"> 911<div class="titlepage"><div><div><h3 class="title"> 912<a name="cache-sim"></a>5.8.1.�Cache Simulation Specifics</h3></div></div></div> 913<p>Specific characteristics of the cache simulation are as 914follows:</p> 915<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 916<li class="listitem"><p>Write-allocate: when a write miss occurs, the block 917 written to is brought into the D1 cache. Most modern caches 918 have this property.</p></li> 919<li class="listitem"> 920<p>Bit-selection hash function: the set of line(s) in the cache 921 to which a memory block maps is chosen by the middle bits 922 M--(M+N-1) of the byte address, where:</p> 923<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "> 924<li class="listitem"><p>line size = 2^M bytes</p></li> 925<li class="listitem"><p>(cache size / line size / associativity) = 2^N bytes</p></li> 926</ul></div> 927</li> 928<li class="listitem"><p>Inclusive LL cache: the LL cache typically replicates all 929 the entries of the L1 caches, because fetching into L1 involves 930 fetching into LL first (this does not guarantee strict inclusiveness, 931 as lines evicted from LL still could reside in L1). This is 932 standard on Pentium chips, but AMD Opterons, Athlons and Durons 933 use an exclusive LL cache that only holds 934 blocks evicted from L1. Ditto most modern VIA CPUs.</p></li> 935</ul></div> 936<p>The cache configuration simulated (cache size, 937associativity and line size) is determined automatically using 938the x86 CPUID instruction. If you have a machine that (a) 939doesn't support the CPUID instruction, or (b) supports it in an 940early incarnation that doesn't give any cache information, then 941Cachegrind will fall back to using a default configuration (that 942of a model 3/4 Athlon). Cachegrind will tell you if this 943happens. You can manually specify one, two or all three levels 944(I1/D1/LL) of the cache from the command line using the 945<code class="option">--I1</code>, 946<code class="option">--D1</code> and 947<code class="option">--LL</code> options. 948For cache parameters to be valid for simulation, the number 949of sets (with associativity being the number of cache lines in 950each set) has to be a power of two.</p> 951<p>On PowerPC platforms 952Cachegrind cannot automatically 953determine the cache configuration, so you will 954need to specify it with the 955<code class="option">--I1</code>, 956<code class="option">--D1</code> and 957<code class="option">--LL</code> options.</p> 958<p>Other noteworthy behaviour:</p> 959<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 960<li class="listitem"> 961<p>References that straddle two cache lines are treated as 962 follows:</p> 963<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; "> 964<li class="listitem"><p>If both blocks hit --> counted as one hit</p></li> 965<li class="listitem"><p>If one block hits, the other misses --> counted 966 as one miss.</p></li> 967<li class="listitem"><p>If both blocks miss --> counted as one miss (not 968 two)</p></li> 969</ul></div> 970</li> 971<li class="listitem"> 972<p>Instructions that modify a memory location 973 (e.g. <code class="computeroutput">inc</code> and 974 <code class="computeroutput">dec</code>) are counted as doing 975 just a read, i.e. a single data reference. This may seem 976 strange, but since the write can never cause a miss (the read 977 guarantees the block is in the cache) it's not very 978 interesting.</p> 979<p>Thus it measures not the number of times the data cache 980 is accessed, but the number of times a data cache miss could 981 occur.</p> 982</li> 983</ul></div> 984<p>If you are interested in simulating a cache with different 985properties, it is not particularly hard to write your own cache 986simulator, or to modify the existing ones in 987<code class="computeroutput">cg_sim.c</code>. We'd be 988interested to hear from anyone who does.</p> 989</div> 990<div class="sect2"> 991<div class="titlepage"><div><div><h3 class="title"> 992<a name="branch-sim"></a>5.8.2.�Branch Simulation Specifics</h3></div></div></div> 993<p>Cachegrind simulates branch predictors intended to be 994typical of mainstream desktop/server processors of around 2004.</p> 995<p>Conditional branches are predicted using an array of 16384 2-bit 996saturating counters. The array index used for a branch instruction is 997computed partly from the low-order bits of the branch instruction's 998address and partly using the taken/not-taken behaviour of the last few 999conditional branches. As a result the predictions for any specific 1000branch depend both on its own history and the behaviour of previous 1001branches. This is a standard technique for improving prediction 1002accuracy.</p> 1003<p>For indirect branches (that is, jumps to unknown destinations) 1004Cachegrind uses a simple branch target address predictor. Targets are 1005predicted using an array of 512 entries indexed by the low order 9 1006bits of the branch instruction's address. Each branch is predicted to 1007jump to the same address it did last time. Any other behaviour causes 1008a mispredict.</p> 1009<p>More recent processors have better branch predictors, in 1010particular better indirect branch predictors. Cachegrind's predictor 1011design is deliberately conservative so as to be representative of the 1012large installed base of processors which pre-date widespread 1013deployment of more sophisticated indirect branch predictors. In 1014particular, late model Pentium 4s (Prescott), Pentium M, Core and Core 10152 have more sophisticated indirect branch predictors than modelled by 1016Cachegrind. </p> 1017<p>Cachegrind does not simulate a return stack predictor. It 1018assumes that processors perfectly predict function return addresses, 1019an assumption which is probably close to being true.</p> 1020<p>See Hennessy and Patterson's classic text "Computer 1021Architecture: A Quantitative Approach", 4th edition (2007), Section 10222.3 (pages 80-89) for background on modern branch predictors.</p> 1023</div> 1024<div class="sect2"> 1025<div class="titlepage"><div><div><h3 class="title"> 1026<a name="cg-manual.annopts.accuracy"></a>5.8.3.�Accuracy</h3></div></div></div> 1027<p>Valgrind's cache profiling has a number of 1028shortcomings:</p> 1029<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 1030<li class="listitem"><p>It doesn't account for kernel activity -- the effect of system 1031 calls on the cache and branch predictor contents is ignored.</p></li> 1032<li class="listitem"><p>It doesn't account for other process activity. 1033 This is probably desirable when considering a single 1034 program.</p></li> 1035<li class="listitem"><p>It doesn't account for virtual-to-physical address 1036 mappings. Hence the simulation is not a true 1037 representation of what's happening in the 1038 cache. Most caches and branch predictors are physically indexed, but 1039 Cachegrind simulates caches using virtual addresses.</p></li> 1040<li class="listitem"><p>It doesn't account for cache misses not visible at the 1041 instruction level, e.g. those arising from TLB misses, or 1042 speculative execution.</p></li> 1043<li class="listitem"><p>Valgrind will schedule 1044 threads differently from how they would be when running natively. 1045 This could warp the results for threaded programs.</p></li> 1046<li class="listitem"> 1047<p>The x86/amd64 instructions <code class="computeroutput">bts</code>, 1048 <code class="computeroutput">btr</code> and 1049 <code class="computeroutput">btc</code> will incorrectly be 1050 counted as doing a data read if both the arguments are 1051 registers, eg:</p> 1052<pre class="programlisting"> 1053 btsl %eax, %edx</pre> 1054<p>This should only happen rarely.</p> 1055</li> 1056<li class="listitem"><p>x86/amd64 FPU instructions with data sizes of 28 and 108 bytes 1057 (e.g. <code class="computeroutput">fsave</code>) are treated as 1058 though they only access 16 bytes. These instructions seem to 1059 be rare so hopefully this won't affect accuracy much.</p></li> 1060</ul></div> 1061<p>Another thing worth noting is that results are very sensitive. 1062Changing the size of the executable being profiled, or the sizes 1063of any of the shared libraries it uses, or even the length of their 1064file names, can perturb the results. Variations will be small, but 1065don't expect perfectly repeatable results if your program changes at 1066all.</p> 1067<p>More recent GNU/Linux distributions do address space 1068randomisation, in which identical runs of the same program have their 1069shared libraries loaded at different locations, as a security measure. 1070This also perturbs the results.</p> 1071<p>While these factors mean you shouldn't trust the results to 1072be super-accurate, they should be close enough to be useful.</p> 1073</div> 1074</div> 1075<div class="sect1"> 1076<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 1077<a name="cg-manual.impl-details"></a>5.9.�Implementation Details</h2></div></div></div> 1078<p> 1079This section talks about details you don't need to know about in order to 1080use Cachegrind, but may be of interest to some people. 1081</p> 1082<div class="sect2"> 1083<div class="titlepage"><div><div><h3 class="title"> 1084<a name="cg-manual.impl-details.how-cg-works"></a>5.9.1.�How Cachegrind Works</h3></div></div></div> 1085<p>The best reference for understanding how Cachegrind works is chapter 3 of 1086"Dynamic Binary Analysis and Instrumentation", by Nicholas Nethercote. It 1087is available on the <a class="ulink" href="http://www.valgrind.org/docs/pubs.html" target="_top">Valgrind publications 1088page</a>.</p> 1089</div> 1090<div class="sect2"> 1091<div class="titlepage"><div><div><h3 class="title"> 1092<a name="cg-manual.impl-details.file-format"></a>5.9.2.�Cachegrind Output File Format</h3></div></div></div> 1093<p>The file format is fairly straightforward, basically giving the 1094cost centre for every line, grouped by files and 1095functions. It's also totally generic and self-describing, in the sense that 1096it can be used for any events that can be counted on a line-by-line basis, 1097not just cache and branch predictor events. For example, earlier versions 1098of Cachegrind didn't have a branch predictor simulation. When this was 1099added, the file format didn't need to change at all. So the format (and 1100consequently, cg_annotate) could be used by other tools.</p> 1101<p>The file format:</p> 1102<pre class="programlisting"> 1103file ::= desc_line* cmd_line events_line data_line+ summary_line 1104desc_line ::= "desc:" ws? non_nl_string 1105cmd_line ::= "cmd:" ws? cmd 1106events_line ::= "events:" ws? (event ws)+ 1107data_line ::= file_line | fn_line | count_line 1108file_line ::= "fl=" filename 1109fn_line ::= "fn=" fn_name 1110count_line ::= line_num ws? (count ws)+ 1111summary_line ::= "summary:" ws? (count ws)+ 1112count ::= num | "."</pre> 1113<p>Where:</p> 1114<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 1115<li class="listitem"><p><code class="computeroutput">non_nl_string</code> is any 1116 string not containing a newline.</p></li> 1117<li class="listitem"><p><code class="computeroutput">cmd</code> is a string holding the 1118 command line of the profiled program.</p></li> 1119<li class="listitem"><p><code class="computeroutput">event</code> is a string containing 1120 no whitespace.</p></li> 1121<li class="listitem"><p><code class="computeroutput">filename</code> and 1122 <code class="computeroutput">fn_name</code> are strings.</p></li> 1123<li class="listitem"><p><code class="computeroutput">num</code> and 1124 <code class="computeroutput">line_num</code> are decimal 1125 numbers.</p></li> 1126<li class="listitem"><p><code class="computeroutput">ws</code> is whitespace.</p></li> 1127</ul></div> 1128<p>The contents of the "desc:" lines are printed out at the top 1129of the summary. This is a generic way of providing simulation 1130specific information, e.g. for giving the cache configuration for 1131cache simulation.</p> 1132<p>More than one line of info can be presented for each file/fn/line number. 1133In such cases, the counts for the named events will be accumulated.</p> 1134<p>Counts can be "." to represent zero. This makes the files easier for 1135humans to read.</p> 1136<p>The number of counts in each 1137<code class="computeroutput">line</code> and the 1138<code class="computeroutput">summary_line</code> should not exceed 1139the number of events in the 1140<code class="computeroutput">event_line</code>. If the number in 1141each <code class="computeroutput">line</code> is less, cg_annotate 1142treats those missing as though they were a "." entry. This saves space. 1143</p> 1144<p>A <code class="computeroutput">file_line</code> changes the 1145current file name. A <code class="computeroutput">fn_line</code> 1146changes the current function name. A 1147<code class="computeroutput">count_line</code> contains counts that 1148pertain to the current filename/fn_name. A "fn=" 1149<code class="computeroutput">file_line</code> and a 1150<code class="computeroutput">fn_line</code> must appear before any 1151<code class="computeroutput">count_line</code>s to give the context 1152of the first <code class="computeroutput">count_line</code>s.</p> 1153<p>Each <code class="computeroutput">file_line</code> will normally be 1154immediately followed by a <code class="computeroutput">fn_line</code>. But it 1155doesn't have to be.</p> 1156<p>The summary line is redundant, because it just holds the total counts 1157for each event. But this serves as a useful sanity check of the data; if 1158the totals for each event don't match the summary line, something has gone 1159wrong.</p> 1160</div> 1161</div> 1162</div> 1163<div> 1164<br><table class="nav" width="100%" cellspacing="3" cellpadding="2" border="0" summary="Navigation footer"> 1165<tr> 1166<td rowspan="2" width="40%" align="left"> 1167<a accesskey="p" href="mc-manual.html"><<�4.�Memcheck: a memory error detector</a>�</td> 1168<td width="20%" align="center"><a accesskey="u" href="manual.html">Up</a></td> 1169<td rowspan="2" width="40%" align="right">�<a accesskey="n" href="cl-manual.html">6.�Callgrind: a call-graph generating cache and branch prediction profiler�>></a> 1170</td> 1171</tr> 1172<tr><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td></tr> 1173</table> 1174</div> 1175</body> 1176</html> 1177