Counting Function Calls Without Losing the Call Count to Inlining

Sampling answers “where was the program at each tick”. Instrumentation answers “how many times was this called, and how long did each call take”. The second question cannot be answered by more frequent sampling, because a function called a million times in a second is sampled roughly never per call and constantly in aggregate; the counts are invisible at any rate. The cost of getting them is that the measurement changes the program.

Two ways to insert a hook

The compiler-driven approach uses -pg, which makes the compiler emit a call to mcount or __fentry__ in every function prologue and record the caller’s address. This is the mechanism behind gprof. It is also available in a finer-grained form as -finstrument-functions, which calls __cyg_profile_func_enter and __cyg_profile_func_exit around each function body and lets the programmer supply implementations that count, time, and record call paths.

The kernel’s ftrace works the same way with a different installer. When built with the function tracer, every function begins with a five-byte nop. At configuration time the kernel patches those bytes to a jump into the tracing trampoline, and the patch sites are recorded in a table. Enabling or disabling a trace flips a variable, and the patching machinery rewrites the call sites when the set of traced functions changes. The static call mechanism does the same at a per-site granularity inside modules. The benefit is that an untraced build executes a nop, which is nearly free, and the cost appears only when tracing is on.

Dynamic binary instrumentation takes the third route: a runtime such as Valgrind or DynamoRIO copies basic blocks into a translation cache, inserts counting and timing code, and executes the copies. No recompilation is needed and third-party binaries can be measured, at the price of a substantial slowdown and a dependency on the tool’s understanding of the instruction set.

The compile-time hook is not a free counter

A call inserted at function entry has consequences beyond the instructions it executes. It inhibits inlining of the function into its callers, because an inlined body has no distinct entry to instrument. That changes the shape of the program being measured: a function that would have been inlined and optimised away now exists, with its own frame, its own register allocation, and its own call overhead. For small accessor functions, the instrumentation-induced cost can exceed the function’s real cost, and the profile reports a program that spends its time in accessor calls.

The exit hook has a worse problem: it must run even when the function does not return normally. longjmp and C++ exceptions leave a function without traversing its exit hook, so a counter incremented on entry and decremented on exit drifts. Tools that build a call stack from enter/exit events therefore need an unwinder or an exception-unwind hook to resynchronise, and the resynchronisation itself changes the measurement.

Recursion is the third break. With entry counting alone, a recursive function’s count is the number of calls, not the number of invocations of the outermost call, and the two can differ by orders of magnitude. gprof’s call-graph arcs distinguish self-recursion from mutual recursion only approximately, and the classic mcount interface cannot reliably attribute recursion depth because it receives only the caller’s address.

Cost per call, and where the attribution goes wrong

Counting hooks give a natural cost model: if a function is called n times and consumes time T, the per-call cost is T/n. Instrumentation-based profilers combine the hook counts with either sampling or timer-based accounting per call, and the per-call average is genuinely useful for functions whose cost is dominated by the call itself: small leaf functions, allocator calls, wrapper layers.

Inlining destroys the correspondence between the measured function and the source function. If the compiler inlines a helper into three callers, the helper’s body exists three times, each with the caller’s name in the symbol table and no trace of the original. The hook, if one is emitted at all, is attributed to the containing function. The call count for the helper drops to zero and the counts of its callers absorb the work, so an instrumented build can report a function as never called while the source calls it in three places.

Debug information can recover the inline structure after the fact, as described in symbol attribution, but the counter itself was incremented at the containing function’s entry. Post-hoc attribution can say where the code came from; it cannot reconstruct how many times the inlined copy was entered, because the copy is entered whenever control reaches that address and there is no hook there.

Reconciling counts with a sampled profile

The two techniques disagree in a characteristic way, and the disagreement is informative rather than a defect. A sampled profile reports time proportional to samples; an instrumented profile reports calls and, if it measures them, an inclusive and exclusive time per function. For a function with a high call count and a short body, instrumentation reports a large total time and sampling reports very little, because each call is shorter than a sampling period. Neither is wrong: the sampling number is the time share, and the instrumentation number includes the hook overhead that sampling does not incur.

Reconciling them requires subtracting the hook cost. A hook that costs, say, a few tens of nanoseconds per call is negligible for a function called a thousand times a second and dominant for one called a million times a second. The measured per-call cost therefore has a floor set by the instrumentation, and a per-call cost near that floor means the function’s true cost is unresolvable. Calibrating the floor once, with an empty instrumented function, gives a usable lower bound.

The other reconciliation is depth. Instrumented counts cover every call; sampled stacks cover only calls that were on the stack at a tick. A function called a billion times in a tight loop appears in a sampled profile as a single wide leaf with a count near the loop’s share of samples and no information about the per-call cost. The call count and the time share are complementary facts, and a question about one is not answered by the other.

Overhead shapes and when instrumentation is affordable

The overhead of instrumentation scales with invocation count, which makes it unsuitable for programs whose hot path is a high-frequency call. The overhead of sampling scales with rate and stack depth, independent of invocation count. This is exactly the inverse of the earlier trade, and it determines which tool fits which program.

Property	Sampling	Entry instrumentation
Cost scales with	rate × depth	number of calls
Exact call counts	no	yes
Sees short-lived functions	no	yes
Changes code layout	no	yes (inlining, register allocation)
Works on unmodified binary	yes	only with dynamic binary instrumentation
Resolution of per-call cost	poor	good down to the hook floor

A practical rule follows from the table. Instrumentation is affordable when the number of instrumented calls per second is small; a few hundred thousand per second at most, with a hook in the tens of nanoseconds range, which is already several percent of a core. For functions called tens of millions of times per second, the only usable instrument is a counter incremented inline without a call, or no instrument at all.

Counting without hooks

The kernel’s static call mechanism and similar designs allow a counter to be incremented by patched-in code with no function call, but the more general solution is hardware. A retired-instructions counter tells nothing about which function, but processors expose a limited set of counters that can be filtered by address range: the core can count events only while the instruction pointer is inside a given region, and read the count out through rdpmc or an mmaped page. Counting per function then becomes a matter of programming one counter per function of interest, which the hardware cannot do for thousands of functions at once but can do for a handful. The same counters, used as sampling sources rather than as totalling counters, give the event-weighted profiles described in hardware counter event sampling.

A cheaper software approximation is a per-thread non-atomic increment in a register-allocated variable. It loses precision under migration between CPUs if incremented non-atomically, but it costs a single instruction and does not inhibit inlining if the counter variable is visible at the call site. Instrumentation frameworks that care about overhead distinguish these cases explicitly and let the caller choose.

Deciding which instrument to trust

An instrumented count is exact for the code the compiler emitted and approximate for the code that was written. It will agree with a hand-written counter in a debug build and diverge in an optimised build, and the divergence is a measurement of how much the inliner did. That is a useful fact in itself: running the same program under -O0 and -O2 with the same instrumentation shows the structural change directly, which is why comparing instrumented builds at two optimisation levels is a defensible exercise in learning about the compiler, not just the program.

For latency questions the instrumentation has a further limit that no calibration removes. A hook that reads the timestamp counter at entry and exit measures the region between two readings, and the readings themselves cost. For sub-microsecond regions the reading cost is a large fraction of the measurement, and for functions whose cost is dominated by a cache miss or a branch misprediction, the perturbation of the hook can change which of those events occur. The region is measured accurately; the measurement has changed the region.