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 62 Valgrind 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 67 hierarchy and (optionally) branch predictor. It simulates a machine with 68 independent first-level instruction and data caches (I1 and D1), backed by a 69 unified second-level cache (L2). This exactly matches the configuration of 70 many modern machines.</p> 71 <p>However, some modern machines have three or four levels of cache. For these 72 machines (in the cases where Cachegrind can auto-detect the cache 73 configuration) Cachegrind simulates the first-level and last-level caches. 74 The reason for this choice is that the last-level cache has the most influence on 75 runtime, as it masks accesses to main memory. Furthermore, the L1 caches 76 often have low associativity, so simulating them can detect cases where the 77 code interacts badly with this cache (eg. traversing a matrix column-wise 78 with the row length being a power of 2).</p> 79 <p>Therefore, Cachegrind always refers to the I1, D1 and LL (last-level) 80 caches.</p> 81 <p> 82 Cachegrind gathers the following statistics (abbreviations used for each statistic 83 is 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 110 accesses 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 115 function in the program. You can also annotate each line of source code in 116 the program with the counts that were caused directly by it.</p> 117 <p>On a modern machine, an L1 miss will typically cost 118 around 10 cycles, an LL miss can cost as much as 200 119 cycles, and a mispredicted branch costs in the region of 10 120 to 30 cycles. Detailed cache and branch profiling can be very useful 121 for understanding how your program interacts with the machine and thus how 122 to make it faster.</p> 123 <p>Also, since one instruction cache read is performed per 124 instruction executed, you can find out how many instructions are 125 executed 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 131 compile with debugging info (the 132 <code class="option">-g</code> option). But by contrast with 133 normal Valgrind use, you probably do want to turn 134 optimisation on, since you should profile your program as it will 135 be normally run.</p> 136 <p>Then, you need to run Cachegrind itself to gather the profiling 137 information, and then run cg_annotate to get a detailed presentation of that 138 information. As an optional intermediate step, you can use cg_merge to sum 139 together the outputs of multiple Cachegrind runs into a single file which 140 you then use as the input for cg_annotate. Alternatively, you can use 141 cg_diff to difference the outputs of two Cachegrind runs into a single file 142 which 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"> 148 valgrind --tool=cachegrind prog 149 </pre> 150 <p>The program will execute (slowly). Upon completion, 151 summary 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 168 first, giving the number of fetches made (this is the number of 169 instructions executed, which can be useful to know in its own 170 right), 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 173 to that of the instruction fetches, except that the values are 174 also 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 177 total).</p> 178 <p>Combined instruction and data figures for the LL cache 179 follow that. Note that the LL miss rate is computed relative to the total 180 number of memory accesses, not the number of L1 misses. I.e. it is 181 <code class="computeroutput">(ILmr + DLmr + DLmw) / (Ir + Dr + Dw)</code> 182 not 183 <code class="computeroutput">(ILmr + DLmr + DLmw) / (I1mr + D1mr + D1mw)</code> 184 </p> 185 <p>Branch prediction statistics are not collected by default. 186 To 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 192 more 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 195 can be changed with the <code class="option">--cachegrind-out-file</code> option. This 196 file is human-readable, but is intended to be interpreted by the 197 accompanying program cg_annotate, described in the next section.</p> 198 <p>The default <code class="computeroutput">.<pid></code> suffix 199 on the output file name serves two purposes. Firstly, it means you 200 don't have to rename old log files that you don't want to overwrite. 201 Secondly, and more importantly, it allows correct profiling with the 202 <code class="option">--trace-children=yes</code> option of 203 programs that spawn child processes.</p> 204 <p>The output file can be big, many megabytes for large applications 205 built 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, 211 it is worth widening your window to be at least 120-characters 212 wide 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 -------------------------------------------------------------------------------- 223 I1 cache: 65536 B, 64 B, 2-way associative 224 D1 cache: 65536 B, 64 B, 2-way associative 225 LL cache: 262144 B, 64 B, 8-way associative 226 Command: concord vg_to_ucode.c 227 Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 228 Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 229 Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 230 Threshold: 99% 231 Chosen for annotation: 232 Auto-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 281 program:</p> 282 <pre class="programlisting"> 283 -------------------------------------------------------------------------------- 284 Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw 285 -------------------------------------------------------------------------------- 286 27,742,716 276 275 10,955,517 21,905 3,987 4,474,773 19,280 19,098 PROGRAM TOTALS</pre> 287 <p> 288 These 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 -------------------------------------------------------------------------------- 293 Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function 294 -------------------------------------------------------------------------------- 295 8,821,482 5 5 2,242,702 1,621 73 1,794,230 0 0 getc.c:_IO_getc 296 5,222,023 4 4 2,276,334 16 12 875,959 1 1 concord.c:get_word 297 2,649,248 2 2 1,344,810 7,326 1,385 . . . vg_main.c:strcmp 298 2,521,927 2 2 591,215 0 0 179,398 0 0 concord.c:hash 299 2,242,740 2 2 1,046,612 568 22 448,548 0 0 ctype.c:tolower 300 1,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 314 is identified by a 315 <code class="computeroutput">file_name:function_name</code> pair. If 316 a column contains only a dot it means the function never performs 317 that event (e.g. the third row shows that 318 <code class="computeroutput">strcmp()</code> contains no 319 instructions that write to memory). The name 320 <code class="computeroutput">???</code> is used if the file name 321 and/or function name could not be determined from debugging 322 information. If most of the entries have the form 323 <code class="computeroutput">???:???</code> the program probably 324 wasn't compiled with <code class="option">-g</code>.</p> 325 <p>It is worth noting that functions will come both from 326 the profiled program (e.g. <code class="filename">concord.c</code>) 327 and 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 333 manually 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 336 produces 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 -------------------------------------------------------------------------------- 342 Ir 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 369 terminal is clearly useful.)</p> 370 <p>Each source file is clearly marked 371 (<code class="computeroutput">User-annotated source</code>) as 372 having been chosen manually for annotation. If the file was 373 found in one of the directories specified with the 374 <code class="option">-I</code>/<code class="option">--include</code> option, the directory 375 and file are both given.</p> 376 <p>Each line is annotated with its event counts. Events not 377 applicable for a line are represented by a dot. This is useful 378 for distinguishing between an event which cannot happen, and one 379 which can but did not.</p> 380 <p>Sometimes only a small section of a source file is 381 executed. To minimise uninteresting output, Cachegrind only shows 382 annotated lines and lines within a small distance of annotated 383 lines. Gaps are marked with the line numbers so you know which 384 part 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 391 controlled by the <code class="option">--context</code> 392 option.</p> 393 <p>To get automatic annotation, use the <code class="option">--auto=yes</code> option. 394 cg_annotate will automatically annotate every source file it can 395 find that is mentioned in the function-by-function summary. 396 Therefore, the files chosen for auto-annotation are affected by 397 the <code class="option">--sort</code> and 398 <code class="option">--threshold</code> options. Each 399 source file is clearly marked (<code class="computeroutput">Auto-annotated 400 source</code>) as being chosen automatically. Any 401 files that could not be found are mentioned at the end of the 402 output, eg:</p> 403 <pre class="programlisting"> 404 ------------------------------------------------------------------ 405 The 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 411 usually compiled with debugging information, but the source files 412 are often not present on a system. If a file is chosen for 413 annotation both manually and automatically, it 414 is marked as <code class="computeroutput">User-annotated 415 source</code>. Use the 416 <code class="option">-I</code>/<code class="option">--include</code> option to tell Valgrind where 417 to look for source files if the filenames found from the debugging 418 information 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, 421 e.g. 30 seconds or more. Also beware that auto-annotation can 422 produce 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 428 the assembly code generated for your C program. Sometimes this is 429 useful for understanding what is really happening when an 430 interesting line of C code is translated into multiple 431 instructions.</p> 432 <p>To do this, you just need to assemble your 433 <code class="computeroutput">.s</code> files with assembly-level debug 434 information. You can use compile with the <code class="option">-S</code> to compile C/C++ 435 programs 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 437 assembly 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 443 has 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>, 446 then the outputs from the parent and child will be intermingled in a single 447 output file, which will almost certainly make it unreadable by 448 cg_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 454 cg_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 526 rare.</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> 532 cg_merge is a simple program which 533 reads multiple profile files, as created by Cachegrind, merges them 534 together, and writes the results into another file in the same format. 535 You can then examine the merged results using 536 <code class="computeroutput">cg_annotate <filename></code>, as 537 described above. The merging functionality might be useful if you 538 want to aggregate costs over multiple runs of the same program, or 539 from a single parallel run with multiple instances of the same 540 program.</p> 541 <p> 542 cg_merge is invoked as follows: 543 </p> 544 <pre class="programlisting"> 545 cg_merge -o outputfile file1 file2 file3 ...</pre> 546 <p> 547 It reads and checks <code class="computeroutput">file1</code>, then read 548 and checks <code class="computeroutput">file2</code> and merges it into 549 the running totals, then the same with 550 <code class="computeroutput">file3</code>, etc. The final results are 551 written to <code class="computeroutput">outputfile</code>, or to standard 552 out if no output file is specified.</p> 553 <p> 554 Costs are summed on a per-function, per-line and per-instruction 555 basis. Because of this, the order in which the input files does not 556 matter, although you should take care to only mention each file once, 557 since any file mentioned twice will be added in twice.</p> 558 <p> 559 cg_merge does not attempt to check 560 that the input files come from runs of the same executable. It will 561 happily merge together profile files from completely unrelated 562 programs. It does however check that the 563 <code class="computeroutput">Events:</code> lines of all the inputs are 564 identical, so as to ensure that the addition of costs makes sense. 565 For example, it would be nonsensical for it to add a number indicating 566 D1 read references to a number from a different file indicating LL 567 write misses.</p> 568 <p> 569 A number of other syntax and sanity checks are done whilst reading the 570 inputs. cg_merge will stop and 571 attempt to print a helpful error message if any of the input files 572 fail 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> 578 cg_diff is a simple program which 579 reads two profile files, as created by Cachegrind, finds the difference 580 between them, and writes the results into another file in the same format. 581 You can then examine the merged results using 582 <code class="computeroutput">cg_annotate <filename></code>, as 583 described above. This is very useful if you want to measure how a change to 584 a program affected its performance. 585 </p> 586 <p> 587 cg_diff is invoked as follows: 588 </p> 589 <pre class="programlisting"> 590 cg_diff file1 file2</pre> 591 <p> 592 It reads and checks <code class="computeroutput">file1</code>, then read 593 and checks <code class="computeroutput">file2</code>, then computes the 594 difference (effectively <code class="computeroutput">file1</code> - 595 <code class="computeroutput">file2</code>). The final results are written to 596 standard output.</p> 597 <p> 598 Costs are summed on a per-function basis. Per-line costs are not summed, 599 because doing so is too difficult. For example, consider differencing two 600 profiles, one from a single-file program A, and one from the same program A 601 where a single blank line was inserted at the top of the file. Every single 602 per-line count has changed. In comparison, the per-function counts have not 603 changed. The per-function count differences are still very useful for 604 determining differences between programs. Note that because the result is 605 the difference of two profiles, many of the counts will be negative; this 606 indicates that the counts for the relevant function are fewer in the second 607 version than those in the first version.</p> 608 <p> 609 cg_diff does not attempt to check 610 that the input files come from runs of the same executable. It will 611 happily merge together profile files from completely unrelated 612 programs. It does however check that the 613 <code class="computeroutput">Events:</code> lines of all the inputs are 614 identical, so as to ensure that the addition of costs makes sense. 615 For example, it would be nonsensical for it to add a number indicating 616 D1 read references to a number from a different file indicating LL 617 write misses.</p> 618 <p> 619 A number of other syntax and sanity checks are done whilst reading the 620 inputs. cg_diff will stop and 621 attempt to print a helpful error message if any of the input files 622 fail these checks.</p> 623 <p> 624 Sometimes you will want to compare Cachegrind profiles of two versions of a 625 program 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 628 slightly different to the first. A straight comparison of the two will not 629 be 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 633 version.</p> 634 <p> 635 When this happens, you can use the <code class="option">--mod-filename</code> option. 636 Its argument is a Perl search-and-replace expression that will be applied 637 to all the filenames in both Cachegrind output files. It can be used to 638 remove minor differences in filenames. For example, the option 639 <code class="option">--mod-filename='s/version[0-9]/versionN/'</code> will suffice for 640 this case.</p> 641 <p> 642 Similarly, sometimes compilers auto-generate certain functions and give them 643 randomized names. For example, GCC sometimes auto-generates functions with 644 names like <code class="function">T.1234</code>, and the suffixes vary from build to 645 build. You can use the <code class="option">--mod-funcname</code> option to remove 646 small 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> 829 Cachegrind gives you lots of information, but acting on that information 830 isn't always easy. Here are some rules of thumb that we have found to be 831 useful.</p> 832 <p> 833 First of all, the global hit/miss counts and miss rates are not that useful. 834 If you have multiple programs or multiple runs of a program, comparing the 835 numbers might identify if any are outliers and worthy of closer 836 investigation. Otherwise, they're not enough to act on.</p> 837 <p> 838 The function-by-function counts are more useful to look at, as they pinpoint 839 which functions are causing large numbers of counts. However, beware that 840 inlining can make these counts misleading. If a function 841 <code class="function">f</code> is always inlined, counts will be attributed to the 842 functions it is inlined into, rather than itself. However, if you look at 843 the line-by-line annotations for <code class="function">f</code> you'll see the 844 counts that belong to <code class="function">f</code>. (This is hard to avoid, it's 845 how the debug info is structured.) So it's worth looking for large numbers 846 in the line-by-line annotations.</p> 847 <p> 848 The line-by-line source code annotations are much more useful. In our 849 experience, the best place to start is by looking at the 850 <code class="computeroutput">Ir</code> numbers. They simply measure how many 851 instructions were executed for each line, and don't include any cache 852 information, but they can still be very useful for identifying 853 bottlenecks.</p> 854 <p> 855 After that, we have found that LL misses are typically a much bigger source 856 of slow-downs than L1 misses. So it's worth looking for any snippets of 857 code 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 862 not always easy to work out how to improve things. You need to have a 863 reasonable understanding of how caches work, the principles of locality, and 864 your program's data access patterns. Improving things may require 865 redesigning a data structure, for example.</p> 866 <p> 867 Looking at the <code class="computeroutput">Bcm</code> and 868 <code class="computeroutput">Bim</code> misses can also be helpful. 869 In particular, <code class="computeroutput">Bim</code> misses are often caused 870 by <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. 872 For example, you might replace code like this:</p> 873 <pre class="programlisting"> 874 enum E { A, B, C }; 875 enum E e; 876 int i; 877 ... 878 switch (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"> 887 enum E { A, B, C }; 888 enum E e; 889 enum E table[] = { 1, 2, 3 }; 890 int i; 891 ... 892 i += table[e]; 893 </pre> 894 <p> 895 This is obviously a contrived example, but the basic principle applies in a 896 wide variety of situations.</p> 897 <p> 898 In short, Cachegrind can tell you where some of the bottlenecks in your code 899 are, but it can't tell you how to fix them. You have to work that out for 900 yourself. 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> 907 This section talks about details you don't need to know about in order to 908 use 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 914 follows:</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, 937 associativity and line size) is determined automatically using 938 the x86 CPUID instruction. If you have a machine that (a) 939 doesn't support the CPUID instruction, or (b) supports it in an 940 early incarnation that doesn't give any cache information, then 941 Cachegrind will fall back to using a default configuration (that 942 of a model 3/4 Athlon). Cachegrind will tell you if this 943 happens. 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. 948 For cache parameters to be valid for simulation, the number 949 of sets (with associativity being the number of cache lines in 950 each set) has to be a power of two.</p> 951 <p>On PowerPC platforms 952 Cachegrind cannot automatically 953 determine the cache configuration, so you will 954 need 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 985 properties, it is not particularly hard to write your own cache 986 simulator, or to modify the existing ones in 987 <code class="computeroutput">cg_sim.c</code>. We'd be 988 interested 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 994 typical of mainstream desktop/server processors of around 2004.</p> 995 <p>Conditional branches are predicted using an array of 16384 2-bit 996 saturating counters. The array index used for a branch instruction is 997 computed partly from the low-order bits of the branch instruction's 998 address and partly using the taken/not-taken behaviour of the last few 999 conditional branches. As a result the predictions for any specific 1000 branch depend both on its own history and the behaviour of previous 1001 branches. This is a standard technique for improving prediction 1002 accuracy.</p> 1003 <p>For indirect branches (that is, jumps to unknown destinations) 1004 Cachegrind uses a simple branch target address predictor. Targets are 1005 predicted using an array of 512 entries indexed by the low order 9 1006 bits of the branch instruction's address. Each branch is predicted to 1007 jump to the same address it did last time. Any other behaviour causes 1008 a mispredict.</p> 1009 <p>More recent processors have better branch predictors, in 1010 particular better indirect branch predictors. Cachegrind's predictor 1011 design is deliberately conservative so as to be representative of the 1012 large installed base of processors which pre-date widespread 1013 deployment of more sophisticated indirect branch predictors. In 1014 particular, late model Pentium 4s (Prescott), Pentium M, Core and Core 1015 2 have more sophisticated indirect branch predictors than modelled by 1016 Cachegrind. </p> 1017 <p>Cachegrind does not simulate a return stack predictor. It 1018 assumes that processors perfectly predict function return addresses, 1019 an assumption which is probably close to being true.</p> 1020 <p>See Hennessy and Patterson's classic text "Computer 1021 Architecture: A Quantitative Approach", 4th edition (2007), Section 1022 2.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 1028 shortcomings:</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. 1062 Changing the size of the executable being profiled, or the sizes 1063 of any of the shared libraries it uses, or even the length of their 1064 file names, can perturb the results. Variations will be small, but 1065 don't expect perfectly repeatable results if your program changes at 1066 all.</p> 1067 <p>More recent GNU/Linux distributions do address space 1068 randomisation, in which identical runs of the same program have their 1069 shared libraries loaded at different locations, as a security measure. 1070 This also perturbs the results.</p> 1071 <p>While these factors mean you shouldn't trust the results to 1072 be 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> 1079 This section talks about details you don't need to know about in order to 1080 use 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 1087 is available on the <a class="ulink" href="http://www.valgrind.org/docs/pubs.html" target="_top">Valgrind publications 1088 page</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 1094 cost centre for every line, grouped by files and 1095 functions. It's also totally generic and self-describing, in the sense that 1096 it can be used for any events that can be counted on a line-by-line basis, 1097 not just cache and branch predictor events. For example, earlier versions 1098 of Cachegrind didn't have a branch predictor simulation. When this was 1099 added, the file format didn't need to change at all. So the format (and 1100 consequently, cg_annotate) could be used by other tools.</p> 1101 <p>The file format:</p> 1102 <pre class="programlisting"> 1103 file ::= desc_line* cmd_line events_line data_line+ summary_line 1104 desc_line ::= "desc:" ws? non_nl_string 1105 cmd_line ::= "cmd:" ws? cmd 1106 events_line ::= "events:" ws? (event ws)+ 1107 data_line ::= file_line | fn_line | count_line 1108 file_line ::= "fl=" filename 1109 fn_line ::= "fn=" fn_name 1110 count_line ::= line_num ws? (count ws)+ 1111 summary_line ::= "summary:" ws? (count ws)+ 1112 count ::= 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 1129 of the summary. This is a generic way of providing simulation 1130 specific information, e.g. for giving the cache configuration for 1131 cache simulation.</p> 1132 <p>More than one line of info can be presented for each file/fn/line number. 1133 In 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 1135 humans 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 1139 the number of events in the 1140 <code class="computeroutput">event_line</code>. If the number in 1141 each <code class="computeroutput">line</code> is less, cg_annotate 1142 treats those missing as though they were a "." entry. This saves space. 1143 </p> 1144 <p>A <code class="computeroutput">file_line</code> changes the 1145 current file name. A <code class="computeroutput">fn_line</code> 1146 changes the current function name. A 1147 <code class="computeroutput">count_line</code> contains counts that 1148 pertain 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 1152 of the first <code class="computeroutput">count_line</code>s.</p> 1153 <p>Each <code class="computeroutput">file_line</code> will normally be 1154 immediately followed by a <code class="computeroutput">fn_line</code>. But it 1155 doesn't have to be.</p> 1156 <p>The summary line is redundant, because it just holds the total counts 1157 for each event. But this serves as a useful sanity check of the data; if 1158 the totals for each event don't match the summary line, something has gone 1159 wrong.</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
