Inlining Heuristics

Every time your program calls a function, the CPU pushes a return address, shuffles arguments into registers, jumps to the callee, and eventually jumps back. For a tiny helper — say, abs(x) or a one-line getter — that overhead can dwarf the actual work.

Inlining is the compiler's answer: instead of emitting a call instruction, just paste the callee's body directly into the caller. The call overhead vanishes, and now the surrounding code can see through the boundary — constant-folding, dead-code elimination, and further optimizations become possible.

The catch is code size. Each inline creates a fresh copy of the callee's instructions at every call site. A function called in a hundred places, each copy bloating the binary, spills the instruction cache and often costs more than the call overhead it replaced. So the compiler must answer: does the benefit of inlining outweigh the cost of growth?

That question has no closed-form solution. Instead, every production compiler — GCC, LLVM/Clang, javac's JIT — runs a heuristic: a scoring rule that estimates the gain and compares it to a size budget. Getting the threshold right is, quietly, one of the most consequential knobs in an optimizing compiler.

Adjust the callee size (in instructions) and the call overhead to see whether the heuristic would inline the call. The green region is where inlining wins; the red region is where the copy costs too much.

<!-- {{c_html_intro}} -->
<div class="panel">
  <div class="controls">
    <label class="ctrl-row">
      <span class="lbl">{{lbl_callee_size}}</span>
      <input type="range" id="sizeSlider" min="1" max="200" value="20" />
      <span class="val" id="sizeVal">20</span>
      <span class="unit">{{unit_instr}}</span>
    </label>
    <label class="ctrl-row">
      <span class="lbl">{{lbl_call_overhead}}</span>
      <input type="range" id="overheadSlider" min="1" max="50" value="10" />
      <span class="val" id="overheadVal">10</span>
      <span class="unit">{{unit_instr}}</span>
    </label>
    <label class="ctrl-row">
      <span class="lbl">{{lbl_call_sites}}</span>
      <input type="range" id="sitesSlider" min="1" max="20" value="3" />
      <span class="val" id="sitesVal">3</span>
    </label>
    <label class="ctrl-row">
      <span class="lbl">{{lbl_threshold}}</span>
      <input type="range" id="threshSlider" min="10" max="150" value="50" />
      <span class="val" id="threshVal">50</span>
      <span class="unit">{{unit_instr}}</span>
    </label>
  </div>
  <div class="verdict-box" id="verdict"></div>
  <canvas id="chart" width="420" height="180" aria-label="{{chart_aria}}"></canvas>
  <div class="legend">
    <span class="leg-item leg-green">{{leg_inline_wins}}</span>
    <span class="leg-item leg-red">{{leg_too_large}}</span>
    <span class="leg-item leg-line">{{leg_breakeven}}</span>
  </div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.panel { padding: .5rem .2rem; }
