Sample-Based Profiling and Stack Walking in Compiled Code

Instrumentation tells a runtime exactly how often each event occurred, and it charges every event for the telling. Sampling tells it approximately where the program spent its time, at a cost proportional to the sampling rate rather than to the program’s activity. For a runtime that must observe a program without changing its performance profile, sampling is the only mechanism that scales, and the price is statistical rather than exact.

The Sampler as an Interrupt

A sampler works by taking control away from the running program at intervals and recording what it was doing. The control transfer comes from one of three sources.

A timer signal is the portable option: the runtime installs a handler for an interval timer, and the operating system delivers the signal to a running thread at a fixed period. The handler records the interrupted program counter and returns. Signals arrive on an arbitrary thread, which for a multi-threaded program means the runtime must either direct the signal to a specific thread or accept a sample of whichever thread the kernel chose.

A dedicated sampling thread is the second option. The sampler thread periodically suspends another thread and reads its program counter and registers. Suspension is cooperative in some runtimes, where the target thread checks a flag at safepoints, and preemptive in others, where the operating system’s thread suspension is used. Cooperative sampling is cheaper and safer but misses time spent in code that does not reach a safepoint; preemptive sampling is accurate but must handle the target being in the middle of an arbitrary instruction.

Hardware performance counters are the third. A counter can be programmed to overflow after a fixed number of instructions or cycles, delivering an interrupt whose program counter is the sample. This measures work rather than wall-clock time, which is often what a compiler wants: the counter overflows on the thread that executed the instructions, so a sample is attributed to the code that produced it rather than to whichever thread the kernel happened to deliver a process-directed timer signal to. A thread descheduled by the operating system accumulates no instruction samples, so its idle time never appears in the profile.

The three differ in what a sample means. Timer samples estimate wall-clock distribution, including time blocked in the kernel or descheduled. Counter samples estimate work distribution. A profile built from timer samples on an oversubscribed machine can show a method as cold when it is merely starved, which is a bias worth knowing before acting on the profile.

Walking a Stack That Has No Frames

Recording a single program counter gives a flat profile: which methods were executing at sample time, counted. Attributing time to call paths requires walking the stack, and that is where compiled code complicates matters.

An interpreter’s stack is easy to walk because its frames are runtime-defined structures with a known layout: each frame holds a method reference and a return address, and the runtime can follow the chain. Compiled code’s frames are whatever the calling convention produced. A compiled method may keep its locals in registers, may have no frame pointer if the compiler omitted it, and may have inlined several callees so that one physical frame corresponds to several source-level frames.

Three approaches exist. Frame-pointer walking requires the compiler to maintain a frame pointer chain, which costs a register and a few instructions per call. It is the cheapest walk and the least informative, since it cannot see through inlining. Unwinding tables, as used for exception handling on several platforms, describe how to recover each caller’s registers from any instruction offset, and a stack walk that consults them can traverse code compiled without frame pointers. The third approach is for the runtime to consult the same metadata it uses for deoptimization: the frame map at the sampled program counter tells the walker which registers hold the return address and the frame pointer, and the deoptimization chain tells it which virtual frames are inlined at that point.

The third is what makes a profile useful for a JIT. Walking the physical frames yields one entry per compiled method; walking the virtual frames yields one entry per inlined callee, which is what the compiler needs in order to know which of its inlining decisions paid off. A profile that attributes all of a method’s time to the outermost frame cannot tell an inliner that a callee inlined into it is the reason for the cost.

/* Sample handler: record the interrupted PC, defer the walk to a safepoint.
   Walking in the signal handler would race with the program's own stack use. */
static void on_sample(int sig, siginfo_t *si, void *uctx) {
    ucontext_t *uc = uctx;
    sample_buffer_push(uc->uc_mcontext.gregs[REG_RIP]);   /* PC only, no walk */
}

