Sampling Error, Skid, and How Many Samples a Profile Needs

A profile that says a function accounts for 12 percent of samples is making a statistical claim about a population it never observed in full. Treating that number as an exact measurement is the most common way to draw a wrong conclusion from a profiler, and the error is quantifiable: the width of the interval around 12 percent depends only on the number of samples and the fraction, not on the program.

Two other effects corrupt the estimate before statistics even apply. The sample may not land where the timer intended, and the mapping from samples to time may not be uniform across code. Both are properties of the measurement apparatus, and both produce profiles that are internally consistent and systematically wrong.

Each sample is a Bernoulli trial

Model the profile as follows. The program has a population of instruction executions; a sample picks one at a random instant. Whether a particular function is executing at that instant is a binary outcome with probability $p$ equal to that function’s share of runtime. With $n$ samples and $k$ hits on the function, the estimate is $\hat{p} = k/n$.

The standard error of that estimate is

$$ \sigma_{\hat{p}} = \sqrt{\frac{p(1-p)}{n}} $$

and a 95 percent interval is roughly $\hat{p} \pm 1.96,\sigma$. The numbers that follow from this are less comfortable than most profiles suggest. At $n = 100$ samples and $p = 0.1$, the standard error is $\sqrt{0.1 \times 0.9 / 100} \approx 0.03$, so the 95 percent interval spans roughly 4 percent to 16 percent. A function reported at 10 percent of a hundred-sample profile could be responsible for anything from a twentieth to a sixth of runtime. At $n = 10{,}000$ the same estimate has a standard error of about 0.3 percent, and the interval is tight enough to rank functions against each other.

The practical consequence is a rule about resolution, not about profiler quality. To distinguish a function at 1 percent from background, the interval must be narrower than 1 percent, which requires on the order of ten thousand samples. To resolve differences between functions that each take a fraction of a percent requires proportionally more. This is why short captures of a fast program produce profiles dominated by whichever function happened to be unlucky in the draw, and why the same capture repeated produces a visibly different ranking.

Relative error scales as $1/\sqrt{n}$, so halving the interval width costs four times the samples. That curve is the entire argument for long, continuous collection over short, intense bursts: the same total sample count spread over an hour gives the same statistical power as a one-minute burst, but the burst misses every slow path that only runs occasionally.

Skid: the sample lands after the instruction that caused it

Hardware-counter sampling does not stop the processor at the exact instruction that overflowed the counter. The counter overflow is detected, a performance-monitoring interrupt is raised, and the processor finishes retiring some number of instructions before the interrupt is taken. The address recorded in the sample is therefore some instructions past the one whose execution completed the count.

The distance is the skid, and its size depends on the microarchitecture, on whether the code is in a tight loop, and on how much work is in flight. Out-of-order execution makes it worse: instructions after the overflowing one may already have retired, so the recorded instruction pointer can be several instructions ahead in program order.

Skid is not random noise around the true location. It is directional. Instructions that take many cycles to retire, such as divides, cache-missing loads, and long dependency chains, give the processor more opportunity to drift before the interrupt arrives, so they attract samples that belong to instructions executed earlier. A tight loop of short instructions accumulates skid in a predictable direction as well, because the same offset from the loop body is hit repeatedly.

The mitigation available in hardware is precise event sampling, where the processor can be configured to freeze the instruction pointer at the overflowing instruction for certain event types. It is not universally available, it costs additional cycles, and it is limited to particular events and particular microarchitectures. The software mitigation is to accept the skid and to sample at a coarser granularity than the skid distance: a profile at function granularity is usually unaffected, because the skid rarely crosses a function boundary, while a profile at instruction granularity is heavily distorted and should be read as indicative rather than exact.

Timer-based sampling has a different but related problem. A signal delivered at interval boundaries is taken at the next instruction boundary after the timer interrupt, and the kernel may delay delivery while it holds a lock or while the thread is in a non-interruptible region. The delay is bounded by the kernel’s own latency, which is small in absolute terms but not zero, and it means a thread that spends its time in short syscalls may have its samples attributed to the syscall return path rather than to the syscall itself.

Not every instruction costs the same

Even with perfect sampling, the fraction of samples in a function is the fraction of time, not the fraction of instructions. A function with a hundred cheap instructions and one cache-missing load will be sampled far more than its instruction count suggests, because the miss occupies hundreds of cycles during which the instruction pointer sits in that function.

This is the property that makes sampling useful and the property that makes it misread. A profile sorted by sample count is a ranking by time, and a function that appears at the top is a function where time is spent, which is not the same as a function that is slow to write or called too often. The two diagnoses have opposite fixes: one wants a better algorithm, the other wants fewer calls or better locality. Distinguishing them requires looking at the callers and at the instruction-level distribution within the function, not at the aggregate.

Cycles-per-instruction is the usual way to make the distinction explicit. A function with a high sample share and a low instruction count is stalled; a function with a high share and a proportional instruction count is simply doing a lot of work. Neither number is available from a sample count alone, which is why profilers that report only percentages are less useful than profilers that report the hardware counters alongside them.

Time attribution and the missing wall clock

A CPU-time profile attributes samples only to time the thread was running. The complement, time spent waiting, is invisible, and it is often the larger part. A service whose handler spends 2 milliseconds computing and 18 milliseconds waiting on a database has a CPU profile in which the handler’s compute is the whole picture, and the database wait appears only as the absence of samples.

The consequence is a bias that scales with how much the program waits. For a compute-bound batch job the bias is negligible. For an I/O-bound service it inverts the ranking: the function that consumes the most CPU may be responsible for a tenth of the latency. Attributing the missing time requires sampling a clock that advances during blocking, which means either a wall-clock timer whose signal is delivered to a blocked thread, or kernel-side instrumentation of scheduler events. The off-CPU side is treated in Off-CPU Time and Scheduler Delay as a Profile.

Reading a profile honestly

The practical rules that follow from the arithmetic are few. Report the sample count next to every percentage, because a percentage without a denominator cannot be interpreted. Treat differences smaller than a few standard errors as ties, which in a ten-thousand-sample profile means differences below roughly half a percent. Prefer comparing profiles collected over comparable windows on comparable workloads, since a profile is a sample of a specific execution and two profiles of different workloads answer different questions.

And treat the top of the profile as a hypothesis rather than a conclusion. The sample count establishes that time is spent in a function with a stated confidence; it does not establish why. The next measurement, whether the cost is in the instructions themselves or in the memory system, needs a different instrument. What the sampling instrument itself costs, and how to budget for it, is the subject of The Overhead Budget of a Sampling Profiler.