Labs / practice
CPU profiling and flame graphs with perf
Profile a C program with perf stat, perf record, and a flame graph; confirm the hotspot and prove the fix.
On this page
- Before you start
- 1. The program
- 2. Measure before profiling
- 3. Record samples
- 4. Read the report: self time first
- 5. Read the report: children and call paths
- 6. Draw a flame graph
- 7. Look at the hot instructions
- 8. Form a hypothesis and test it before fixing
- 9. Fix it and measure again
- 10. Troubleshooting
- What you practised
- Sources
Find out where a C program spends its CPU time, starting from nothing more than "it is slow". You will measure it with time and perf stat, sample it with perf record, read the report two ways, draw a flame graph, look at the hot instructions, fix the problem, and prove the fix with the same tools.
The program contains a deliberate mistake: it searches a sorted array linearly for every query, which makes the lookup stage quadratic. The point is not the bug, which you can see in the source, but learning how the tools reveal it when you cannot.
Before you start#
You need Linux on x86-64 or arm64, GCC or Clang, perf matching your kernel, and Git to download the flame graph scripts. Read performance analysis from zero for installation and permissions. Hardware counters may be missing in containers and some virtual machines; the steps that need them say so, and the rest still works with the software clock.
mkdir -p cpu-profile && cd cpu-profile
uname -r > env.txt
perf --version >> env.txt
cat /proc/sys/kernel/perf_event_paranoid >> env.txt1. The program#
Save this as hotspot.c. It has four stages, each in its own non-inlined function so that every stage gets a name in the profile. It also measures each stage with its own clock and prints the times to standard error: you will compare perf's view with the program's own view.
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
static double now_ms(void) {
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return ts.tv_sec * 1e3 + ts.tv_nsec / 1e6;
}
/* A tiny deterministic generator: every run performs the same work. */
static unsigned next_value(unsigned *state) {
*state = *state * 1103515245u + 12345u;
return *state >> 8;
}
__attribute__((noinline)) void fill_ids(unsigned *ids, size_t n) {
unsigned state = 42;
for (size_t i = 0; i < n; i++)
ids[i] = next_value(&state);
}
static int compare_unsigned(const void *a, const void *b) {
unsigned x = *(const unsigned *)a, y = *(const unsigned *)b;
return (x > y) - (x < y);
}
__attribute__((noinline)) void sort_ids(unsigned *ids, size_t n) {
qsort(ids, n, sizeof ids[0], compare_unsigned);
}
/* Slow version: scans the array from the start for every key. */
__attribute__((noinline)) long find_linear(const unsigned *ids, size_t n, unsigned key) {
for (size_t i = 0; i < n; i++)
if (ids[i] == key)
return (long)i;
return -1;
}
/* Fixed version: the array is already sorted, so binary search is enough. */
__attribute__((noinline)) long find_binary(const unsigned *ids, size_t n, unsigned key) {
size_t lo = 0, hi = n;
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (ids[mid] < key) lo = mid + 1;
else hi = mid;
}
return (lo < n && ids[lo] == key) ? (long)lo : -1;
}
__attribute__((noinline)) unsigned long lookup_all(const unsigned *ids, size_t n, int fixed) {
unsigned state = 7;
unsigned long found = 0;
for (size_t q = 0; q < n; q++) {
/* Odd queries ask for a key that exists; even queries use a fresh value. */
unsigned key = (q % 2) ? ids[(q * 7919) % n] : next_value(&state);
long at = fixed ? find_binary(ids, n, key) : find_linear(ids, n, key);
if (at >= 0)
found++;
}
return found;
}
__attribute__((noinline)) unsigned long checksum(const unsigned *ids, size_t n, int rounds) {
unsigned long sum = 0;
for (int r = 0; r < rounds; r++)
for (size_t i = 0; i < n; i++)
sum = sum * 31 + (ids[i] ^ (unsigned)r);
return sum;
}
int main(int argc, char **argv) {
size_t n = argc > 1 ? strtoul(argv[1], NULL, 10) : 40000;
int fixed = argc > 2 && strcmp(argv[2], "fixed") == 0;
unsigned *ids = malloc(n * sizeof *ids);
if (n == 0 || !ids) {
fprintf(stderr, "usage: %s [count>0] [slow|fixed]\n", argv[0]);
return 2;
}
double t0 = now_ms();
fill_ids(ids, n);
double t1 = now_ms();
sort_ids(ids, n);
double t2 = now_ms();
unsigned long found = lookup_all(ids, n, fixed);
double t3 = now_ms();
unsigned long sum = checksum(ids, n, 2000);
double t4 = now_ms();
printf("mode=%s n=%zu found=%lu checksum=%lu\n", fixed ? "fixed" : "slow", n, found, sum);
fprintf(stderr, "fill=%.1fms sort=%.1fms lookup=%.1fms checksum=%.1fms\n",
t1 - t0, t2 - t1, t3 - t2, t4 - t3);
free(ids);
return 0;
}Build an optimized binary that keeps debug information and frame pointers:
gcc -std=c11 -Wall -Wextra -O2 -g -fno-omit-frame-pointer hotspot.c -o hotspot-O2 keeps the build realistic. -g lets perf map addresses to function names and source lines. -fno-omit-frame-pointer keeps the frame-pointer chain that perf's default call-graph mode walks.
2. Measure before profiling#
time ./hotspotThe output has the shape:
fill=0.1ms sort=3.3ms lookup=318.6ms checksum=58.7ms
mode=slow n=40000 found=20051 checksum=7322226836377315584
real 0m0.39s
user 0m0.38s
sys 0m0.00sThese numbers come from one reference run on a different machine; yours will differ with the CPU and operating system. Three things should hold everywhere:
found=20051and the checksum are identical on every run and in both modes: they are the correctness check for the fix.realis close touser: one thread was busy the whole time. This is an on-CPU problem, so a CPU profiler is the right tool.- The program's own timer says
lookupdominates. Keep that number; perf should agree with it.
Now count events with perf stat, repeating five times to see the variation:
perf stat -r 5 ./hotspot > /dev/nullRead these lines in the output:
task-clockandCPUs utilized: about 1.0 CPUs utilized confirms a single busy thread.context-switchesandpage-faults: small numbers. The program is not waiting or allocating much.cycles,instructions, andinsn per cycle: the hardware view. If they show<not supported>, your environment does not expose the PMU; continue anyway.+- x.xx%after each value: the run-to-run variation. A later improvement must be larger than this.
3. Record samples#
perf record -F 999 -g -o slow.data ./hotspot-F 999asks for about 999 samples per second. The program runs for less than half a second; 99 Hz would give only a few dozen samples.-grecords the call chain at each sample.-o slow.datanames the output file so you can keep several captures.
perf prints how many samples it wrote. Fewer than a hundred samples is too few to trust small percentages; increase -F or run a longer workload (./hotspot 80000).
If perf refuses to run, check perf_event_paranoid and try with sudo. If it warns that kernel symbols are restricted, you will see [k] entries without names; that does not affect this user-space exercise.
4. Read the report: self time first#
perf report -i slow.data --stdio --no-children | head -n 40--no-children sorts functions by self samples: the percentage of samples in which that function's own instructions were executing. Expect find_linear at the top with a large majority, followed by checksum, and small entries for qsort internals and compare_unsigned.
Check perf against the program: lookup took roughly 85 % of the program's own total in the reference run, and find_linear should hold a similar share of samples. The two measurements are independent (a clock inside the program versus interrupts from the kernel); agreement makes the finding much stronger than either alone.
5. Read the report: children and call paths#
perf report -i slow.data --stdio --children | head -n 60With --children, each function also gets the samples of everything it called. main is now near 100 % because everything runs under it, and lookup_all has its own small self share plus the large share of find_linear below it. Expand the call graph lines under find_linear and confirm the path main → lookup_all → find_linear.
Use the two views for two questions:
| View | Answers |
|---|---|
self (--no-children) |
which instructions burn the CPU? |
children (--children) |
which higher-level operation is expensive, including everything it calls? |
6. Draw a flame graph#
A flame graph puts every sampled stack side by side: the x-axis is the share of samples (not time order), the y-axis is stack depth, and the width of a box is how often that function was on the stack.
git clone --depth 1 https://github.com/brendangregg/FlameGraph
perf script -i slow.data > slow.perf
FlameGraph/stackcollapse-perf.pl slow.perf > slow.folded
FlameGraph/flamegraph.pl slow.folded > slow.svgOpen slow.svg in a browser; it is interactive, so you can click a box to zoom in. You should see a wide find_linear plateau above lookup_all, and a narrower checksum tower beside it. Wide top edges are where the CPU time is spent.
slow.folded is plain text: one line per unique stack, frames separated by ;, followed by a sample count. Reading a few lines shows exactly what the picture is drawn from:
sort -t' ' -k2 -nr slow.folded | head -n 5Recent perf versions can also produce a flame graph directly with perf script report flamegraph; that command depends on your perf build and may need extra Python packages.
7. Look at the hot instructions#
perf annotate -i slow.data --stdio -s find_linear | head -n 40perf prints the disassembly of find_linear with the percentage of samples that landed on each instruction. Expect most samples on a short loop: a load from the array, a compare with the key, a conditional jump back. Samples usually appear on or just after the instruction that was slow to complete, not always on the exact one; read the loop as a whole. The assembly reading guide explains the instructions.
The annotation confirms what kind of problem this is: the CPU is not stalled on something unusual, it is simply executing the loop body an enormous number of times. That is an algorithm problem, not a micro-optimization problem.
8. Form a hypothesis and test it before fixing#
Hypothesis: lookup time grows with the square of n, because each of n queries scans up to n elements. Prediction: doubling n should roughly quadruple lookup time, while checksum only doubles.
./hotspot 20000 > /dev/null
./hotspot 40000 > /dev/null
./hotspot 80000 > /dev/nullCompare the lookup= and checksum= values on standard error. If lookup grows about fourfold per doubling and checksum about twofold, the prediction holds. This test uses no profiler at all, which makes it an independent check.
9. Fix it and measure again#
The program contains the fix already: the array is sorted, so find_binary can be used. Run the fixed mode with the same tools:
./hotspot 40000 fixed
perf stat -r 5 ./hotspot 40000 fixed > /dev/null
perf record -F 999 -g -o fixed.data ./hotspot 40000 fixed
perf report -i fixed.data --stdio --no-children | head -n 20Check, in order:
found=andchecksum=are the same as in slow mode: the fix did not change the result.- Total time dropped by much more than the
perf statvariation. - In the new profile,
checksumis now at the top. Removing one bottleneck reveals the next; whether it is worth optimizing depends on your goal.
Compare the two captures directly:
perf diff slow.data fixed.data | head -n 30perf diff shows percentage shares. checksum grows in share although its own time did not change; the total got smaller. Always read shares together with absolute time from perf stat or the program's own timers.
10. Troubleshooting#
| Symptom | Cause | Fix |
|---|---|---|
| functions appear as hexadecimal addresses | no symbols | build with -g, do not strip, keep the binary next to perf.data |
| call graph stops at the first frame | frame pointers missing | rebuild with -fno-omit-frame-pointer, or try perf record --call-graph dwarf |
find_linear missing from the report |
it was inlined | check noinline; inspect with nm hotspot | grep find_ |
<not supported> for cycles |
PMU not available (VM or container) | use -e task-clock; sampling falls back to a software clock |
| very few samples | short run | raise -F, increase n |
--call-graph dwarf copies part of the stack with every sample and unwinds it later using debug information. It works without frame pointers but produces much larger files.
What you practised#
- Decided on-CPU versus off-CPU from
realversususer. - Counted with
perf stat, sampled withperf record, read self and children views. - Drew and read a flame graph and the folded stacks it comes from.
- Confirmed a hotspot with an independent measurement and a scaling prediction.
- Measured a fix and interpreted percentage shifts correctly.
Continue with the first bpftrace lab to count and time specific events instead of sampling, and read execution analysis with perf for counter details and Intel PT.