.controls { display: flex; flex-direction: column; gap: .6rem; margin-bottom: .8rem; }
.ctrl-row { display: flex; align-items: center; gap: .5rem; font-size: .88rem; }
.lbl { width: 130px; flex-shrink: 0; font-weight: 600; color: #1d3557; }
.ctrl-row input[type=range] { flex: 1; accent-color: #1d3557; }
.val { font-weight: 700; font-variant-numeric: tabular-nums; min-width: 2.5ch; text-align: right; }
.unit { color: #555; font-size: .8rem; width: 56px; flex-shrink: 0; }
.verdict-box { font-size: 1rem; font-weight: 700; padding: .45rem .8rem; border-radius: 8px;
               margin-bottom: .6rem; min-height: 2.2em; line-height: 1.35; }
.verdict-box.inline { background: #d4edda; color: #0a7d33; border: 1px solid #a3d9a5; }
.verdict-box.skip   { background: #fde8e8; color: #c92f3c; border: 1px solid #f5b8b8; }
canvas { display: block; max-width: 100%; border-radius: 8px; border: 1px solid #dde3ea; }
.legend { display: flex; gap: .9rem; flex-wrap: wrap; margin-top: .4rem; font-size: .8rem; }
.leg-item { display: flex; align-items: center; gap: .3rem; }
.leg-item::before { content: ''; display: inline-block; width: 14px; height: 14px; border-radius: 3px; }
.leg-green::before { background: rgba(10,125,51,.18); border: 1px solid #0a7d33; }
.leg-red::before   { background: rgba(201,47,60,.12); border: 1px solid #c92f3c; }
.leg-line::before  { background: #1d3557; height: 3px; border-radius: 2px; }

// Code not found

Notice how a very small callee almost always inlines — the copy is tiny and the overhead savings are proportionally large. As the callee grows, the breakeven point shifts until copying it everywhere hurts more than the call tax it saved.

The local rule — inline if callee size $\leq$ threshold — is fast and widely used, but it is provably not optimal.

The real problem is global: given a call graph, a per-call benefit estimate, and a total code-size budget $B$, choose the subset of calls to inline so that total estimated benefit is maximized without exceeding $B$. This is exactly the knapsack problem — NP-hard in general.

Production compilers handle this tension in layers:

• Local threshold rule: inline any call whose callee has fewer than $k$ instructions (LLVM's default is around 225 "cost units"). Fast, $O(E)$ over call edges, but ignores interactions between sites.
• Benefit estimation: modern compilers weight the threshold by estimated speedup — a callee that enables constant folding at the call site gets a bonus, pushing it below the threshold even if it is large.
• Inlining budgets: a per-function or per-translation-unit cap prevents runaway growth even when many callees individually pass the threshold.
• Call-graph aware passes: tools like GCC's interprocedural analysis and LLVM's inline advisor (including an ML-based model) try to approximate the global optimum without solving the full NP-hard problem.

The unsolvable core means every compiler ships a heuristic. Benchmark suites like SPEC CPU exist partly to tune these heuristics — and a single threshold change can swing total runtime by several percent across a large code base.

Inlining heuristics are one of those invisible decisions that shape performance across every language ecosystem:

• C and C++: GCC and Clang both expose -finline-limit and per-function __attribute__((always_inline)) / __attribute__((noinline)) overrides. Getting the default threshold wrong by 10 % can swing a benchmark by 3–5 %.
• Rust: the MIR (Mid-level IR) inliner runs before LLVM, applying its own threshold on MIR body size, then lets LLVM inline again at the IR level. The two-stage process is one reason Rust can produce very tight binaries.
• Java JIT: the HotSpot server JIT inlines aggressively once a call site is "hot" (called $\geq 10{,}000$ times by default), with a bytecode-size threshold around 35 bytes. Inlining drives most of the speed gap between Java and C++ in tight loops.
• JavaScript engines: V8 (Turbofan) and SpiderMonkey inline small callees speculatively, deoptimizing back to the interpreter if a hidden-class assumption breaks. The heuristic must balance inline gain against the cost of potential deoptimization.
• Machine-learning advisors: LLVM's experimental ML inliner (part of MLGO) replaces the hand-tuned threshold with a reinforcement-learning policy trained on large code corpora — trading explainability for a few extra percent on benchmarks.

The knapsack structure of the global problem connects inlining directly to program synthesis and non-convex optimization: you are searching a combinatorial space where the objective is hard to evaluate and interactions between decisions matter.

Inlining looks deceptively simple: paste the callee, remove the call, go faster. But behind that one-liner sits a global knapsack problem — choosing which calls to inline to maximize speed without blowing the code-size budget — and that problem is NP-hard.

Production compilers answer with fast local heuristics: a size threshold, a benefit bonus, a budget cap. These heuristics are tuned against benchmark suites, tweaked between releases, and occasionally replaced by ML policies. They are not optimal, and every compiler vendor knows it.

So the next time a profiler shows a hot function that somehow doesn't inline, look for the threshold. Somewhere in the compiler's cost model, a callee grew just a few instructions past the budget — and the globally correct answer was quietly left on the table.