Calltree: a call-graph cache profiler

Detailed technical documentation on how Calltree works is available here. If you want to know how to use it, you only need to read this page.

1. Purpose

2. Usage

2.1 Basics

calltree [calltree options] program [program parameters]

This will collect information

1. on memory accesses of your program, and if an access can be satisfied by loading from 1st/2nd level cache,
2. on the calls made in your program among the functions executed.

If you are only interested the first item, it's enough to use the Cachegrind skin from Valgrind. If you are only interested in the second item, use Calltree with option "--simulate-cache=no". This will give instruction read accesses only. But it significantly speeds up the profiling typically by a factor of 2 or 3.

2.2 Multiple dumps from one program run

The generated dump files are named

cachegrind.out.pid[.part][-threadID]

There are different ways to generate multiple profile dumps while a program is running under supervision of Calltree. Still, all methods trigger the same action "dump all profile information since last dump or program start, and zero cost counters afterwards". To allow for zeroing cost counters without dumping, there exists a second action "zero all cost counters now". The different methods are:

• Dump on program termination. This method is the standard way and doesn't need any special action from your side.

• Spontaneous, interactive dumping. To send commands to a running profile run, you create a file named "cachegrind.cmd" in the current working directory of the profiled process. At the moment, only the dump action/command is supported. For this, the pure existence of the file is enough.

  Thus, execute "touch cachegrind.cmd" to force creation of a new dump file. When the dump is finished, the command file is removed. Note that the program must be running for detection of the file. So, for a GUI application, resize the window or for a server send a request.

  If you are using KCachegrind for browsing of profile information, you can use the toolbar button "Force dump". This will create the file "cachegrind.cmd" and will trigger a reload after the dump is written.

• Periodic dumping after execution of a specified number of basic blocks. For this, use the command line option --dumps=count. The resultion of the internal basic block counter of Valgrind is only rough, so you should at least specify a interval of 50000 basic blocks.
• Dumping at enter/leave of all functions whose name starts with funcprefix. Use option --dump-before=funcprefix and --dump-after=funcprefix). To zero cost counters before entering a function, use --zero-before=funcprefix. The prefix method for specifying function names was choosen to ease the use with C++: you don't have to specify full signatures.

  You can specify these options multiple times for different function prefixes.

• Program controlled dumping. Put "#include <valgrind/calltree.h>" into your source and add "CALLTREE_DUMP_STATS;" when you want a dump to happen. Use "CALLTREE_ZERO_STATS;" to only zero cost centers.

  In Valgrind terminology, this way is called "Client requests". The given macros generate a special instruction pattern with no effect at all (i.e. a NOP). Only when run under Valgrind (or Calltree), the CPU simulation engine detects the special instruction pattern and triggers special actions like the ones described above.

2.3 Limiting range of event collection

2.4 Avoiding cycles

If a call chain goes multiple times around inside of a cycle, you can't distinguish costs coming from the first round or the second. Thus, it makes no sense to attach any cost to a call among function in one cycle: if "A > B" appears multiple times in a call chain, you have no way to partition the one big sum of all appearances of "A > B". Thus, for profile data presentation, all functions of a cycle are seen as one big virtual function.

Unfortunately, if you have an application using some callback mechanism (like any GUI program), or even with normal polymorphism (as in OO languages like C++), it's quite possible to get large cycles. As it is often impossible to say anything about performance behaviour inside of cycles, it is useful to introduce some mechanisms to avoid cycles in call graphs at all. This is done by treating the same function as different functions depending on the current execution context by giving them different names, or by ignoring calls to functions at all.

There is an option to ignore calls to a function with "--fn-skip=funcprefix". E.g., you usually don't want to see the trampoline functions in the PLT sections for calls to functions in shared libraries. You can see the difference if you profile with "--skip-plt=no". If a call is ignored, cost events happening will be attached to the enclosing function.

If you have a recursive function, you can distinguish the first 10 recursion levels by specifying "--fn-recursion10=funcprefix". Or for all functions with "fn-recursion=10", but this will give you much bigger profile dumps. In the profile data, you will see the recursion levels of "func" as the different functions with names "func", "func'2", "func'3" and so on.

If you have call chains "A > B > C" and "A > C > B" in your program, you usually get a "false" cycle "B <> C". Use "--fn-caller2=B --fn-caller2=C", and functions "B" and "C" will be treated as different functions depending on the direct caller. Using the apostrophe for appending this "context" to the function name, you get "A > B'A > C'B" and "A > C'A > B'C", and there will be no cycle. Use "--fn-callers=3" to get a 2-caller depencendy for all functions. Again, this will multiplicate the profile data size.

3. Command line option reference

Specify another base name for the dump file names. This defaults to "cachegrind.out". To distinguish different profile runs of the same application, there is ".<pid>" appended to the base dump file name with <pid> being the process ID of the profile run (with multiple dumps happening, the file name is modified further; see below).

This option is especially usefull if your application changes its working directory. Usually, the dump file is generated in the current working directory of the application at program termination. By giving an absolute path with the base specification, you can force a fixed directory for the dump files.

Write each dump into separate file.

Specify if you want to do full cache simulation. Default is yes. If you say no, only instruction read accesses will be profiled. This typically makes the execution at least twice as fast.

Note however, that estimating of how much real time your program will need only by using the instruction read counts is impossible. Use it if you want to find out how many times different functions are called and there call relation.

Specify whether event collection is switched on at beginning of the profile run. This defaults to yes.

To only look at parts of your program, you have two possibilities:

• Zero event counters before entering the program part you want to profile, and dump the event counters to a file after leaving that program part.
• Switch on/off collection state as needed to only see event counters happening while inside of the program part you want to profile.
The second option can be used if the programm part you want to profile is called many times. Option 1, i.e. creating a lot of dumps is not practically here.

Collection state can be toggled at entering and leaving of a given function with option --toggle-collect=<function>. For this, collection state should be switched off at the beginning. Note that the specification of --toggle-collect implicitly sets --collect-state=no.

Collection state can be toggled also by using a Valgrind User Request in your application. For this, include valgrind/calltree.h and specify the macro CALLTREE_TOGGLE_COLLECT at the needed positions. This only will have any effect if run under supervision of the Calltree skin.

Ignore calls to/from PLT sections. Defaults to yes.