Sampling Allocation Profilers and the Statistics of Estimates

Recording a stack trace at every allocation is accurate and unusable: the tracer costs more than the allocations it describes, and the tracing lock serialises threads that were previously independent. The alternative is to record a small fraction of events and scale the results up. The scaling is where the subject becomes statistical rather than mechanical, because a sampled profile is an estimate with an error that depends on how the sample was drawn.

Fixed-rate sampling and its bias

The obvious scheme is to capture every n-th allocation. Count allocations in a per-thread counter, capture when the counter crosses the threshold, reset. Each captured event represents exactly n allocations, so the reported count is the sample count times n and the reported bytes are the sampled bytes times n.

That is unbiased for the count and biased for the bytes, because the allocations captured are not representative of the bytes. Consider a program that allocates a million 32-byte objects and a thousand 4 KiB objects. With n of 1000, the sample contains a thousand small objects and one large one. Scaling by n reports 32 MiB in small objects (correct) and 4 MiB in large objects, which happens to be correct only because the large-object rate exactly matched the threshold. Shift the rate and the estimate for the large class is dominated by whether one or two large allocations happened to land on a threshold boundary. The large objects, which are the ones a footprint investigation cares about, are sampled at a rate that makes their estimate nearly meaningless.

The fix is to sample by bytes rather than by count: capture when the cumulative bytes allocated since the last capture cross a threshold. For sizes small relative to the threshold T, an allocation of s bytes is captured with probability roughly s / T, so a 4 KiB request is about 128 times more likely to produce a capture than a 32-byte one, and that proportionality is what keeps the byte total accurate. An allocation of T bytes or more cannot be under-sampled: it always produces at least one capture, which is how the large objects that dominate a footprint stay exact while the small ones are estimated.

The estimator, precisely

The standard construction is Poisson sampling on bytes. Give each thread a counter of bytes allocated since its last capture. On each allocation of size s, add s to the counter. When the counter exceeds a threshold T, subtract T (or reset to zero, which introduces a small bias), capture a trace, and credit the capture with T bytes.

Because the threshold is crossed by cumulative bytes, the expected number of captures across the whole process is B_total / T, and each capture is worth T bytes, so the total is estimated by counting captures rather than by summing the sizes of the sampled requests. Attributing captures to call sites therefore estimates each site’s share only as finely as the sample allows: a site receives a number of captures proportional to its bytes, but the count is small whenever the site is a small fraction of the total. For a Poisson capture process with mean n captures, the relative standard error is 1 / sqrt(n). A call site responsible for 100 MiB with a 512 KiB threshold accounts for about 200 captures, giving a relative standard error near 7 percent. A call site that accounts for a single capture has a Poisson relative standard error of 100 percent: the estimate could plausibly be zero or twice the true value.

The consequence is a rule about reading profiles: totals for large contributors are trustworthy to a few percent, totals for small contributors are not, and the number of samples behind a row should be reported alongside the bytes. A profile that shows 200 MiB against a stack with four samples is reporting an estimate whose confidence interval spans most of the heap.

# Relative standard error of a byte-weighted sample, by call site.
import math

def rse(total_bytes, threshold):
    expected_samples = total_bytes / threshold
    if expected_samples == 0:
        return float("inf")
    return 1.0 / math.sqrt(expected_samples)

for total in (512 << 10, 4 << 20, 64 << 20, 512 << 20):
    print(f"{total >> 20:4d} MiB  rse={rse(total, 512 << 10):.3f}")

The arithmetic assumes captures are independent, which holds when the counter is per-thread and threads behave independently. It does not hold when a single allocation site is hit in a tight burst by many threads sharing a counter, because the counter then synchronises captures across threads. A shared counter is also a shared cache line, which reintroduces exactly the contention the sampling was meant to avoid; per-thread counters are both the accurate and the fast choice.

Choosing the threshold

The threshold sets the trade between overhead and resolution. Overhead per allocation is roughly the cost of a counter update plus, for the captured fraction, the cost of an unwind. An unwind costs tens to hundreds of times a counter update, so the overhead is dominated by unwind_cost / (T / mean_size), the capture rate times the unwind cost.

