Characterizing Type Feedback in Just-In-Time Compilation

The Ř runtime records three feedback categories: observed callees (closure pointers at call sites), observed types (expression types), and observed tests (guard outcomes). Values in each category form a lattice, with multiple observations merged via least upper bound. Up to three closure pointers per call site distinguish monomorphic (single target), polymorphic (few targets), and megamorphic (many targets) cases. Test feedback records guard outcomes, e.g. whether a builtin has been overloaded. Type feedback is more involved. R has primitive types (int, double, string) that are vectorized, plus heterogeneous vectors, expressions, environments, closures, and others. Almost any value may carry attributes (name–value pairs), some affecting dynamic dispatch, essentially turning values into objects. R also has two builtin object systems: S3 and S4. Beyond nominal type, the runtime tracks two properties. First, whether a value is scalar ($) – a vector of length 1 – or possibly non-scalar (no suffix). Second, its objectness: no attributes (-), has attributes but not an object (+), or possibly an object. These combine into type descriptors like int$- (scalar integer, no attributes) or dbl+ (double vector, not object). Finally, R’s lazy semantics pass arguments as promises – deferred computations with cached results. The runtime records the state before the last force: promise, evaluatedpromise, or plain value. Fig. 1 shows a simplified observed value lattice.

Fig. 2 shows the compilation pipeline. An R closure’s AST is first compiled into Ř bytecode. During bytecode generation, a feedback vector is allocated – a sequence of slots for storing observed runtime information. Each slot corresponds to a bytecode instruction that produces a value, such as variable loads, function calls, or arithmetic operations.

Feedback is primarily recorded during bytecode interpretation. Once a function becomes hot, the bytecode is compiled into a higher-level SSA-style CFG IR [11]. The compiler leverages type feedback, code analysis, and optimizations to generate specialized code. Speculation is eager: type checks are inserted early to specialize code to assumed types, with each speculation guarded by an Assume instruction referencing its feedback slot. The optimized IR is then lowered to LLVM bitcode for the backend.

When a guard fails at runtime, control returns to the interpreter and the corresponding slot is updated with the new observation. Future recompilations account for this updated behavior. Over time, feedback vectors become less precise as more behaviors are observed, degrading code quality – a phenomenon known as feedback vector pollution [17].

During bytecode interpretation, each instruction that produces a value is followed by a recording instruction that updates an associated feedback slot. This update merges the current observation with the slot’s existing content using the lattice least upper bound operation. For example, if a variable load instruction with slot @1 first observes int$-, the slot records this precise type. On a subsequent execution with a different input, if the same instruction observes dbl$-, the slot is updated to (int|dbl)$-, their least upper bound. This merging continues across all executions, gradually generalizing the recorded type.

To illustrate feedback recording, consider the R code in Fig. 3a. Following the compilation pipeline from Fig. 2, the R closure f is first compiled into bytecode. The resulting closure object contains bytecode and a feedback vector with 5 slots. Since R is lazy, each argument is compiled separately into a promise – p0 in this example. Calling f(42) involves loading function g, creating and pushing a promise, calling the loaded function with one argument, pushing the result, and returning.

A promise is a triplet of code, environment, and cached value (initially unset). When forced, the code executes in its environment and caches the result. For p0 representing x + x, this involves looking up variable²²2Ř distinguishes function loading (LdFun) from variable loading (LdVar) due to semantic differences. x using the promise’s environment (i.e. f’s environment), forcing it if needed, and placing its value on the stack. This repeats for the second operand before the values are added and the result returned.

During execution, the runtime records feedback about program behavior. In f, it records g’s target (slot @0) and the return type of g(x + x) (slot @4) – here a scalar double with no attributes, [ dbl$- ]. In p0, it records x’s type twice (slots @1 and @2) and the result of x + x (slot @3). The notation [ dbl$- | prom ] indicates x was bound to an unevaluated promise whose forced value was [ dbl$- ]. The second load of x also observes a scalar double, but since the promise has already been forced, it is recorded as an evaluated promise, [ dbl$- | eval prom ]. The three promise states are: prom (unevaluated), eval prom (already forced), and value (not wrapped in a promise at all).

Ř’s recording is more extensive than in typical JIT compilers. In other languages, recording the second load of x might be omitted as redundant. However, R’s reflection permits inspecting and modifying any environment on the call stack. Consider function h:

which modifies variable x two frames up. Calling f(h()) yields 43 for x+x: the first load sees 42 (the return value of h), while the second sees integer 1 after h modifies x in f’s environment. The type feedback becomes [ dbl$- | prom ] for the first load and [ int$- | value ] for the second. Without recording both, speculations on x would be invalidated, causing unnecessary deoptimizations.

Of the 5 feedback slots recorded during interpretation, only 2 are used in speculation: @0 for speculating on g’s target, and @1 for speculating on the type of x; the rest of the slots are unused. Note that some slots influence compilation without appearing in final speculation – for instance, by guiding inlining decisions or other heuristics (as we explore later in § 5). We say a slot is present if its associated instruction remains in the final optimized IR, and not present if the instruction was eliminated during optimization. Slots @2 and @4 (the second load of x and the result of calling g) are not present – they belong to dead code. Slot @3 is present (still attached to an instruction) but remains unused because the inferred type of the Add instruction already matches the observed type, making speculation unnecessary.

