Performance Analysis
The USE method (Brendan Gregg): for every resource (CPU, memory, disk, network) check Utilization, Saturation (queueing) and Errors.
Concept
A Method, Not Guesswork Define the goal and metric: latency (p50/p99), throughput, CPU time, memory, energy.
Measure the whole system first: is the program CPU-bound, memory-bound, I/O-bound or waiting on locks?
Profile to find where time goes; optimize the biggest contributor.
Measure again under the same conditions.
The USE method (Brendan Gregg): for every resource (CPU, memory, disk, network) check Utilization, Saturation (queueing) and Errors.
Tools on Linux time, /usr/bin/time -v Wall-clock vs user vs system time, max RSS, page faults
top, htop, vmstat, iostat, pidstat Which resource is busy perf stat, perf record/report
Hardware counters (cycles, instructions, cache and branch misses), sampling profiles gprof (-pg) Classic function-level profile strace -c, ltrace Time in system and library calls
Valgrind (Callgrind, Cachegrind, Massif) Instruction-level and memory profiling (slow, precise) Visualize sampled call stacks eBPF tools (bcc, bpftrace) Low-overhead tracing inside the kernel
Amdahl's law (Module 4): the serial fraction limits speedup.
Gustafson's law: with more cores we usually solve bigger problems, so the parallel part grows.
Little's law: items in the system = arrival rate × time in the system (queues, thread pools, I/O depth).
Efficiency = speedup / number of threads; SMT threads share one core's execution units, so they add much less than a full core.
Why It Matters
Performance work without measurement wastes time and often makes code worse. The same method finds a slow SQL query, a lock-contended server and a control loop missing its deadline.
Syntax
/usr/bin/time -v ./prog
perf stat -e cycles,instructions,cache-misses,branch-misses ./prog
perf record -g ./prog && perf report
gcc -pg prog.c -o prog && ./prog && gprof -b prog gmon.outExample
29.1 Measuring parallel scaling 29.2 Profiling with gprof and measuring with time
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
/* CPU-bound work: count primes below LIMIT by trial division, split across T threads (interleaved) */
enum { LIMIT = 3000000 };
typedef struct { int id, threads; long count; } Job;
static int is_prime(int n)
{
if (n < 2) return 0;
for (int d = 2; (long)d * d <= n; d++) if (n % d == 0) return 0;
return 1;
}
static void *work(void *arg)
{
Job *j = arg;
/* chunks of 1000 numbers dealt out round-robin: every thread gets a similar mix of small and large n */
for (int base = j->id * 1000; base < LIMIT; base += j->threads * 1000)
for (int n = base; n < base + 1000 && n < LIMIT; n++) j->count += is_prime(n);
return NULL;
}
static double run(int threads, long *primes)
{
pthread_t t[16];
Job jobs[16];
struct timespec a, b;
clock_gettime(CLOCK_MONOTONIC, &a);
for (int i = 0; i < threads; i++) { jobs[i] = (Job){i, threads, 0}; pthread_create(&t[i], NULL, work, &jobs[i]); }
*primes = 0;
for (int i = 0; i < threads; i++) { pthread_join(t[i], NULL); *primes += jobs[i].count; }
clock_gettime(CLOCK_MONOTONIC, &b);
return (b.tv_sec - a.tv_sec) + (
…#include <stdio.h>
/* A program with an obvious hot spot, for a sampling profiler */
__attribute__((noinline)) long checksum(const unsigned char *d, long n)
{
long s = 0;
for (long r = 0; r < 400; r++) for (long i = 0; i < n; i++) s = (s * 31 + d[i]) & 0xFFFFFFF;
return s;
}
__attribute__((noinline)) void fill(unsigned char *d, long n)
{
for (long i = 0; i < n; i++) d[i] = (unsigned char)(i * 7);
}
int main(void)
{
static unsigned char buf[1 << 20];
fill(buf, sizeof buf);
printf("checksum %ld\n", checksum(buf, sizeof buf));
return 0;
}$ gcc -O1 -pg prof.c -o prof && ./prof
checksum 209715200
$ gprof -b -p prof gmon.out | head -6
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
100.00 0.47 0.47 1 470.00 470.00 checksum
$ /usr/bin/time -f "elapsed %e s, user %U s, system %S s, max RSS %M KB" ./prof
checksum 209715200
elapsed 0.46 s, user 0.46 s, system 0.00 s, max RSS 2668 KBExpected Result
The CPU-bound work scaled almost perfectly to 2 threads and well to 4 (the machine has 4 physical cores); going to 8 threads uses Hyper-Threading, which added far less than another 2× because two hardware threads share each core's execution units. (An earlier version of this program handed out odd and even numbers to different threads; with 2 threads one thread got all the cheap even numbers and there was no speedup at all — load balance matters as much as thread count.)
The profile attributes 100% of the time to checksum — the only function worth optimizing; /usr/bin/time confirms the program is CPU-bound (user time ≈ elapsed time, no system time) with a small memory footprint.
threads time speedup efficiency (primes found: 216816)
1 0.70 s 1.00x 100%
2 0.36 s 1.93x 97%
4 0.21 s 3.29x 82%
8 0.16 s 4.42x 55%Common Mistakes
Optimizing without a profile.
Benchmarking a single run, a cold cache, or a debug build.
Counting SMT threads as full cores.
Ignoring variance: report medians and percentiles, not just a mean.
Best Practices
Automate benchmarks and keep results over time (performance regressions are bugs).
Profile with realistic inputs on the target hardware.
Change one thing at a time and keep the before/after numbers.
Interview Relevance
High: "how would you find out why a program is slow?", "what tools would you use?", "what is Amdahl's law?", "how do you know if a program is CPU- or I/O-bound?", "what is the USE method?".
Practice Questions
Use /usr/bin/time -v on m18_stride and compare page faults and time.
Optimize checksum in 29.2 (hint: dependency chain, Module 24) and re-profile.
Apply Little's law: 200 requests/s, 50 ms each — how many requests are in flight on average?
Compute the parallel fraction implied by the measured 4-thread speedup using Amdahl's law.
Quick Quiz
Q1. (Multiple choice) A program's user time ≈ elapsed time and system time ≈ 0. It is most likely: A) I/O-bound B) CPU-bound in user code C) Waiting on locks D) Swapping
Answer: B (verified for the profiled program).
Q2. (Predict the output) Does going from 4 to 8 threads on a 4-core/8-thread CPU double the speed of CPU-bound work?
Answer: No — about 1.3× more here (3.29× → 4.42×, verified).
Q3. (True/False) Little's law applies to any stable queueing system.
Answer: True. Q4. (Find the bug) "Thread 0 processes even numbers and thread 1 odd numbers, so the work is split evenly."
Answer: Equal counts aren't equal work: primality tests on even numbers finish immediately (verified: no speedup with that split). Balance by work, e.g. with chunks or a work queue.
Coding Challenge
Given measured speedups S(n) for n threads, estimate the parallel fraction with Amdahl's law (f = (1 − 1/S) / (1 − 1/n)) for S(2) = 1.93 and S(4) = 3.29.
#include <stdio.h>
static double parallel_fraction(double speedup, int n) { return (1.0 - 1.0 / speedup) / (1.0 - 1.0 / n); }
int main(void)
{
printf("from S(2) = 1.93: f = %.3f\n", parallel_fraction(1.93, 2));
printf("from S(4) = 3.29: f = %.3f\n", parallel_fraction(3.29, 4));
return 0;
}