Type Feedback and the Speculation Budget

A dynamic language compiler cannot know the type of a variable. It can, however, know what types a variable has had, and that is enough to compile code that is fast when the past predicts the future and correct when it does not. The mechanism that records the past is type feedback; the machinery that handles the failure of the prediction is deoptimization; and the design question that ties them together is how much the runtime is willing to bet.

Feedback is recorded per site, not per variable and not per function. The same variable read at two sites yields two independent records, because the two sites may be executed under different conditions and see different types. The granularity is forced by the optimization: each site becomes its own guard, and each guard needs its own prediction.

What gets recorded, and where

The cheapest place to record feedback is the instruction stream itself, and that is where the inline cache already lives. A monomorphic property load has a slot holding the layout; that slot is simultaneously the cache and the feedback. The runtime reads it at compile time and knows the layout.

For values that are not properties, the record is a type, not a layout. A local variable holding a number can hold a small integer, a double, or a heap-allocated arbitrary-precision value in some languages. Each of those has a different representation and a different set of operations, so the compiler needs to know which one the site produces. The feedback entry holds a tag or a small set of tags, updated on each execution.

Recording costs a store on the slow path and, in an interpreter, nothing on the fast path because the cache entry is the feedback. In compiled code that has not yet been optimized, the recording is done by the baseline code: each operation that produces a value with an interesting type writes a tag into a per-site feedback vector. The vector is a contiguous array indexed by site, which keeps the recording to a single store with no allocation and no locking. Whether the vector belongs to the function or to each closure created from it is a separate choice: a per-closure vector lets two closures of the same function accumulate different feedback, at the cost of one vector per closure, while a shared vector records everything any of them sees in one place.

Counters and the optimization trigger

The runtime does not optimize on the first execution, because the first execution is unrepresentative. It counts invocations or loop back edges, and when a count crosses a threshold it hands the function to the optimizing compiler together with its feedback.

The count is per function, or per loop, depending on what is being optimized. A function called many times is optimized as a whole; a function called once but containing a long-running loop is optimized with the loop as the entry point. The second case requires on-stack replacement, because the loop is already executing in the interpreter when the decision is made, and the compiled version must take over mid-iteration.

The thresholds are tuning constants and differ between engines and versions. The principle is that they should be high enough that compilation cost is amortized over the remaining executions and low enough that a program does not spend most of its time in the interpreter. A typical arrangement has a first tier that compiles quickly and without much speculation, and a second tier that compiles slowly and speculates aggressively, entered only after the first tier’s code has run enough times to be worth replacing.

This is where the speculation budget becomes literal. Second-tier compilation is expensive in compile time and in code size, and it is only justified when the function will run many more times. The counter that triggers it is the runtime’s estimate of that.

Why speculation needs an exit

Compiled code that assumes a layout, a type, or a constant is wrong if the assumption fails. The runtime has two ways to handle the failure: check the assumption at every use, or compile an exit path that runs when a check fails.

The first is what the inline cache guard does. It checks on every execution, and the cost is the check. This is cheap when the check is a single pointer compare and expensive when it is a chain.

The second is what aggressive optimization does. The compiler emits the fast path with a guard, but the guard’s failure branch does not fall back to a generic version of the same operation. It calls a runtime routine that reconstructs the interpreter state for the function and resumes execution there. The compiled code is discarded.

The second design allows more optimization because the fast path need not accommodate the general case at all. A loop that sums a field can be compiled to unboxed floating-point arithmetic with a guard on each iteration, and if any iteration fails the guard, the entire function’s state is materialized and the interpreter continues from the failing operation. The fast path contains no boxing, no tag checks, and no generic add.

The price is the machinery to reconstruct that state. The runtime needs to know, at every point where a guard can fail, where each live value is: in a register, on the stack, in a spill slot, or as a constant that has been folded away. It needs to know how to rebuild the interpreter’s frame from those locations. It needs to handle the case where the optimized code has eliminated an object entirely through escape analysis, so that an object that should exist at the deoptimization point has to be reallocated.

This metadata is a stack map or deoptimization table, emitted per safepoint. Its size is proportional to the number of safepoints times the number of live values, and it can account for a large part of what a heavily optimized function carries. That is a real cost, and it is the reason engines do not optimize everything to the maximum tier.

The shape of a losing bet

The sequence when a guard fails in optimized code is fixed.

The guard’s failure branch jumps to a call into the runtime, passing an identifier for the deoptimization point. The runtime reads the stack map for that point, walks the compiled frame, and writes each live value into the corresponding slot of a freshly allocated interpreter frame. The compiled frame is abandoned. Execution resumes in the interpreter at the operation after the failed guard, with the failing value now present as a normal boxed value.

The function may then be reoptimized later with updated feedback, or it may stay in the interpreter. Either way, the deoptimization is not free: allocating the frame, copying values, and discarding compiled code costs on the order of hundreds to thousands of cycles depending on frame size, and the loop that triggered it loses all its compiled state.

If deoptimizations happen repeatedly at the same site, the runtime raises the site’s “deopt count” and eventually stops optimizing the function at all, or optimizes it with less speculation. A function that oscillates between two types is a case where the feedback is genuinely unstable, and the runtime’s response is to stop believing it.

Feedback that is wrong rather than incomplete

The harder problem is not a guard failing but a guard succeeding on a wrong premise, which is why the conditions enumerated in Monomorphic Inline Caches and the Guard That Makes Them Work have to be complete. A layout check that passes while the value at the offset has changed meaning produces wrong results with no failure to detect.

The runtime’s defence is the dependency mechanism. When the compiler uses a fact that is not local to the guarded object, such as “this prototype has no property named x” or “this field has always held a small integer”, it registers a dependency. The dependency is a pointer to a cell that the runtime invalidates when the fact changes. Changing the prototype’s layout, or storing a value of a different representation into the field, invalidates the cell, and every compiled function that registered a dependency on it is deoptimized.

This is why the invalidation has to be conservative. Adding a property to a prototype is a rare operation, but it can invalidate code in every function that read through that prototype, and the invalidation is a scan over the dependency list. The runtime accepts the scan cost because the alternative, checking the prototype on every access, is a cost paid on the hot path instead.

The cell itself is small: a state word, plus a list of dependents. The check at compile time is a comparison against the expected state; the invalidation at run time walks the list. The arrangement is described in Prototype Chain Guards and Validity Cells, and the same cell type is used for assumptions that have nothing to do with prototypes.

What the budget buys and what it does not

Speculation converts dynamic dispatch into static code, and the conversion is the source of nearly all the performance that optimized dynamic language runtimes achieve. Without it, every property access is a lookup and every arithmetic operation is a dispatch on tags.

It does not make the language static. A program can change the types of its variables at any point, and the runtime will handle it, at the cost of deoptimization. The budget is a bet that most programs do not, most of the time, and the bet pays because the cost of being wrong is bounded by the deoptimization machinery rather than by incorrectness.

The design constraint that follows is that speculation must be cheap to abandon. Every optimization that is expensive to undo is an optimization that has to be justified by a stronger prediction, and the tiered structure of modern engines is exactly a ranking of optimizations by how much they cost to reverse. Tier one speculates on nothing beyond the inline caches it inherits; tier two speculates on types and layouts and pays for the stack maps; a hypothetical tier three would speculate on values and pay more.