Our experiments are run on a dedicated benchmark machine, with all background tasks disabled. The machine features an Intel i7-6700K CPU, stepping 3, microcode 0xea with 4 cores and 8 threads, 32 GB of RAM and Ubuntu 18.04 on a 4.15.0-151 Linux kernel. Experiments are built as Ubuntu 20.04.1 based containers, and executed on the Docker runtime 20.10.7, build f0df350.

The Ř benchmark suite⁴⁴4github.com/reactorlabs/RBenchmarking includes 14 programs from the well-known shootout⁵⁵5benchmarksgame-team.pages.debian.net/benchmarksgame and Are We Fast Yet⁶⁶6github.com/smarr/are-we-fast-yet suites, plus real-world programs (flexclust, volcano, convolution). The benchmarks contain 1,410 lines of code and run 20 times in the same Ř instance. We recorded 472 compiled functions with 17,119 type feedback slots (7,126 or 42% non-empty) across 556 compilations. Per benchmark, this averages 34 functions, 40 compilations, and 1,222 slots.

We selected notebooks for Titanic dataset exploration⁷⁷7kaggle.com/code/mrisdal/exploring-survival-on-the-titanic, Bolt taxi driver earnings analysis⁸⁸8kaggle.com/code/dannymumo/bolt-driver-earnings-analysis, and London Airbnb dataset analysis⁹⁹9kaggle.com/code/godofoutcasts/eda-on-london-airbnb-r. These 428 lines of code use various popular packages and operate on large datasets. Each notebook runs 15 times in the same instance to warm up occasionally invoked functions. We observed 3,748 compiled functions with 94,402 slots (44,227 or 47% non-empty) across 4,458 compilations. Per notebook, this averages 1,249 functions, 1,486 compilations, and 31,467 slots.

The Recommenderlab [15] examples from the CRAN repository span 222 lines of code. Execution yielded 1,060 compiled functions with 34,818 slots (15,188 or 44% non-empty) across 1,359 compilations. All examples run in a single Ř instance, each executed 15 times.

A slot is used when the compiler speculates on it based on the inferred and observed types, refining the inferred type to unlock new optimizations. As described above, speculation may use the expected type directly (e.g., slot @1 in Fig. 4), or apply widening to find a more exploitable type. We distinguish two subcategories of used slots:

• $\mathrm{■}$

  Exact match, observed type is used directly in a speculation, and

• $\mathrm{■}$

  Partial match, observed type is narrowed or widened before participating in a speculation.

Note that narrowing discards observations inconsistent with the inferred type, but this is rare since the observed type typically falls within the inferred type.

Unused slots are either present or not present in the final version of the code. Slots that are not present correspond to instructions that were eliminated during optimization (e.g., the slots @2 and @4 in Fig. 4), so no speculation on them is possible. Speculation on dead code is impossible. Unused present slots can be further divided into two subcategories based on the reason speculation did not happen:

• $\mathrm{■}$

  Type stable slots, formally $widened(IT,ET)=IT$, capture slots where speculation cannot improve precision. Either the widened expected type is not a meaningful speculation target, or the inferred type already matches it and speculation would not refine the type further (e.g., slot @3 in Fig. 4 is attached to the Add instruction with $OT=IT=$[dbl$- ]).

• $\mathrm{■}$

  Speculation blocked by non-type constraints, formally $widened(IT,ET)⊏IT$, contains slots where types align favorably but speculation is prevented by other factors. For instance, speculation requires an available deoptimization checkpoint; without one, speculation cannot be inserted. Additionally, optimization heuristics may intentionally defer speculation to allow subsequent passes to rewrite or simplify code first.

Fig. 6 summarizes this taxonomy. The categorization provides a systematic framework for understanding how feedback slots are utilized during compilation, distinguishing between slots that actively contribute to speculation and those that remain unused for various reasons.

Table 1 summarizes what we found:

• $\mathrm{■}$

  Slot usage behavior is similar between synthetic benchmarks and real-world code.

• $\mathrm{■}$

  Almost 75% of slots are not used for speculation, mostly because they are type stable.

• $\mathrm{■}$

  Over half of the speculations use exactly the observed type.

Our evaluation uses a fixed set of training inputs to determine which slots are used. Different inputs may require different slots, and the configurations may underperform when encountering code paths not seen during training. This limitation is inherent to feedback-directed compilation, where compilers specialize code based on observed behavior.

Additionally, we do not include slots that were empty during training. These might prove useful when different inputs explore new code paths. Handling such cases remains future work.

We evaluate four configurations that vary the number of recorded slots. For each, we measure interpreter-only execution to estimate reduced overhead, and peak performance to assess optimization impact. The configurations, ordered by increasing slot count, are:

• $\mathrm{■}$

  No slots: no feedback information is recorded (baseline for comparison)

• $\mathrm{■}$

  Optimistic set: slots used in speculation (as previously defined)

• $\mathrm{■}$

  Conservative set: slots used in compilation (as previously defined)

