Introduction

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.

Try It

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.

<!-- Inlining heuristic demo: sliders control callee size, call overhead, call sites, and the size threshold. -->
<div class="panel">
  <div class="controls">
    <label class="ctrl-row">
      <span class="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">instr.</span>
    </label>
    <label class="ctrl-row">
      <span class="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">instr.</span>
    </label>
    <label class="ctrl-row">
      <span class="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">Size threshold</span>
      <input type="range" id="threshSlider" min="10" max="150" value="50" />
      <span class="val" id="threshVal">50</span>
      <span class="unit">instr.</span>
    </label>
  </div>
  <div class="verdict-box" id="verdict"></div>
  <canvas id="chart" width="420" height="180" aria-label="Chart showing inline vs skip regions as callee size grows"></canvas>
  <div class="legend">
    <span class="leg-item leg-green">Inline wins</span>
    <span class="leg-item leg-red">Too large / no gain</span>
    <span class="leg-item leg-line">Threshold</span>
  </div>
</div>

/* Styles for the inlining heuristic demo panel. */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Inlining heuristic simulator. */

/* Model: a callee of `size` instructions is called at `sites` call sites. */
/* Benefit of inlining = call overhead saved at every site. */
/* Cost of inlining = extra instructions added at every site (size * (sites-1) net, since one copy replaces the call). */
/* Decision: inline iff callee <= threshold AND net gain > 0. */

function computeDecision(size, overhead, sites, threshold) {
  const benefit = overhead * sites;          /* total call overhead saved */
  const cost    = size * (sites - 1);        /* net extra instructions (size copies minus the one that replaces the call) */
  const netGain = benefit - cost;
  const belowThreshold = size <= threshold;
  return { benefit, cost, netGain, belowThreshold, inline: belowThreshold && netGain > 0 };
}

/* Draw the chart: green region = inline wins, red = skip. */
function draw(size, overhead, sites, threshold) {
  const canvas = document.getElementById('chart');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  const PAD = { top: 16, right: 16, bottom: 36, left: 48 };
  const cw = W - PAD.left - PAD.right;
  const ch = H - PAD.top  - PAD.bottom;
  const maxSize = 200;

  ctx.clearRect(0, 0, W, H);

  /* color each pixel column by the inline decision at that callee size */
  for (let px = 0; px < cw; px++) {
    const s = Math.round((px / cw) * maxSize) || 1;
    const r = computeDecision(s, overhead, sites, threshold);
    ctx.fillStyle = r.inline ? 'rgba(10,125,51,.14)' : 'rgba(201,47,60,.10)';
    ctx.fillRect(PAD.left + px, PAD.top, 1, ch);
  }

  /* draw axes */
  ctx.strokeStyle = '#bbb';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD.left, PAD.top); ctx.lineTo(PAD.left, PAD.top + ch);
  ctx.lineTo(PAD.left + cw, PAD.top + ch);
  ctx.stroke();

  /* draw benefit and cost curves */
  const maxY = Math.max(overhead * sites * 1.2, 10);
  function toY(v) { return PAD.top + ch - (v / maxY) * ch; }
  function toX(s) { return PAD.left + (s / maxSize) * cw; }

  /* benefit line (constant = overhead * sites) */
  ctx.strokeStyle = '#0a7d33'; ctx.lineWidth = 2;
  ctx.setLineDash([4, 3]);
  ctx.beginPath();
  for (let s = 1; s <= maxSize; s++) {
    const y = toY(overhead * sites);
    s === 1 ? ctx.moveTo(toX(s), y) : ctx.lineTo(toX(s), y);
  }
  ctx.stroke();

  /* cost line (grows linearly with size) */
  ctx.strokeStyle = '#c92f3c'; ctx.lineWidth = 2;
  ctx.setLineDash([4, 3]);
  ctx.beginPath();
  for (let s = 1; s <= maxSize; s++) {
    const y = toY(s * (sites - 1));
    s === 1 ? ctx.moveTo(toX(s), y) : ctx.lineTo(toX(s), y);
  }
  ctx.stroke();
  ctx.setLineDash([]);

  /* vertical threshold line */
  ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 2;
  ctx.beginPath();
  const tx = toX(threshold);
  ctx.moveTo(tx, PAD.top); ctx.lineTo(tx, PAD.top + ch);
  ctx.stroke();

  /* markers at current callee size */
  const markerX = toX(size);
  ctx.fillStyle = '#e63946'; ctx.beginPath();
  ctx.arc(markerX, toY(size * (sites - 1)), 5, 0, Math.PI * 2); ctx.fill();
  ctx.fillStyle = '#0a7d33'; ctx.beginPath();
  ctx.arc(markerX, toY(overhead * sites), 5, 0, Math.PI * 2); ctx.fill();

  /* axis labels */
  ctx.fillStyle = '#444'; ctx.font = '11px system-ui, sans-serif'; ctx.textAlign = 'center';
  ctx.fillText('0', PAD.left, PAD.top + ch + 20);
  ctx.fillText('100', toX(100), PAD.top + ch + 20);
  ctx.fillText('200', toX(200), PAD.top + ch + 20);
  ctx.textAlign = 'left';
  ctx.fillText('Callee size (instr.)', PAD.left + cw / 2 - 30, PAD.top + ch + 32);
  ctx.save(); ctx.translate(12, PAD.top + ch / 2); ctx.rotate(-Math.PI / 2);
  ctx.textAlign = 'center'; ctx.fillText('Instructions', 0, 0); ctx.restore();
}

function updateVerdict(size, overhead, sites, threshold) {
  const r = computeDecision(size, overhead, sites, threshold);
  const box = document.getElementById('verdict');
  if (r.inline) {
    box.className = 'verdict-box inline';
    box.textContent = i18nFmt('Inline — size %size% <= threshold %threshold%, net gain %gain% instr.', { size, threshold, gain: r.netGain });
  } else if (!r.belowThreshold) {
    box.className = 'verdict-box skip';
    box.textContent = i18nFmt('Skip — size %size% exceeds threshold %threshold%.', { size, threshold });
  } else {
    box.className = 'verdict-box skip';
    box.textContent = i18nFmt('Skip — copy cost %cost% instr. exceeds call savings %benefit% instr.', { cost: r.cost, benefit: r.benefit });
  }
}

function getVals() {
  return {
    size:     +document.getElementById('sizeSlider').value,
    overhead: +document.getElementById('overheadSlider').value,
    sites:    +document.getElementById('sitesSlider').value,
    threshold:+document.getElementById('threshSlider').value
  };
}

function refresh() {
  const { size, overhead, sites, threshold } = getVals();
  document.getElementById('sizeVal').textContent     = size;
  document.getElementById('overheadVal').textContent = overhead;
  document.getElementById('sitesVal').textContent    = sites;
  document.getElementById('threshVal').textContent   = threshold;
  draw(size, overhead, sites, threshold);
  updateVerdict(size, overhead, sites, threshold);
}

['sizeSlider','overheadSlider','sitesSlider','threshSlider'].forEach(id => {
  document.getElementById(id).addEventListener('input', refresh);
});
refresh();
Result
Console

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 Real Complexity

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 BB, choose the subset of calls to inline so that total estimated benefit is maximized without exceeding BB. 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 kk instructions (LLVM's default is around 225 "cost units"). Fast, O(E)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.

Where It Matters

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 ≥10,000\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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/inlining-heuristics/Content licensed under CC BY-NC 4.0.