An eager three-stage chain over a large export versus the same stages run lazily - what differs in traversals and memory?
answer
- count the boundaries, not the stages
- one traversal per stage versus one total
- intermediates disappear, per-element work does not
- peak memory: result plus one element
- n parses either way, k formats either way
basics
~20 sThe eager chain walks the data once per stage and builds a complete collection at every stage boundary. The fused lazy chain walks it once and holds one element in flight, so no collection exists at a boundary - only the final result is built.
solid answer
~40 sAn eager chain of three stages produces three collections: parsed, selected, formatted. The source is walked once by the first stage, the first intermediate is walked by the second, and so on, so peak memory is roughly the largest intermediate plus the result. Fusing the same three stages into a lazy chain collapses them into one traversal: a single element is carried through all three per-element functions, then the next, so the boundary collections are never allocated and peak memory is the result plus one element in flight. What does **not** change is the per-element work - each surviving element still has every stage's function applied to it exactly once, and each dropped element still costs whatever the stages before the drop cost.
code
pseudocode · 6 lines# eager: three stages, three collections, three walks
parsed = map(rows, parse) # collection of size n
discrepant = filter(parsed, isDiscrepant) # collection of size k
report = map(discrepant, format) # collection of size k
# peak: rows + parsed + discrepant (+ report being built)go deeper
Hold on to the picture: an eager chain leaves a finished collection between each pair of stages, a fused chain leaves none and carries one element at a time. Being able to count the collections in a three-stage chain is enough here.
Explain both halves precisely: traversals drop from one per stage to one, and boundary collections drop to zero, while the number of times each stage function is applied is unchanged. The second half is what separates a real answer from a slogan.
Bring the operational consequence: peak memory stops tracking the size of unwanted intermediate data, the first result appears after one element rather than two full passes, and the source can be something read incrementally rather than a materialised collection.
The judgment call is where to spend the fusion. A pipeline whose intermediates are small gains almost nothing and pays per-element overhead; one whose input dwarfs its output changes its memory ceiling, and that is the case worth standardising on.
Take a stock-take export and three stages over it: parse each row into an item, keep the items whose counted quantity differs from the recorded one, format each discrepancy for a report. Written eagerly, that is three statements; written lazily, it is one chain. They compute the same report, and the difference between them is entirely in **how many times the data is walked** and **what exists in memory while it is walked**. ## The eager chain: one traversal per stage Each eager stage is a complete loop. It consumes its whole input, builds a whole output, and returns it. With `n` rows and `k` discrepancies among them, the chain costs: - one walk of `n` rows to build the parsed collection, sized `n`; - one walk of `n` parsed items to build the selected collection, sized `k`; - one walk of `k` items to build the formatted result, sized `k`. That is three traversals and three collections, two of which are **intermediates** - they exist only to be handed to the next stage and are garbage the moment it finishes. Peak memory is roughly the source plus the largest intermediate plus the result. ## The fused chain: one traversal for the chain A lazy chain does not build a stage's output; it builds a **description** of the stages, and the collecting step at the end drives it. One row is pulled, parsed, tested, and either formatted and appended to the result or discarded. Then the next row. The three stage functions have been collapsed into the body of a single loop - which is why the same idea is called fusion. | | Eager chain | Fused lazy chain | |---|---|---| | Traversals of the data | one per stage | one for the whole chain | | Collections built | one per stage, boundaries included | the result only | | Live at peak | largest intermediate plus result | one element plus result | | Applications of each stage function | once per element reaching it | once per element reaching it | | Total per-element work | the same | the same | The last two rows are the ones candidates skip, and they are the honest half of the answer. **Fusion is a memory-and-boundary optimisation, not a work optimisation.** The parse function still runs `n` times and the format function still runs `k` times under both schedules. What disappears is the allocation, filling, walking and collection of the two intermediate collections. ## Why that matters beyond an allocation count - **Peak memory stops scaling with the intermediates.** If the export is far larger than the report, the eager chain's ceiling is set by data nobody wanted; the fused chain's ceiling is set by the report. - **The first result appears much earlier.** The eager chain cannot produce its first formatted line until the export has been fully parsed and fully selected. The fused chain produces it after the first discrepancy. - **The source need not be a collection at all.** A fused chain consumes one element at a time, so it can be driven by something being read incrementally rather than something already in memory - an eager chain has to have the whole input first. - **Locality improves.** One element goes through three functions while it is warm, instead of a whole collection being walked three separate times. - **The boundaries are where the copies were.** People reach for "it is faster" as the benefit; the defensible claim is "it allocates less and starts producing sooner", and on small inputs the per-element machinery of a lazy chain can make it the slower of the two. ## The part that is easy to state backwards The fused chain is not "no collection at all" - the collecting step still builds the result, and if you ask for a result the size of the input you get a collection the size of the input. What it removes is a collection **at each stage boundary**. Equally, "one traversal" is a property of the fused chain, not of laziness as such: a chain containing a stage that cannot emit anything until it has seen every element is walked in more than one segment, and its memory profile goes back to looking eager.
- Does fusing the chain reduce how many times each stage's function is applied?No. Every element that reaches a stage still has that stage's function applied exactly once, under either schedule. Fusion removes the intermediate collections and the extra traversals of them, not the per-element work. Reducing the number of applications is a question of stage order, not of fusion.
- When can an eager chain be the faster of the two despite the extra allocations?On small inputs, where the intermediates are trivial and the per-element indirection of a lazy chain - a demand travelling back through the stages for every element - costs more than the allocations it avoids. It can also win when the same intermediate is consumed more than once, since a lazy chain would recompute it per consumer.
- How does the time to the first output differ between the two?The eager chain emits nothing until every earlier stage has finished over the whole input, so the first formatted item appears after two full traversals. The fused chain emits its first formatted item as soon as one element has made it through all three stages, which matters whenever the consumer is a reader or a writer rather than a final collection.
saying these in an interview costs you the question
- Says a fused chain builds no collection at all, forgetting the result
- Claims fusion reduces how many times each stage function runs
- Thinks the eager chain walks the source once and mutates it in place
- Assumes lazy is always faster, ignoring per-element overhead
- Counts three stages as three intermediates rather than two boundaries
- Believes memory falls because elements are smaller, not because boundaries vanish