• $\mathrm{■}$

  Baseline: all slots recorded (default compiler behavior)

The Optimistic set and Conservative set configurations provide bounds on achievable improvements: they show what could be gained if we could perfectly predict which slots the compiler will use. The No slots and Baseline configurations establish the extreme points for comparison.

We ran the same set of programs with each of the above configurations.

On average, Optimistic set includes 26% of slots, while Conservative set includes 41%. In Fig. 9 (upper panel), Optimistic set demonstrates clear advantages over Conservative set, most prominently for nbody, mandelbrot, and convolution. Note that, in some cases (e.g. binarytrees, flexclust), the dots do not appear in the expected ordering; the Optimistic set is always smaller (or equal) than the Conservative set, and therefore the recording should be faster (or on par). The difference is within measurement noise: it is due to either the program running for too little time or the mentioned sets being too similar, or both.

Fig. 9 (lower panel) shows peak performance for each configuration, normalized to baseline (optimized code compiled under complete feedback information). One group of benchmarks reaches baseline performance even with no type feedback slots. For these programs, adding more slots provides no benefit, making all configurations equivalent. These programs also show minimal interpreter differences across configurations because they spend most time in native code, which Ř cannot optimize.

The remaining programs make significant use of type feedback, as evidenced by No slots showing substantial performance degradation. These programs appear in Table 2. With Conservative set, all programs reach baseline performance. However, Optimistic set falls short for some programs. Specifically, convolution, fannkuchredux, mandelbrot, nbody, and volcano perform equivalently to No slots, indicating that speculation-only slots are insufficient.

Why does Optimistic set fail for these programs? The issue is that some slots influence compilation even though they do not appear in final speculations. To understand this phenomenon, we examine the convolution benchmark as a representative example.

The convolution benchmark in Listing 1 illustrates how the Optimistic set configuration underapproximates the necessary slots. This simple program performs compute-intensive operations within a doubly-nested loop. In the baseline configuration (all slots recorded), the compiler emits assumptions on all intermediate steps of the computations in the loop – an element access on an object can execute arbitrary code which could modify the current environment. These assumptions are later pulled out of the loop and subsumed by speculation on the function arguments, allowing the compiler to infer the type of all variables. Only speculation on the function arguments survives in the final code; these become the Optimistic set. However, when the slots within the loop are not available, the compiler cannot propagate the information from the arguments to the loop section. This example highlights an important detail: even if an assumption is not present in the final code, its presence at some point may unlock critical optimizations.

Conversely, for binarytrees, fasta, fastaredux, and pidigits programs, the Optimistic set was sufficient to reach baseline performance. This is the ideal case: the compiler reaches full performance without tracking all intermediate uses of slots. The ratio of slots preserved in the Optimistic set for these programs is 33% of all non-empty slots, which is on average 26% fewer slots than the Conservative set.

These results show that Optimistic set works for some programs but not others, while Conservative set succeeds in all cases. However, even Conservative set likely overapproximates: it includes all slots consumed during compilation, but some may not be strictly necessary. Neither configuration yields the minimal set of slots. Finding the true minimum would require a more sophisticated tracking mechanism than we have implemented. The fundamental difficulty is that when feedback information is consumed, it is impossible to predict whether it will affect the final result or be eliminated during optimization. The compiler runs many optimization passes iteratively until a fixed point is reached, and the order in which code is transformed is unpredictable.

An alternative approach would be brute-force search: start with the full baseline set and iteratively remove combinations of slots, checking each time whether the resulting configuration yields the same compilation result. However, this approach is computationally infeasible due to the combinatorial explosion of possible subsets, even when performed offline.

We conducted an additional experiment to evaluate the stability of the Conservative set and Optimistic set configurations. The goal is to evaluate how fast these sets saturate, meaning how many iterations are needed before no new slots are added to the set. This indicates how quickly we could identify the necessary slots for a given program. We ran the same set of programs while tracking the number of new slots discovered in each iteration, as well as the number of unique closures that were compiled. Fig. 10 shows the most frequent result: since programs typically have an inner loop, after a certain number of iterations (here 5) there is a pronounced jump in the number of compiled functions, as well as in the number of discovered used slots. The second jump occurs after all the functions are warmed up (i.e. the iteration number is equal to the warmup counter; here 10). After that, the set is saturated. Notice that new slots only get discovered during compilation.

In a few programs, however, the set is not saturated even after warmup (flexclust, titanic, and recommenderlab). Fig. 11 shows this case – the number of closures and used slots is always increasing. This is because in each iteration a new function is created (e.g. using non-standard evaluation) which cannot be matched with an already existing definition. Therefore, in each iteration new referenced slots are created and new used slots discovered.

Our evaluation establishes upper bounds on achievable gains from selective recording. The Conservative set configuration demonstrates that profiling costs could be substantially reduced without sacrificing optimization quality, though a practical implementation would need to predict compiler decisions – a significant challenge given iterative optimization. The Optimistic set configuration shows more aggressive reductions are possible by accepting degraded performance for certain programs. These oracle-based bounds quantify the design space and tradeoffs, providing motivation and concrete targets for future practical implementations.