|
Information Source Code Documentation Contact How to Help Gallery | |||||
Table of Contents To use this tool, you must specify
Cachegrind is a tool for finding places where programs interact badly with typical modern superscalar processors and run slowly as a result. In particular, it will do a cache simulation of your program, and optionally a branch-predictor simulation, and can then annotate your source line-by-line with the number of cache misses and branch mispredictions. The following statistics are collected:
On a modern machine, an L1 miss will typically cost around 10 cycles, an L2 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 improving the performance of your program. 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 and test coverage. Branch profiling is not enabled by default. To use it, you must
additionally specify First off, as for normal Valgrind use, you probably want to
compile with debugging info (the
The two steps are:
As an optional intermediate step, you can use the supplied cg_merge program to sum together the outputs of multiple Cachegrind runs, into a single file which you then use as the input for cg_annotate. These steps are described in detail in the following sections. Cachegrind simulates a machine with independent first level instruction and data caches (I1 and D1), backed by a unified second level cache (L2). This configuration is used by almost all modern machines. Some old Cyrix CPUs had a unified I and D L1 cache, but they are ancient history now. Specific characteristics of the simulation are as follows:
The cache configuration simulated (cache size,
associativity and line size) is determined automagically using
the CPUID instruction. If you have an old 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/L2) 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. To gather cache profiling information about the program
valgrind --tool=cachegrind ls -l 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== L2 misses: 275 ==31751== I1 miss rate: 0.0% ==31751== L2i 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== L2 misses: 23,085 ( 3,987 rd + 19,098 wr) ==31751== D1 miss rate: 0.2% ( 0.1% + 0.4%) ==31751== L2d miss rate: 0.1% ( 0.0% + 0.4%) ==31751== ==31751== L2 misses: 23,360 ( 4,262 rd + 19,098 wr) ==31751== L2 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 L2 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 L2 cache follow that. As well as printing summary information, Cachegrind also
writes line-by-line cache profiling information to a user-specified
file. By default this file is named
Things to note about the
The default Using command line options, you can manually specify the I1/D1/L2 cache configuration to simulate. For each cache, you can specify the size, associativity and line size. The size and line size are measured in bytes. The three items must be comma-separated, but with no spaces, eg: valgrind --tool=cachegrind --I1=65535,2,64 You can specify one, two or three of the I1/D1/L2 caches. Any level not manually specified will be simulated using the configuration found in the normal way (via the CPUID instruction for automagic cache configuration, or failing that, via defaults). Cache-simulation specific options are:
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 The output looks like this: -------------------------------------------------------------------------------- I1 cache: 65536 B, 64 B, 2-way associative D1 cache: 65536 B, 64 B, 2-way associative L2 cache: 262144 B, 64 B, 8-way associative Command: concord vg_to_ucode.c Events recorded: Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw Events shown: Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw Event sort order: Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw Threshold: 99% Chosen for annotation: Auto-annotation: on -------------------------------------------------------------------------------- Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw -------------------------------------------------------------------------------- 27,742,716 276 275 10,955,517 21,905 3,987 4,474,773 19,280 19,098 PROGRAM TOTALS -------------------------------------------------------------------------------- Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw 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 First up is a summary of the annotation options:
Then follows summary statistics for the whole
program. These are similar to the summary provided when running
Then follows function-by-function statistics. Each function
is identified by a
It is worth noting that functions will come both from
the profiled program (eg. There are two ways to annotate source files -- by choosing
them manually, or with the
--------------------------------------------------------------------------------
-- User-annotated source: concord.c
--------------------------------------------------------------------------------
Ir I1mr I2mr Dr D1mr D2mr Dw D1mw D2mw
[snip]
. . . . . . . . . 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 To get automatic annotation, run
------------------------------------------------------------------ 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. Valgrind's cache profiling has a number of shortcomings:
Another thing worth noting is that results are very sensitive. Changing the size of the 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, hopefully they should be close enough to be useful.
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. So, you've managed to profile your program with Cachegrind. Now what? What's the best way to actually act on the information it provides to speed up your program? Here are some rules of thumb that we have found to be useful. First of all, the global hit/miss rate numbers 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 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 L2 misses are typically a much bigger source of slow-downs than L1 misses. So it's worth looking for any snippets of code that cause a high proportion of the L2 misses. If you find any, it's still not always easy to work out how to improve things. You need to have a reasonable understanding of how caches work, the principles of locality, and your program's data access patterns. Improving things may require redesigning a data structure, for example. 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. 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. Total counts (eg. total cache accesses, total L1 misses) are calculated when traversing this structure rather than during execution, to save time; the cache simulation functions are called so often that even one or two extra adds can make a sizeable difference. 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, eg. 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 |
||||||
Copyright © 2000-2009 Valgrind Developers |
||||||