/* Called at a safepoint where every thread's stack is stable. */
void drain_samples(struct vm *vm) {
    uintptr_t pc;
    while (sample_buffer_pop(&pc)) {
        struct compiled_method *m = code_cache_lookup(vm, pc);
        if (!m) { vm->samples.native++; continue; }
        struct frame_state *fs = frame_map_at(m, pc);     /* inlined chain */
        for (; fs != NULL; fs = fs->caller)
            profile_record(vm->profile, fs->method, fs->bci);
    }
}

Deferring the walk is not an optimization; it is a correctness requirement. A signal handler may interrupt the code that would do the walking, and the lookup and the allocation a walk needs are not async-signal-safe. Recording only the program counter in the handler and resolving it later, at a point where the runtime controls the thread’s state, is the standard arrangement.

Bias, Skew, and the Cost of Resolution

Sampling has failure modes that exact counting does not.

The first is insufficient samples. A method that accounts for one percent of execution needs hundreds of samples before its share is distinguishable from noise, and a profile that stops after a few dozen samples will report many methods as equally cold. Runtimes that recompile based on sampled profiles must therefore require a minimum sample count in a method before acting on its profile, or they will specialize based on one or two observations.

The second is safepoint bias. A sampler that only records samples at safepoints, because the program counter must be at a known point for the walk to be valid, systematically misses time in code between safepoints. A long-running loop with a poll at its back edge gets sampled at the back edge, which is representative; a straight-line region with no safepoint gets sampled only at its boundaries, attributing its cost to whatever code precedes the poll. The bias is small in loop-heavy code and significant in code dominated by long calls into native libraries, where the sampler sees the call site but not the work inside.

The third is skid. A counter overflow or a signal delivery takes some cycles to reach the handler, so the recorded program counter may be slightly after the instruction that caused the event. On an out-of-order core, several instructions may have retired in that window. The effect is to smear samples across adjacent instructions, which matters for instruction-level attribution and not at all for method-level decisions.

The fourth is the resolution cost itself. Mapping a program counter to a compiled method requires a lookup in the code cache’s side table, and doing it for every sample at a high rate can consume measurable time. Runtimes bound the rate, typically to tens or hundreds of samples per second per thread, which is enough for method-level attribution over seconds and insufficient for instruction-level analysis over milliseconds.

What Sampled Profiles Are Good For

The uses divide by the granularity the profile supports.

At method granularity, a sampled profile answers which methods are hot, which is what a tiering policy needs and what counters already provide. The advantage over counters is that samples measure time rather than frequency, so a method called a million times but doing almost nothing does not dominate, and a method called rarely but blocking for milliseconds does.

At call-site granularity, a profile with stack walking answers which callers cause a method’s cost, which counters cannot. That is the input to inlining decisions that depend on context: inlining a callee into one caller but not another is only justifiable if the profile shows the cost concentrated in the first.

At branch granularity, samples can indicate which side of a conditional is hot if the sample resolves to an instruction and the branch is identified, but the resolution is coarse and branch mispredictions are invisible to it. Counters on branches are exact and cheap; sampling is the wrong tool here, and runtimes that collect branch profiles instrument rather than sample.

The combination is what a mature runtime uses: counters to detect hotness cheaply and exactly, inline caches to record types, and sampling to attribute time to call paths where the exact mechanism would be too expensive. Each covers a bias of the others, since counters miss cost, samples miss exactness, and caches miss control flow, and the compiler consumes whichever of the three is available at the moment it compiles, falling back to conservative code when none is.

Sampling and Deoptimization Metadata

The dependency on frame maps creates a constraint that reaches back into the compiler. Every safepoint must have an accurate map, not only because deoptimization needs it, but because the sampler reads it while the program runs. A compiler that omits a map at a point where sampling can occur produces profiles that attribute inlined frames incorrectly, and a runtime that samples compiled code without maps is reduced to physical frame walking and cannot see through inlining at all.

This is one of the reasons the metadata for deoptimization is designed as a general description of machine state rather than as a structure specific to one consumer. The same description lets a stack walk find references for the collector, reconstruct a frame for a fallback, and resolve inlined frames for a profile. A runtime that pays for the metadata once gets three mechanisms, and a runtime that tries to economize by recording it only where deoptimization seems necessary finds that its profiler and its collector are both crippled.