skip to content

A first-match search runs after an expensive transform stage - why does eager evaluation call that transform more often than lazy evaluation does?

level: middleimportance: should knowfreq 50%

answer

  1. who asks for the next element
  2. stage completes first, or on demand
  3. the terminal step drives the pull
  4. calls counted up to the hit, inclusive
  5. no match means both models pay the same

basics

~20 s

Under eager evaluation the transform stage finishes over the whole input before the search ever begins, so it runs once per element. Under lazy evaluation the search pulls elements one at a time and stops at the match, so the transform runs only up to that element.

solid answer

~50 s

Who drives the work is the whole difference. In an **eager** pipeline each stage completes over the entire input and hands a finished result to the next, so the expensive transform runs `n` times whatever the search finds. In a **lazy** pipeline the terminal step is the driver: the search asks for one element, the transform produces one element, and the moment the search has its match it stops asking. If the match is at index `k`, the transform ran `k + 1` times. The saving is not a cleverer transform - it is the elements that never reach it. Two things temper the win: a search that finds nothing pulls the whole input anyway, and if the transform had effects the team relied on, those effects now happen only for the prefix that was pulled.

code

pseudocode · 7 lines
pseudocode
// eager: the stage finishes before the search starts
transformed = mapAll(items, expensiveTransform)      // 1000 calls
result = firstWhere(transformed, isMatch)            // match at index 4

// lazy: the search pulls one element at a time
result = firstWhere(lazyMap(items, expensiveTransform), isMatch)
// expensiveTransform runs 5 times, for indexes 0 through 4

go deeper

for a junior

Know that a search which stops at the first match can spare the work of the stage before it, but only when that stage produces elements on demand rather than finishing over the whole input first.

for a middle

Count the calls out loud for a concrete index and get the inclusive boundary right, and explain that the terminal step drives the demand rather than the stages predicting anything.

for a senior

Spot the no-match path where both models cost the same, and the effectful stage whose behaviour quietly changes when the pipeline becomes demand-driven; say how you would detect that in a running system.

for a principal

Decide where effects are allowed to live at all, so that a stage's call count is never an accident of what a downstream step happened to need on a given input.

## Two models of who drives the work A staged pipeline - produce, transform, then search - can be evaluated in two ways, and the difference is about **who asks for the next element**. - **Eager (each stage completes first).** The transform stage is applied to every element of the input, producing a finished result; only then does the search stage begin, over that result. The search's early exit still happens, but it happens *after* all the transform work is already done. - **Lazy (the terminal step drives).** The search asks for an element. That demand travels back through the transform to the source, one element at a time. When the search has what it needs it stops asking, and every stage upstream simply stops being called. The question this leaf asks is not how many traversals happen or how the stages are arranged internally - it is **how many elements ever reach each stage**. ## Counting it out Take a 1000-element input, an expensive transform, and a search for the first transformed element satisfying a predicate, where that element is at index 4. | Model | Transform calls | Predicate calls | Source elements read | |---|---|---|---| | Eager | 1000 | 5 | 1000 | | Lazy | 5 | 5 | 5 | Indexes 0, 1, 2, 3 and 4 are pulled, so five elements pass through the transform - the match is included, not excluded. Getting that off-by-one wrong is a common slip at the whiteboard, and an interviewer will usually ask you to walk the indexes. ## Why the earlier stage stops running In the lazy model the stages do not know anything about the search. There is no prediction and no analysis. The mechanism is simply that a stage does work when it is **asked for a value**, and once the terminal step has settled the answer it stops asking. Nothing upstream needs to be told; it is never called again. This is why the win grows with the pipeline's depth: every stage between the source and the search is spared the same `n - (k + 1)` elements, so an expensive stage near the front benefits most. ## When the lazy model does not help 1. **The search finds nothing.** With no match, the terminal step keeps asking until the source is exhausted, and the transform runs `n` times - exactly the eager count. 2. **The match is near the end.** `k` close to `n` means almost nothing is saved, and the per-element bookkeeping of demand-driven evaluation may even cost a little more. 3. **The transform is cheap.** The saving is proportional to the transform's per-element cost; skipping cheap work saves little. 4. **The transform has effects that were relied upon.** This is the trap that bites in production. If the transform writes a record, increments a counter, or warms a cache, converting the pipeline from eager to lazy quietly reduces those effects to the pulled prefix. Nothing fails; the numbers just get smaller. A stage with effects the system depends on does not belong in a pipeline whose length is decided by a downstream search. ## Reading the shape in review The tell is a terminal step that can stop - a first match, an existence check, a bounded prefix - sitting behind a stage whose per-element cost is real: a parse, a decode, a remote lookup, a hash. When the pipeline is eager, that stage's cost is paid `n` times to answer a question that needed `k + 1`. When it is lazy, the same source code costs what the answer costs. The practical judgment to state out loud is where `k` actually falls on your data. 'Lazy is faster' is not an answer; 'our matches are usually in the first hundred of a few million, so the transform runs a hundred times instead of millions, except on the no-match path where both models pay the same' is. ## One boundary worth naming Whether the stages are collapsed into a single traversal is a different question from how far the traversal reaches. This one is about the reach: how many elements ever enter the pipeline before the answer is settled.

  • The team converts the pipeline from eager to lazy and a downstream counter drops. What happened?
    The transform stage was not pure - it was incrementing that counter per element. Eagerly it ran `n` times; lazily it runs only for the elements the search pulled. The pipeline's result is unchanged, so nothing fails, and the only symptom is a metric that no longer matches the input size. Effects belong outside a stage whose call count is decided downstream.
  • Does the lazy model help when the search finds no match at all?
    No. Without a match the terminal step keeps demanding elements until the source is exhausted, so every element passes through the transform and the call count matches the eager model. The lazy model never does more elements than eager - it just does not always do fewer.

saying these in an interview costs you the question

  • Says the lazy pipeline transforms only the matched element.
  • Thinks the transform stage inspects the search predicate and skips work.
  • Claims laziness helps equally when no element matches.
  • Counts the calls as the match index rather than index plus one.
  • Assumes moving an effectful stage into a lazy pipeline is behaviour-preserving.