skip to content

A trampolined step chain runs measurably slower than the direct recursion it replaced; what is each step now paying for?

level: seniorimportance: nice to knowfreq 28%

answer

  1. every turn now costs something
  2. look at what each step builds
  3. one allocation per step
  4. an invocation the compiler cannot see through
  5. safety bought with churn and lost inlining

basics

~20 s

Every step now allocates a description of the next call and is reached through an indirect invocation the compiler cannot see through, plus a loop turn and a tag check. The safety is bought with allocation churn and lost inlining.

solid answer

~40 s

In the direct version a step calls a known function. In the trampolined version it builds a value, returns it, and the loop invokes it through a reference. That adds, per step: one allocation for the description plus anything it captured; an indirect invocation, which blocks inlining and makes the branch harder to predict; one loop turn with a tag check; and churn on whatever reclaims memory. None of it is large, but it is paid n times on a chain of n steps and it is paid even when the chain is three steps long. What you buy is that chain length stops being a limit, and that every step passes through one place you control.

code

pseudocode · 8 lines
pseudocode
function processFrom(step, depth)
    if step.isFinal then
        return Done(step.result)
    if depth >= 1000 then
        return More(function() processFrom(step.next, 0))
    return processFrom(step.next, depth + 1)

// direct for 1000 steps, then one bounce; depth never exceeds 1000

go deeper

for a junior

Remember that the safe version is not the free version: building a value for every step and calling it through a reference costs something, even though each piece is small.

for a middle

Be able to list the costs concretely — an allocation per step, an indirect invocation that blocks inlining, a tag check per turn, and steady churn — rather than saying it is slower.

for a senior

Show the measurement instinct: compare per class of chain, note that the overhead is a fraction of per-step work, and offer a mitigation such as running directly up to a counted threshold before bouncing.

for a principal

The call is where the boundary sits. Bounce at the edge whose length is decided by data you do not control, keep the direct call inside bounded walks, and say what the coarser intervention point costs when you batch steps.

## What one step pays after the rewrite The direct version calls a function the compiler can see. The trampolined version builds a value, returns it, and lets a loop invoke it. That difference shows up as several small costs, each paid once per step in a chain of n steps: - **An allocation per step.** The description is an object — a zero-argument function, or a tagged value naming the next step. If it captures anything from the step that built it, that capture is allocated too. - **An indirect invocation.** The loop calls through a reference whose target varies. A compiler that could have inlined a direct self-call generally cannot inline this, so the step body stays a real call with real argument passing. - **A worse-predicted branch.** Each turn tests which variant came back. The test itself is trivial; what costs is that the processor is now guessing at an indirect target rather than running straight-line code. - **Churn.** Descriptions are made and dropped at the rate of one per step. Wherever memory is reclaimed automatically, that is steady pressure; where it is not, it is explicit bookkeeping someone has to write. - **Lost locality.** The straight recursive version keeps everything in a tight loop of code and data; the bounced version bounces through the driver, touching a freshly allocated value each turn. ## What the payment buys - **Chain length stops being a limit.** The only property that changed qualitatively is that depth no longer decides whether the program survives — a constant-factor cost in exchange for removing a cliff. - **One place everything passes through.** Every step goes through the loop, so a depth budget, a step counter, a cancellation check or an audit trail is written once instead of trusted to every step. - **Steps become inspectable.** A description is a value, so it can be examined or logged before it is run, which a direct call never allows. ## Reading the measurement honestly The comparison only makes sense per class of chain: | chain | direct recursion | trampolined | verdict | |---|---|---|---| | a few dozen steps, bound fixed by design | fast, always safe | same result, measurably slower | overhead buys nothing | | thousands, bounded by something you control | fast, safe while the bound holds | slower, safe | judgment call, watch the bound | | length decided by input data | fast until it dies | slower, survives | the overhead is the price of correctness | | deep, and each step does heavy work | fast, dies at depth | overhead lost in the noise | easy yes | The last row is the one people forget. Per-step overhead is a *fraction* of per-step work: where a step parses a document or calls out to something, the allocation and the indirect invocation disappear into the measurement. Where a step adds two numbers, the overhead can dominate. ## Making it cheaper without giving the safety back 1. **Bounce only where depth is unbounded.** Recurse directly inside a step that recurses over a bounded shape, and bounce only the walk whose length is set by data. 2. **Bounce after a counted run.** Run directly and count; once the count reaches a threshold safely below the limit, return a description and let the loop resume from there. Depth stays bounded while most steps pay nothing. 3. **Batch the work per description.** Have one description advance several steps before returning, trading a coarser cancellation point for a fraction of the allocations. 4. **Reuse the carrier.** Where a mutable value can be returned and rewritten each turn rather than freshly built, the allocation disappears and only the indirect invocation remains — at the price of a value that cannot be retained or shared. ## The judgment The wrong reading of a slow benchmark is to abandon the rewrite; the wrong reading of a safe test is to apply it everywhere. The question is always which kind of chain this is. A depth that a fixed region comfortably holds, and that the engine's own design bounds, does not need the rewrite, and adopting it there imposes a style on everyone who reads the code for a failure that cannot happen. A depth decided by data you do not control needs it, and the overhead is not a trade-off at all — it is what correctness costs. One more honest note: the direct version is not merely faster, it is also easier to read and to debug, because its control flow is the language's own. That readability is part of what the overhead buys back, and it is worth naming when arguing for or against the change.

  • When does the per-step overhead stop mattering in a measurement?
    When per-step work is large relative to it. An allocation and an indirect invocation are fixed, small costs; a step that reads a record, validates it or calls another service dwarfs them. The overhead dominates only where the step itself is near-trivial, which is exactly where a benchmark makes the rewrite look worst.
  • Why would you run directly for a counted number of steps before bouncing?
    Because most of the cost is per step while the risk is only at depth. Running directly up to a threshold safely below the limit keeps the depth bounded by that threshold, and pays for one description per threshold-many steps instead of one per step. The price is a coarser point at which the loop can intervene.

saying these in an interview costs you the question

  • Assumes the trampolined version costs about the same as a plain loop
  • Says the only overhead is one extra turn of the loop
  • Claims returning a function allocates nothing
  • Dismisses per-step allocation as free because the values die young
  • Applies the rewrite to short chains whose depth is fixed by design