Profile with Valgrind Callgrind and View in KCachegrind

Topic Overview

Deterministic Profiling Without Hardware Counters

Valgrind's Callgrind simulates every instruction, so results are repeatable across machines even when hardware perf events are blocked in containers. KCachegrind turns Callgrind output into inclusive and exclusive cost views. It is slower than perf by 10x/50x, but invaluable when you need exact call counts on a laptop without perf permissions.

Reading Inclusive vs Exclusive Cost

Inclusive cost counts time in a function plus everything it called. Exclusive cost is time spent inside the function body only. A high inclusive, low exclusive node means the callee is the real problem.

bashCopy
Loading…

• Run the smallest input that still exercises the slow path
• JIT and self-modifying code confuse simulators; test native C first
• Compare two callgrind.out files with callgrind_annotate --diff
• Massif pairs well when allocations correlate with hot paths

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will profile a C program with Callgrind and interpret the annotated output. This exercise asks you to name the top three inclusive-cost functions and explain what each one does in your call graph.

Your Task

Callgrind counts exact instructions (Ir) per function, plus how often each function calls each other one. callgrind_annotate and KCachegrind then show self cost (instructions in the function's own code) and inclusive cost (self plus everything it calls). Given self costs and call counts, compute inclusive costs, produce the annotate table, and show where a function's time goes among its callees.

Input

cCopy
Loading…

Functions are created on first mention with a self cost of 0.

Rules

• A callee's inclusive cost is shared among its callers in proportion to the number of calls: along an edge with C calls into callee g, the caller is charged round(incl(g) * C / calls_into(g)) (half up), where calls_into(g) sums all edges into g. Then incl(f) = self(f) + the charges for all of f's outgoing edges.
• If the call graph has a cycle (recursion), print annotate: recursion cycle detected (callgrind would merge it into a cycle group) (or callees: recursion cycle detected).
• annotate prints the program total (the sum of all self costs), then one row per function sorted by inclusive cost (descending, ties by name): inclusive and self costs with their percentages of the program total, and the number of calls into the function.
• callees NAME lists NAME's outgoing edges in input order, with the charged inclusive cost as a percentage of NAME's inclusive cost.
• Errors: fn NAME: rejected (negative cost), call A B: rejected (COUNT < 1), and callees NAME: unknown function.

Output

cCopy
Loading…

Table rows use "%9ld %3ld.%ld%% %8ld %3ld.%ld%% %6ld %s", and percentages are rounded half up to 1 decimal.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Compute inclusive costs with a memoised DFS over callees, detecting cycles with an "on stack" mark.
2. Split a shared callee's cost by call counts. This is the same approximation KCachegrind makes when it has no per-call-site data.

Hidden tests cover a helper shared by several callers, a deep call chain, a function with zero self cost, ties in the sort order, recursion, and an unknown function in callees.