|
Information Source Code Documentation Contact How to Help Gallery | |||||
Table of Contents
To use this tool, you must specify
Cachegrind simulates how your program interacts with a machine's cache hierarchy and (optionally) branch predictor. It simulates a machine with independent first-level instruction and data caches (I1 and D1), backed by a unified second-level cache (L2). This exactly matches the configuration of many modern machines. However, some modern machines have three or four levels of cache. For these machines (in the cases where Cachegrind can auto-detect the cache configuration) Cachegrind simulates the first-level and last-level caches. The reason for this choice is that the last-level cache has the most influence on runtime, as it masks accesses to main memory. Furthermore, the L1 caches often have low associativity, so simulating them can detect cases where the code interacts badly with this cache (eg. traversing a matrix column-wise with the row length being a power of 2). Therefore, Cachegrind always refers to the I1, D1 and LL (last-level) caches. Cachegrind gathers the following statistics (abbreviations used for each statistic is given in parentheses):
Note that D1 total accesses is given by
These statistics are presented for the entire program and for each function in the program. You can also annotate each line of source code in the program with the counts that were caused directly by it. On a modern machine, an L1 miss will typically cost around 10 cycles, an LL miss can cost as much as 200 cycles, and a mispredicted branch costs in the region of 10 to 30 cycles. Detailed cache and branch profiling can be very useful for understanding how your program interacts with the machine and thus how to make it faster. Also, since one instruction cache read is performed per instruction executed, you can find out how many instructions are executed per line, which can be useful for traditional profiling. First off, as for normal Valgrind use, you probably want to
compile with debugging info (the
Then, you need to run Cachegrind itself to gather the profiling information, and then run cg_annotate to get a detailed presentation of that information. As an optional intermediate step, you can use cg_merge to sum together the outputs of multiple Cachegrind runs into a single file which you then use as the input for cg_annotate. Alternatively, you can use cg_diff to difference the outputs of two Cachegrind runs into a single file which you then use as the input for cg_annotate. To run Cachegrind on a program valgrind --tool=cachegrind prog The program will execute (slowly). Upon completion, summary statistics that look like this will be printed: ==31751== I refs: 27,742,716 ==31751== I1 misses: 276 ==31751== LLi misses: 275 ==31751== I1 miss rate: 0.0% ==31751== LLi miss rate: 0.0% ==31751== ==31751== D refs: 15,430,290 (10,955,517 rd + 4,474,773 wr) ==31751== D1 misses: 41,185 ( 21,905 rd + 19,280 wr) ==31751== LLd misses: 23,085 ( 3,987 rd + 19,098 wr) ==31751== D1 miss rate: 0.2% ( 0.1% + 0.4%) ==31751== LLd miss rate: 0.1% ( 0.0% + 0.4%) ==31751== ==31751== LL misses: 23,360 ( 4,262 rd + 19,098 wr) ==31751== LL miss rate: 0.0% ( 0.0% + 0.4%) Cache accesses for instruction fetches are summarised
first, giving the number of fetches made (this is the number of
instructions executed, which can be useful to know in its own
right), the number of I1 misses, and the number of LL instruction
( Cache accesses for data follow. The information is similar
to that of the instruction fetches, except that the values are
also shown split between reads and writes (note each row's
Combined instruction and data figures for the LL cache
follow that. Note that the LL miss rate is computed relative to the total
number of memory accesses, not the number of L1 misses. I.e. it is
Branch prediction statistics are not collected by default.
To do so, add the option As well as printing summary information, Cachegrind also writes
more detailed profiling information to a file. By default this file is named
The default The output file can be big, many megabytes for large applications built with full debugging information. Before using cg_annotate, it is worth widening your window to be at least 120-characters wide if possible, as the output lines can be quite long. To get a function-by-function summary, run: cg_annotate <filename> on a Cachegrind output file. The first part of the output looks like this: -------------------------------------------------------------------------------- I1 cache: 65536 B, 64 B, 2-way associative D1 cache: 65536 B, 64 B, 2-way associative LL cache: 262144 B, 64 B, 8-way associative Command: concord vg_to_ucode.c Events recorded: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Events shown: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Event sort order: Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw Threshold: 99% Chosen for annotation: Auto-annotation: off This is a summary of the annotation options:
Then follows summary statistics for the whole program: -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw -------------------------------------------------------------------------------- 27,742,716 276 275 10,955,517 21,905 3,987 4,474,773 19,280 19,098 PROGRAM TOTALS These are similar to the summary provided when Cachegrind finishes running. Then comes function-by-function statistics: -------------------------------------------------------------------------------- Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function -------------------------------------------------------------------------------- 8,821,482 5 5 2,242,702 1,621 73 1,794,230 0 0 getc.c:_IO_getc 5,222,023 4 4 2,276,334 16 12 875,959 1 1 concord.c:get_word 2,649,248 2 2 1,344,810 7,326 1,385 . . . vg_main.c:strcmp 2,521,927 2 2 591,215 0 0 179,398 0 0 concord.c:hash 2,242,740 2 2 1,046,612 568 22 448,548 0 0 ctype.c:tolower 1,496,937 4 4 630,874 9,000 1,400 279,388 0 0 concord.c:insert 897,991 51 51 897,831 95 30 62 1 1 ???:??? 598,068 1 1 299,034 0 0 149,517 0 0 ../sysdeps/generic/lockfile.c:__flockfile 598,068 0 0 299,034 0 0 149,517 0 0 ../sysdeps/generic/lockfile.c:__funlockfile 598,024 4 4 213,580 35 16 149,506 0 0 vg_clientmalloc.c:malloc 446,587 1 1 215,973 2,167 430 129,948 14,057 13,957 concord.c:add_existing 341,760 2 2 128,160 0 0 128,160 0 0 vg_clientmalloc.c:vg_trap_here_WRAPPER 320,782 4 4 150,711 276 0 56,027 53 53 concord.c:init_hash_table 298,998 1 1 106,785 0 0 64,071 1 1 concord.c:create 149,518 0 0 149,516 0 0 1 0 0 ???:tolower@@GLIBC_2.0 149,518 0 0 149,516 0 0 1 0 0 ???:fgetc@@GLIBC_2.0 95,983 4 4 38,031 0 0 34,409 3,152 3,150 concord.c:new_word_node 85,440 0 0 42,720 0 0 21,360 0 0 vg_clientmalloc.c:vg_bogus_epilogue Each function
is identified by a
It is worth noting that functions will come both from
the profiled program (e.g. By default, all source code annotation is also shown. (Filenames to be
annotated can also by specified manually as arguments to cg_annotate, but this
is rarely needed.) For example, the output from running
--------------------------------------------------------------------------------
-- Auto-annotated source: concord.c
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
. . . . . . . . . void init_hash_table(char *file_name, Word_Node *table[])
3 1 1 . . . 1 0 0 {
. . . . . . . . . FILE *file_ptr;
. . . . . . . . . Word_Info *data;
1 0 0 . . . 1 1 1 int line = 1, i;
. . . . . . . . .
5 0 0 . . . 3 0 0 data = (Word_Info *) create(sizeof(Word_Info));
. . . . . . . . .
4,991 0 0 1,995 0 0 998 0 0 for (i = 0; i < TABLE_SIZE; i++)
3,988 1 1 1,994 0 0 997 53 52 table[i] = NULL;
. . . . . . . . .
. . . . . . . . . /* Open file, check it. */
6 0 0 1 0 0 4 0 0 file_ptr = fopen(file_name, "r");
2 0 0 1 0 0 . . . if (!(file_ptr)) {
. . . . . . . . . fprintf(stderr, "Couldn't open '%s'.\n", file_name);
1 1 1 . . . . . . exit(EXIT_FAILURE);
. . . . . . . . . }
. . . . . . . . .
165,062 1 1 73,360 0 0 91,700 0 0 while ((line = get_word(data, line, file_ptr)) != EOF)
146,712 0 0 73,356 0 0 73,356 0 0 insert(data->;word, data->line, table);
. . . . . . . . .
4 0 0 1 0 0 2 0 0 free(data);
4 0 0 1 0 0 2 0 0 fclose(file_ptr);
3 0 0 2 0 0 . . . }
(Although column widths are automatically minimised, a wide terminal is clearly useful.) Each source file is clearly marked
( Each line is annotated with its event counts. Events not applicable for a line are represented by a dot. This is useful for distinguishing between an event which cannot happen, and one which can but did not. Sometimes only a small section of a source file is executed. To minimise uninteresting output, Cachegrind only shows annotated lines and lines within a small distance of annotated lines. Gaps are marked with the line numbers so you know which part of a file the shown code comes from, eg: (figures and code for line 704) -- line 704 ---------------------------------------- -- line 878 ---------------------------------------- (figures and code for line 878) The amount of context to show around annotated lines is
controlled by the Automatic annotation is enabled by default.
cg_annotate will automatically annotate every source file it can
find that is mentioned in the function-by-function summary.
Therefore, the files chosen for auto-annotation are affected by
the ------------------------------------------------------------------ The following files chosen for auto-annotation could not be found: ------------------------------------------------------------------ getc.c ctype.c ../sysdeps/generic/lockfile.c This is quite common for library files, since libraries are
usually compiled with debugging information, but the source files
are often not present on a system. If a file is chosen for
annotation both manually and automatically, it
is marked as Beware that cg_annotate can take some time to digest large
Valgrind can annotate assembly code programs too, or annotate the assembly code generated for your C program. Sometimes this is useful for understanding what is really happening when an interesting line of C code is translated into multiple instructions. To do this, you just need to assemble your
If your program forks, the child will inherit all the profiling data that has been gathered for the parent. If the output file format string (controlled by
There are a couple of situations in which cg_annotate issues warnings.
Some odd things that can occur during annotation:
This list looks long, but these cases should be fairly rare.
cg_merge is a simple program which
reads multiple profile files, as created by Cachegrind, merges them
together, and writes the results into another file in the same format.
You can then examine the merged results using
cg_merge is invoked as follows: cg_merge -o outputfile file1 file2 file3 ...
It reads and checks Costs are summed on a per-function, per-line and per-instruction basis. Because of this, the order in which the input files does not matter, although you should take care to only mention each file once, since any file mentioned twice will be added in twice.
cg_merge does not attempt to check
that the input files come from runs of the same executable. It will
happily merge together profile files from completely unrelated
programs. It does however check that the
A number of other syntax and sanity checks are done whilst reading the inputs. cg_merge will stop and attempt to print a helpful error message if any of the input files fail these checks.
cg_diff is a simple program which
reads two profile files, as created by Cachegrind, finds the difference
between them, and writes the results into another file in the same format.
You can then examine the merged results using
cg_diff is invoked as follows: cg_diff file1 file2
It reads and checks Costs are summed on a per-function basis. Per-line costs are not summed, because doing so is too difficult. For example, consider differencing two profiles, one from a single-file program A, and one from the same program A where a single blank line was inserted at the top of the file. Every single per-line count has changed. In comparison, the per-function counts have not changed. The per-function count differences are still very useful for determining differences between programs. Note that because the result is the difference of two profiles, many of the counts will be negative; this indicates that the counts for the relevant function are fewer in the second version than those in the first version.
cg_diff does not attempt to check
that the input files come from runs of the same executable. It will
happily merge together profile files from completely unrelated
programs. It does however check that the
A number of other syntax and sanity checks are done whilst reading the inputs. cg_diff will stop and attempt to print a helpful error message if any of the input files fail these checks.
Sometimes you will want to compare Cachegrind profiles of two versions of a
program that you have sitting side-by-side. For example, you might have
When this happens, you can use the
Similarly, sometimes compilers auto-generate certain functions and give them
randomized names. For example, GCC sometimes auto-generates functions with
names like Cachegrind-specific options are:
Cachegrind gives you lots of information, but acting on that information isn't always easy. Here are some rules of thumb that we have found to be useful. First of all, the global hit/miss counts and miss rates are not that useful. If you have multiple programs or multiple runs of a program, comparing the numbers might identify if any are outliers and worthy of closer investigation. Otherwise, they're not enough to act on.
The function-by-function counts are more useful to look at, as they pinpoint
which functions are causing large numbers of counts. However, beware that
inlining can make these counts misleading. If a function
The line-by-line source code annotations are much more useful. In our
experience, the best place to start is by looking at the
After that, we have found that LL misses are typically a much bigger source
of slow-downs than L1 misses. So it's worth looking for any snippets of
code with high
Looking at the
enum E { A, B, C };
enum E e;
int i;
...
switch (e)
{
case A: i += 1; break;
case B: i += 2; break;
case C: i += 3; break;
}
with code like this:
enum E { A, B, C };
enum E e;
int table[] = { 1, 2, 3 };
int i;
...
i += table[e];
This is obviously a contrived example, but the basic principle applies in a wide variety of situations. In short, Cachegrind can tell you where some of the bottlenecks in your code are, but it can't tell you how to fix them. You have to work that out for yourself. But at least you have the information! This section talks about details you don't need to know about in order to use Cachegrind, but may be of interest to some people. Specific characteristics of the cache simulation are as follows:
The cache configuration simulated (cache size,
associativity and line size) is determined automatically using
the x86 CPUID instruction. If you have a machine that (a)
doesn't support the CPUID instruction, or (b) supports it in an
early incarnation that doesn't give any cache information, then
Cachegrind will fall back to using a default configuration (that
of a model 3/4 Athlon). Cachegrind will tell you if this
happens. You can manually specify one, two or all three levels
(I1/D1/LL) of the cache from the command line using the
On PowerPC platforms
Cachegrind cannot automatically
determine the cache configuration, so you will
need to specify it with the
Other noteworthy behaviour:
If you are interested in simulating a cache with different
properties, it is not particularly hard to write your own cache
simulator, or to modify the existing ones in
Cachegrind simulates branch predictors intended to be typical of mainstream desktop/server processors of around 2004. Conditional branches are predicted using an array of 16384 2-bit saturating counters. The array index used for a branch instruction is computed partly from the low-order bits of the branch instruction's address and partly using the taken/not-taken behaviour of the last few conditional branches. As a result the predictions for any specific branch depend both on its own history and the behaviour of previous branches. This is a standard technique for improving prediction accuracy. For indirect branches (that is, jumps to unknown destinations) Cachegrind uses a simple branch target address predictor. Targets are predicted using an array of 512 entries indexed by the low order 9 bits of the branch instruction's address. Each branch is predicted to jump to the same address it did last time. Any other behaviour causes a mispredict. More recent processors have better branch predictors, in particular better indirect branch predictors. Cachegrind's predictor design is deliberately conservative so as to be representative of the large installed base of processors which pre-date widespread deployment of more sophisticated indirect branch predictors. In particular, late model Pentium 4s (Prescott), Pentium M, Core and Core 2 have more sophisticated indirect branch predictors than modelled by Cachegrind. Cachegrind does not simulate a return stack predictor. It assumes that processors perfectly predict function return addresses, an assumption which is probably close to being true. See Hennessy and Patterson's classic text "Computer Architecture: A Quantitative Approach", 4th edition (2007), Section 2.3 (pages 80-89) for background on modern branch predictors. Valgrind's cache profiling has a number of shortcomings:
Another thing worth noting is that results are very sensitive. Changing the size of the executable being profiled, or the sizes of any of the shared libraries it uses, or even the length of their file names, can perturb the results. Variations will be small, but don't expect perfectly repeatable results if your program changes at all. More recent GNU/Linux distributions do address space randomisation, in which identical runs of the same program have their shared libraries loaded at different locations, as a security measure. This also perturbs the results. While these factors mean you shouldn't trust the results to be super-accurate, they should be close enough to be useful. This section talks about details you don't need to know about in order to use Cachegrind, but may be of interest to some people. The best reference for understanding how Cachegrind works is chapter 3 of "Dynamic Binary Analysis and Instrumentation", by Nicholas Nethercote. It is available on the Valgrind publications page. The file format is fairly straightforward, basically giving the cost centre for every line, grouped by files and functions. It's also totally generic and self-describing, in the sense that it can be used for any events that can be counted on a line-by-line basis, not just cache and branch predictor events. For example, earlier versions of Cachegrind didn't have a branch predictor simulation. When this was added, the file format didn't need to change at all. So the format (and consequently, cg_annotate) could be used by other tools. The file format: file ::= desc_line* cmd_line events_line data_line+ summary_line desc_line ::= "desc:" ws? non_nl_string cmd_line ::= "cmd:" ws? cmd events_line ::= "events:" ws? (event ws)+ data_line ::= file_line | fn_line | count_line file_line ::= "fl=" filename fn_line ::= "fn=" fn_name count_line ::= line_num ws? (count ws)+ summary_line ::= "summary:" ws? (count ws)+ count ::= num | "." Where:
The contents of the "desc:" lines are printed out at the top of the summary. This is a generic way of providing simulation specific information, e.g. for giving the cache configuration for cache simulation. More than one line of info can be presented for each file/fn/line number. In such cases, the counts for the named events will be accumulated. Counts can be "." to represent zero. This makes the files easier for humans to read. The number of counts in each
A Each The summary line is redundant, because it just holds the total counts for each event. But this serves as a useful sanity check of the data; if the totals for each event don't match the summary line, something has gone wrong. |
||||||
Copyright © 2000-2022 Valgrind™ Developers |
||||||
