skip to content

Analyze allocation and pass count for a multi-step pipeline run eagerly vs as a Sequence over large data. What exactly differs?

level: seniorimportance: should knowfreq 45%

answer

  1. Eager: passes = #operators, intermediate list per step
  2. Lazy: 1 fused pass, only wrapper allocs (O(stages))
  3. Short-circuit shrinks work + final array
  4. sorted/distinct/chunked buffer -> break fusion
  5. Filter early, sort late, mapNotNull to fuse

basics

~20 s

Eager makes a new list at every step and walks the whole data once per step. A Sequence makes no intermediate lists and walks each element once through all steps, stopping early if a terminal allows.

solid answer

~40 s

For a chain `filter -> map -> filter` on an n-element `List`, the eager path makes three full passes and allocates up to three intermediate `List`s (sized to each stage's output), plus the final result. Total memory churn is roughly proportional to the sum of intermediate sizes. The `Sequence` path makes one fused pass: each element is pulled once and flows through all three stages, allocating only wrapper iterators (constant, independent of n) and the final materialized result. If the terminal short-circuits (`take`, `first`), the Sequence also reduces the element count processed. The catch: a **stateful** intermediate op (`sorted`, `distinct`, `chunked`) forces buffering, so it allocates and breaks the single-pass/short-circuit property for downstream stages. Net: Sequences cut intermediate allocations and passes; place stateless filtering early to maximize the win.

code

kotlin · 6 lines
kotlin
// Fuse filter+map and keep reducing ops early
val out = data.asSequence()
    .mapNotNull { it.parseOrNull() } // filter + map in one stage
    .filter { it.isActive }
    .take(100)
    .toList() // single fused, short-circuited pass

go deeper

for a junior

Knows Sequences avoid intermediate lists.

for a middle

Counts passes and intermediate allocations for eager vs lazy on a simple chain.

for a senior

Models allocation as O(stages) for Sequence vs sum-of-stage-sizes for eager and reorders ops to preserve fusion/short-circuit.

for a principal

Profiles allocations with async-profiler/JFR, sets pipeline-ordering conventions, and weighs readability against the measured win.

## Setup Consider `data.<...>.filter { p1 }.map { f }.filter { p2 }` over n large elements, materialized to a list. ## Eager (Iterable/List) cost model Each operator is a full, independent pass that allocates a fresh result list: 1. `filter { p1 }` — reads all n, allocates list of size n1 (≤ n). 2. `map { f }` — reads all n1, allocates list of size n1. 3. `filter { p2 }` — reads all n1, allocates list of size n2 (≤ n1). - **Passes:** 3 (one per operator). - **Intermediate allocations:** ~ (n1) + (n1) + (n2) elements across three backing arrays (which may also resize/grow as they fill). - **No early exit:** even if the terminal is `first`, every stage materialized fully first. ## Lazy (Sequence) cost model ```kotlin data.asSequence() .filter { p1 } // intermediate, lazy .map { f } // intermediate, lazy .filter { p2 } // intermediate, lazy .toList() // terminal: single fused pass ``` - **Passes:** 1 fused pass. Each element is pulled once and threaded through `p1`, then `f`, then `p2`. - **Intermediate allocations:** only the wrapper `Sequence`/iterator objects — O(number of stages), **independent of n**. No per-stage data arrays. - **Short-circuit:** swap `toList()` for `take(k).toList()` or `first { }` and the pass stops after k results, cutting both work and the final array size. ## Where the model breaks: stateful intermediates ```kotlin data.asSequence() .map { f } .sorted() // STATEFUL: must drain & buffer all upstream .filter { p2 } .first() // cannot short-circuit past sorted() ``` - `sorted` / `sortedBy` buffer everything into an array and sort it — O(n) memory and a full upstream drain before emitting. - `distinct` keeps a `HashSet` of seen keys — extra memory, but still streams output. - `chunked` / `windowed` buffer per chunk. Downstream of a stateful op you lose the single-pass and short-circuit benefits, though stages *before* it still stream. ## Practical optimization rules - Put **stateless, reducing** ops (`filter`, `take`) as early as possible so fewer elements reach expensive stages. - Keep `sorted`/`distinct` as late and as small-input as possible. - Prefer `mapNotNull`/`filterIsInstance` to fuse a filter+map into one stage. - Materialize once at the end with a single terminal; don't re-iterate a Sequence (it may be one-shot/`constrainOnce`). ## Measuring it Allocation differences are visible via async-profiler's allocation mode or JFR; pass counts via simple counters in the lambdas. Don't infer from wall-clock alone on small inputs.

  • How many intermediate data arrays does a 4-operator eager chain allocate vs the Sequence equivalent?
    Eager allocates roughly four intermediate lists (one per stage). The Sequence allocates none for data — only a constant number of wrapper iterator objects plus the final materialized result.
  • Why might re-iterating a Sequence throw or recompute?
    Sequences from builders or constrainOnce() are single-use and throw on second iteration; others recompute the whole pipeline each iteration since they hold no buffered result.

saying these in an interview costs you the question

  • Saying Sequences allocate an intermediate list per step
  • Ignoring that sorted/distinct buffer and break fusion
  • Assuming short-circuit works after a stateful op
  • Re-iterating a one-shot Sequence
  • Not ordering filters before expensive stages

context

resolving links…