Partial Evaluation and Specialization
When some inputs are known and others are not, a program can be specialized with respect to the known ones — producing a smaller, faster program that takes only the remaining inputs. It is the idea behind constant folding, template instantiation, JIT specialization and monomorphization, and it explains why they behave alike.
Half of my function's inputs are fixed at startup. Can the compiler produce a version of it that only takes the rest?
IR plus a binding-time division: each value is classified as *static* (known at specialization time) or *dynamic* (not known until the specialized program runs). That division is the representation this lesson adds; everything else follows mechanically from it. A pass that folds static operations and residualizes dynamic ones turns a two-input program into a one-input program.
The specialized program must produce, for every dynamic input, exactly what the original produced for that input together with the fixed static ones — including the same effects in the same order. Operations on static values may be evaluated only under constant folding's conditions: they must not trap, and the specializer's arithmetic must match the target's. Where a static value drives a branch, both the branch and its untaken arm may be removed. Where speculation supplies the static value rather than proof — a JIT specializing on an observed type — the specialized code is valid only behind a guard with a path back.
Key points
- A program with some inputs fixed can be mechanically transformed into a smaller program taking only the rest.
- Constant folding, monomorphization, template instantiation, JIT specialization and
constexprare all instances of this, which is why they share their costs and their failure modes. - The binding-time division — which values are static — is the entire design decision; everything else follows from it.
- A JIT chooses its static set by observation, which makes it a hypothesis about the future and makes a guard mandatory.
- Specializing an interpreter with respect to a program yields a compiler for that program: the first Futamura projection, and the basis of GraalVM/Truffle and PyPy.
- Every specialization is a copy, so the cost is code size and compile time, and the benefit is proportional to how much the static input determines.
One idea, five names
A program is a function of its inputs. If some of those inputs are fixed and the rest are not, there is a smaller program that takes only the rest. Producing it mechanically is partial evaluation, and once the idea is named, a great deal of compiler technology turns out to be instances of it.
[[constant-folding]] is partial evaluation over a single operation. [[monomorphization]] is partial evaluation with respect to type parameters: Vec<T> specialized to T = i32. [[template-instantiation]] in C++ is the same thing with a different surface. A JIT specializing a function to the receiver types it observed is partial evaluation with speculated static inputs. And [[compile-time-evaluation]] — constexpr, const fn, comptime — is partial evaluation exposed to the programmer as a language feature with a guarantee attached.
Seeing them as one thing has a practical payoff: the same questions apply to all of them. What is static and what is dynamic? What does specializing cost in code size? What happens when the static assumption is wrong? And how many specializations is too many?
fn interpret(program: [Op], input: int) -> int {
let acc = input;
for op in program {
match op {
Add(k) => acc = acc + k,
Mul(k) => acc = acc * k,
Neg => acc = -acc,
}
}
return acc;
}
// called repeatedly with program = [Add(3), Mul(2)]// specialized with `program` static, `input` dynamic:
fn interpret_add3_mul2(input: int) -> int {
return (input + 3) * 2;
}program is fixed across every call being specialized, so the loop trip count, the dispatch on each op and the constants 3 and 2 are all static. Unrolling the loop over the known program and folding each dispatch removes the interpretive overhead entirely, and the residual program computes the same result for every value of the dynamic input.
program is not actually fixed. If the specialized version is reached with a different program, it computes the wrong answer — silently. A specializer that speculates on the value rather than proving it must guard: check that program is the one specialized for, and fall back to the general interpreter or deoptimize when it is not. That guard is the entire difference between a JIT and a miscompiler.
The binding-time division is the whole design
Everything in a partial evaluator follows from deciding which values are static. Get the division right and the residual program is small and fast; get it wrong and you either specialize on something that varies — producing a combinatorial explosion of versions — or fail to specialize on something that was fixed, producing no benefit at all.
Real systems make this division in very different ways. C++ templates make it syntactic: template parameters are static, function parameters are dynamic, and the programmer draws the line explicitly. Rust does the same for generics, with monomorphization producing one machine-code copy per instantiation. constexpr and const fn let the programmer mark computations as evaluable when their inputs are, with a compile error if they are not — a checked division rather than a hoped-for one.
A JIT draws the line dynamically, and this is the interesting case: it observes which values are stable across executions and treats those as static, guarded. A field that has always held an integer, a call site that has always seen one receiver type, a loop whose bound has always been the same — each is a candidate for a specialization that is valid as long as a cheap check keeps passing. The static set is a hypothesis about the future, which is exactly why [[guards]] and [[deoptimization]] are not optional extras.
| System | How the static set is chosen | Cost of a bad division |
|---|---|---|
| Constant folding | Whatever is a literal in the IR | None — it simply does not fire |
| C++ templatesspec | Template parameters, by syntax | Code bloat and compile time: one instantiation per distinct argument list |
| Rust monomorphization | Generic type parameters, by syntax | Binary size; the standard reason a Rust binary is larger than the equivalent C one |
constexpr / const fnspec | Programmer annotation, checked by the compiler | A compile error, which is the good failure mode |
| JIT specializationimplementation | Observed stability at run time | A failed guard: wasted compilation plus a deoptimization, repeated if the assumption keeps failing |
| Profile-guided specializationtypical | Measured value distribution from a training run | A specialization for a value the production workload does not have — size spent for nothing |
The Futamura projections, and why they are not just a curiosity
If you specialize an interpreter with respect to a program, you get a compiled version of that program. That is the first Futamura projection, and it is exactly the transform shown above: the interpretive dispatch disappears and what remains is the program's own logic.
The result is genuinely used. Truffle and GraalVM build language implementations as interpreters and rely on partial evaluation to turn them into compiled code, so that writing a new language means writing an interpreter rather than a backend. RPython does the same for PyPy, generating a tracing JIT from an interpreter. The projections are not a party trick — they are a production strategy for building language runtimes at a fraction of the usual cost.
The practical version most engineers meet is smaller and just as useful: a function with a mode flag, a regular expression compiled once and matched many times, a sorting routine specialized to a comparator, a database query plan compiled to code. All of them are the same move — separate the inputs that are fixed from the ones that are not, and pay once for the fixed ones.
What it costs, and the honest limit
Every specialization is a copy. Specializing a function for four argument values produces four functions, and the same instruction-cache argument that limits [[inlining]] applies here with more force, because the copies are usually larger. Rust's binary sizes and C++'s template instantiation times are the everyday evidence.
Compile time grows with the number of specializations, and in the template case it grows in a way that is hard to predict from the source: an instantiation is generated per distinct argument list, per translation unit, and then deduplicated by the linker — work done many times and thrown away. This is the mechanism behind build times that scale badly with template use.
The honest limit is that specialization only pays when the static input actually determines a lot. Specializing on a value that appears in one arithmetic operation buys one operation. Specializing on a value that determines a branch, a loop bound, a type, or a dispatch buys everything downstream of it. Before specializing anything by hand, the question is which of those two cases you are in, and the answer is usually visible in the source.
How it works
The steps, in the order the compiler takes them.
- Divide the inputs into static and dynamic — by annotation, by syntax, by analysis, or by run-time observation.
- Propagate the division: any value computed only from static values is static; anything touching a dynamic value is dynamic.
- Evaluate static operations at specialization time, under constant folding's legality conditions.
- Residualize dynamic operations: emit them into the specialized program unchanged, with their static operands replaced by literals.
- Unfold control flow whose condition is static — take the known branch, unroll the known-trip-count loop — and drop the arms that cannot be reached.
- If the static values were speculated rather than proved, emit a guard checking them, with a fallback or a deoptimization point on failure.
- Cache the specialized version keyed on the static values, and bound the cache, or the specialization count grows without limit.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A binary grows dramatically after generic code is used with many type arguments, and the instruction cache stops holding the hot path. The source did not get bigger; the number of instantiations did.
- Compile time becomes the dominant cost of the build, and the profile shows time in template instantiation. Each translation unit is generating the same specializations and the linker is discarding the duplicates.
- A JIT repeatedly specializes, guards, deoptimizes and respecializes, because the assumption is not actually stable. The symptom is a workload that never reaches steady-state performance and burns CPU compiling.
- A hand-written specialization is used with a value it was not specialized for, because someone added a caller. The wrong answer is computed with no error — the failure mode the compiler's version prevents with a guard and hand-written versions usually do not.
- A specialization is generated for a value the training profile contained and production does not, so the binary carries a fast path nothing takes and pays for it in size.
When it helps
- Any interpretive loop with a stable program: a regular expression matched many times, a query plan executed many times, a shader compiled once and run per pixel.
- Generic code where the type argument determines layout and dispatch — the reason monomorphization is worth its binary size in Rust and C++.
- Configuration fixed at startup that drives branches on a hot path: specialize once and the branch disappears rather than being predicted correctly a billion times.
- JIT compilation of dynamically typed code, where specializing on observed types is what makes the language competitive at all —
[[why-runtime-information-helps]].
When it hurts
- When the static value varies more than expected, producing many specializations that each run rarely — all the cost and none of the benefit.
- When the static input barely determines anything, so the residual program is the original program with a few literals substituted.
- When binary size or compile time is a first-class constraint: embedded targets and very large codebases both hit this limit before they hit a performance one.
What it costs
Every one of these is paid by something.
- Specialization buys a smaller, branch-free residual program per static input and pays in code size, once per specialization — the same instruction-cache bill as inlining, usually larger per copy.
- Choosing the static set by observation buys precision no static analysis can match, and costs a guard on every execution plus the machinery to recover when the guard fails.
- Exposing specialization to the programmer as a language feature (
constexpr,const fn) buys a guarantee and a diagnostic instead of a hope, and costs a restricted sublanguage that must be extended one standard revision at a time. - Caching specializations buys reuse and costs memory plus an eviction policy; without a bound, a long-running JIT specializing on unbounded value sets leaks code.
What else you could do
What a different compiler or language does instead, and when that is better.
- Do it by hand: write the specialized function yourself when you know the important case. Verbose and unchecked, but it does not depend on a compiler heuristic and its cost is visible in the source.
- Type erasure instead of monomorphization: one shared implementation with dynamic dispatch, trading run-time cost for a fraction of the code size. Java generics and Swift's default choose this —
[[type-erasure]]. - A table instead of a specialization: precompute the static part into data rather than into code, which costs a lookup and none of the code size.
- Run-time code generation with an explicit API — a JIT you call yourself, as regex engines and query compilers do — which puts the binding-time division in your hands and the compilation cost on your budget.
See it for yourself
The flag, dump or tool that shows you this directly.
- Rust:
cargo llvm-linesranks functions by generated LLVM IR lines and shows which generic instantiations dominate your binary. - C++:
-ftime-tracein Clang produces a build profile showing time per template instantiation, which is the direct view of specialization cost. - GCC:
-fdump-ipa-cp-detailsshows interprocedural constant propagation creating specialized clones of functions with constant arguments — the AOT compiler's version of this transformation. - HotSpot:
-XX:+PrintCompilationwith-XX:+TraceDeoptimizationshows specializations being made and withdrawn as the guards fail. nm --size-sort -Con the binary before and after adding a generic instantiation makes the code-size cost concrete rather than theoretical.
Plausible wrong readings
Stated the way a confident engineer states them.
- "Partial evaluation is an academic idea." It is the mechanism behind template instantiation, monomorphization, JIT type specialization and
constexpr— four things most engineers use every week. - "Specializing always makes it faster." It makes the residual program faster and the binary larger. Past the instruction cache, the second effect wins.
- "A JIT specializes because it compiles at run time." It specializes because it can *observe*. Compiling at run time is what makes observation possible, not the benefit itself.
- "Generics are free abstraction." Monomorphized generics are free at run time and expensive in code size and compile time; erased generics are the opposite. There is no version that is free in both.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
If you know some of a function's inputs in advance, you can bake them in and get a simpler function that only needs the rest. That is all specialization is. Templates, generics and JIT compilation are all doing it in different ways and at different times.
practical
When something is hot and one of its inputs never changes, specializing on that input is usually the largest available win — but check what the input actually determines. If it picks a branch, a loop bound or a type, specialize. If it is one addend, do not. Watch the size and build-time bill: cargo llvm-lines and -ftime-trace are the two tools that make it visible before it becomes a problem.
advanced
The subtle issue is termination and the specialization cache. An online specializer that inlines and unfolds whenever a value is static will not terminate on a recursive function whose static argument grows; offline partial evaluators solve this with a binding-time analysis and explicit generalization, deliberately marking a value dynamic to force termination. JITs solve it with version limits per site and with abandoning sites that exceed them. The same tension appears in a C++ compiler as template instantiation depth limits, and in a tracing JIT as trace length limits — three surfaces of one problem: specialization is unfolding, and unfolding needs a stopping rule that is not derivable from the program.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
constexpr expressions used in constant contexts — the specialization is a language guarantee there, not an optimization. Rust likewise guarantees monomorphization of generics. In both, the code-size consequence is a specified behavior rather than a compiler heuristic you could tune away.If you were asked this in an interview
- What do template instantiation, monomorphization and JIT type specialization have in common?
- A JIT specializes a function on the assumption that a variable is always an integer. What has to be in the generated code for that to be safe?
- When is specializing on a known input not worth doing?
Connections
- Programming Languages & Runtime Internals — The code cache: how many specialized versions a running system keeps, and how it evicts themDeciding what to specialize is ours; storing, sharing and evicting the resulting machine code in a live process is the runtime's, and an unbounded specialization policy shows up there as a memory problem rather than a compiler one.