10. Measurement and Timing

What this lecture covers

This lecture asks a deceptively simple question: how do you reliably measure how fast software runs? It opens with a real anomaly, a sorting benchmark whose run times bounce up and down instead of following a clean n log n curve, and uses it to motivate a systematic look at every source of noise between your code and the number you read off a timer.

The lecture covers three areas: quiescing a system (removing sources of variability such as dynamic frequency scaling, hyperthreading, interrupts and code alignment), tools for taking measurements (the time command, clock_gettime, sampling profilers, hardware counters and simulators), and performance modeling (choosing the right summary statistic, comparing two programs statistically, and avoiding the classic mistake of averaging ratios the wrong way). After watching, you should be able to explain why two runs of the same program give different times, set up a fairer comparison between two versions of a program, and choose a summary statistic that matches the question you're actually asking.

Key ideas

• DVFS (dynamic voltage and frequency scaling): the processor lowers its clock frequency and voltage as it heats up, since dynamic power scales with C * V^2 * F, which is exactly what produced the mysterious rollercoaster pattern in the opening example.
• Quiescing: following Genichi Taguchi's quality-control insight, reducing variance first (before trying to make things faster) makes it possible to tell whether a change actually helped.
• Sources of variability: background daemons, interrupts, code and data alignment, thread placement, the OS scheduler, hyperthreading, multi-tenancy in the cloud, turbo boost, and even linker order or a program's file name can all change measured performance.
• clock_gettime(CLOCK_MONOTONIC): the recommended timer, guaranteed never to run backwards, at roughly 83 nanoseconds per call; gettimeofday and the raw cycle counter (RDTSC) have subtler problems and are not recommended.
• Five ways to measure: external timing (the time command), instrumenting the program itself, interrupting it periodically (the "poor man's profiler"), hardware performance counters, and simulation.
• Triangulation: never trust a single measurement or a single method; take at least two independent measurements and check that they agree.
• Choice of summary statistic: the minimum best rejects noise for a deterministic program's raw performance, but mean, median, maximum, or percentiles are each appropriate for different questions, such as CPU utilization versus tail latency.
• Ratio of means, not mean of ratios: averaging ratios of two programs' run times with the arithmetic mean gives a result that depends on which program you put in the numerator; the geometric mean fixes this, and the harmonic mean is the right choice for rates.
• Head-to-head statistical comparison: running paired trials and testing whether one program wins significantly more often than the other, using a null-hypothesis test, is a robust way to decide which of two programs is actually faster under noisy conditions.

Walkthrough

A sorting benchmark that shouldn't look like this (0:01)

The lecture opens with a student's merge-sort timing experiment: array size increases, and run time is measured with clock_gettime. The expected n log n curve is shown next to the actual measured points, which rise and fall in an unexplained pattern, setting up the rest of the lecture as detective work to explain it.

Diagnosing the cause: DVFS (12:16)

After ruling out caching, powers of two, background processes, and memory allocation delays, the culprit is revealed: the machine throttles its clock frequency as it heats up during the larger sorts, then speeds back up as it cools, producing the observed oscillation. The lecture explains the underlying power law, P = C * V^2 * F, and why reducing frequency and voltage together gives a cubic power reduction.

Quiescing the system (17:23)

Drawing on Taguchi's quality-control philosophy of reducing variance before trying to improve a system, the lecture lists concrete sources of measurement noise: daemons and cron jobs, interrupts (illustrated by a true story of a mouse-moving graduate student corrupting supercomputer measurements), code and data alignment, thread placement, the scheduler, hyperthreading, multi-tenancy, turbo boost and network traffic. A before/after experiment on an 18-core machine shows run-to-run variation dropping from about 25% down to under 1% once the system is quiesced.

Timing tools in practice (40:51)

Five measurement approaches are compared: the external time command (elapsed, user and system time); in-program timing calls, where clock_gettime(CLOCK_MONOTONIC) is recommended over gettimeofday or RDTSC; interrupting the running program (control-C sampling, gprof), which needs many samples to be accurate; hardware performance counters via libpfm4, which are powerful but poorly documented and limited to a handful of simultaneous counters; and simulators like Cachegrind, which are slow but repeatable and useful for isolating specific effects like cache misses.

Choosing summary statistics (1:02:27)

Polling the class on which statistic best represents a deterministic program's raw performance, the lecture argues the minimum rejects noise best, since any measurement above it is attributable to interference, while mean, median, maximum and other statistics each serve different practical goals such as CPU utilization, tail latency, or memory footprint.

The ratio-averaging trap (1:07:38)

A worked example compares two programs across four trials and shows that taking the arithmetic mean of per-trial speed ratios gives an answer that depends on which program is the numerator, an obvious red flag. The geometric mean is shown to be consistent regardless of direction, and the harmonic mean is noted as the correct choice when averaging rates.

Statistically comparing two programs (1:13:57)

The lecture closes with a discussion-driven approach to deciding whether program A or B is faster under noise: run many paired trials, count how often each wins, and use a null-hypothesis test (treating wins as roughly a coin flip if the programs were equal) to compute a p-value for rejecting the hypothesis that they perform the same. This answers a more practical question than raw performance: which program wins in the actual noisy environment it will run in.

Before you watch

• Familiarity with basic descriptive statistics (mean, median, percentiles) will help with the summary-statistics discussion.
• It helps to have already run code on the course's AWS setup, since the lecture repeatedly contrasts a quiesced course environment with a typical noisy laptop.
• A basic sense of processor architecture (clock frequency, caches, hyperthreading) makes the sources-of-variability section easier to follow.

Check your understanding

1. Why did the sorting benchmark's run times rise and fall instead of following a smooth n log n curve?
2. Why is clock_gettime(CLOCK_MONOTONIC) recommended over gettimeofday or reading the cycle counter directly?
3. Give three concrete steps you could take to quiesce a laptop before benchmarking code on it.
4. Why is taking the arithmetic mean of ratios of two programs' run times misleading, and what fixes it?
5. Describe the head-to-head statistical method for deciding whether program A is faster than program B under noisy conditions.