A threshold of a few hundred kilobytes per capture is the usual default for general-purpose profiling. For a program that allocates gigabytes, that yields thousands of captures per second, which is enough resolution to identify the top contributors and small enough overhead to leave the program’s behaviour intact. For a program that allocates a few megabytes in total, the same threshold yields a handful of captures and a profile that is barely a sketch; lowering the threshold to tens of kilobytes raises the capture count but also the overhead relative to the work being done.

The threshold also interacts with the leak case. A leak that allocates one large object per hour is invisible at any threshold that a busy process can afford, because its total bytes are small even though its retention is unbounded. Sampling profilers measure allocation volume, not retention, and a slow leak is exactly the case where volume and retention diverge. Finding it requires the growth-over-time analysis that compares live sets rather than allocation rates.

Keeping the stack cheap

Sampling reduces the number of unwinds but does not reduce the cost of each. The unwind path has to be fast and re-entrancy-safe, which is a stronger requirement than in a tracing profiler because the sampling decision happens inside the allocator’s hot path.

Three techniques are standard:

Unwind to a fixed depth. Capturing the first eight or sixteen frames is enough to identify the call path in most programs, and it bounds the per-capture cost. The cost of the tree insertion that follows is proportional to the depth.

Defer symbolisation. Storing raw return addresses is cheap; resolving them to function names requires consulting the object files and is expensive. The standard split is to record addresses at capture time and resolve them when the profile is written, which keeps the hot path free of file I/O and of the locks inside the symboliser.

Avoid locks on the capture path. A shared hash table for the trace tree needs a lock, and a lock taken on a sampling path is a lock that can be held while another thread is in the unwinder. The usual design is a per-thread buffer of raw records that is flushed in batches, so the shared structure is touched once per batch rather than once per capture. The buffer is bounded, and when it fills the capture path either blocks or drops the record; dropping is often preferable, and the drop count must be reported or the profile silently undercounts.

What sampling cannot see

Four limitations follow from the design rather than from any implementation.

Rare events. An allocation path taken once in a million allocations may never be captured, and the profile will show nothing at all for it. If that path is the one that retains a large buffer, the profile is not merely imprecise but wrong about which code is responsible. Comparing two profiles taken at different times can surface such paths indirectly, since a path absent from both is invisible while a path present in both with growing totals is not.

Per-object sizes. A sampled profile estimates total bytes well and mean object size reasonably, but the distribution of sizes within a call site is lost. A call site that allocates a mix of tiny and huge objects appears as a single weighted average, which is not enough to decide whether the site is a problem or whether one of its branches is.

Short-lived allocations. A profile taken over the life of the process includes every allocation that ever happened, including the ones freed immediately. The live set at any instant is a small fraction of the total for most programs, so an allocation-volume profile describes traffic rather than footprint. Tools that report in-use bytes keep the same sampling decisions but weight only the sampled objects still live at the time of the dump, by the inverse of their inclusion probability; that requires marking each sampled object at capture and clearing the mark when it is freed, which is feasible for a sampled subset and not for a full trace at the same cost.

Allocations the sampler cannot intercept. A runtime with its own heap, a direct mmap, or a statically linked allocator is invisible, exactly as in the interposition case, and for the same reasons.

Reconciling a sampled profile with a footprint

The numbers from a sampling profiler never add up to RSS, and the discrepancy has several independent causes that are worth separating before concluding the profiler is wrong.

The profiler counts bytes requested. The process pays bytes reserved, including the per-object overhead and the span rounding, which for small objects can be a factor of 1.5. The process also pays for pages it has reserved but not returned, which no allocation-level tool sees. And the process’s resident size includes file-backed mappings and the runtime’s own structures, neither of which passes through the traced allocator.

The reconciliation is therefore a multiplication by known factors rather than a match: requested bytes times the structural ratio gives reserved bytes, reserved bytes times the occupancy factor gives heap pages, and heap pages plus non-heap mappings gives the resident set. Each factor is measurable separately, and each is the subject of its own measurement. Treating the first number as an approximation of the last is the single most common error in memory profiling, in either direction.