skip to content

IntProgression implements Iterable<Int>, yet `for (i in 0..n)` rarely allocates. Explain how iteration works and when the compiler optimization does or doesn't kick in.

level: seniorimportance: should knowfreq 35%

answer

  1. Iterable via IntIterator.nextInt(), no boxing on hot path
  2. for-over-range lowered to primitive while loop
  3. snapped last + overflow guard => safe termination
  4. Up-cast to Iterable or .forEach loses lowering
  5. Prefer for(i in a..b) over (a..b).forEach in hot loops

basics

~20 s

A progression knows how to hand out numbers one by one through an iterator. But when you write a simple for-loop over a literal range, the compiler turns it into a plain counting loop with no extra objects, so it's fast.

solid answer

~50 s

`IntProgression` implements `Iterable<Int>` via `iterator()`, returning an `IntIterator` whose `nextInt()` walks `first` toward `last` by `step` and stops when the next value would pass `last`. That path involves an iterator object and boxing only if you treat elements as `Int?`/`Any`. However, when the compiler sees `for (i in a..b)` (or `a until b`, `downTo`, `step` with statically-known progression shape), it **lowers** the loop into an index-based `while` loop over primitive ints — no iterator allocation, no boxing. This optimization applies when the loop subject is recognized as a range/progression expression. If you instead store the progression in a variable typed as `Iterable<Int>` and loop over that, or call `.forEach { }`, the optimization is lost and you pay for an iterator and boxing. Overflow at `Int.MAX_VALUE` is handled by the snapped `last` so the loop terminates safely.

code

kotlin · 12 lines
kotlin
// Lowered: no allocation, primitive ints
for (i in 0..n) use(i)

// NOT lowered: iterator allocated, Int boxed
val r: Iterable<Int> = 0..n
for (i in r) use(i)

// NOT lowered like the for-statement: lambda + iterator
(0..n).forEach { use(it) }

// Terminates safely thanks to snapped last + overflow guard
for (i in (Int.MAX_VALUE - 2)..Int.MAX_VALUE) print(i)

go deeper

for a junior

Knows a for-loop over a range works and is fast; may not know why.

for a middle

Knows Iterable is implemented and that simple for-loops are efficient.

for a senior

Explains the compiler lowering to a primitive while-loop and when up-casting or forEach defeats it.

for a principal

Reasons about IntIterator/nextInt boxing avoidance, the overflow-safe termination, and codegen trade-offs across loop forms.

## The Iterable contract `IntProgression : Iterable<Int>` provides `override fun iterator(): IntIterator`. `IntIterator` is a specialized `Iterator<Int>` with a primitive `nextInt()` to avoid boxing on the hot path. The iterator holds the current value, the `last`, the `step`, and a `hasNext` flag; `next()` returns the current value then advances by `step`, finishing when it would move past `last`. ## Why the snapped `last` matters for termination Progressions store the **already-snapped** `last` (the final reachable element). The iterator compares against that, and there's a guard so it doesn't overflow when stepping past `Int.MAX_VALUE`. That's why `(0..Int.MAX_VALUE)` terminates rather than wrapping around forever. ## Compiler loop-lowering (the optimization) For a statically recognizable range/progression directly in the `for`, the Kotlin compiler rewrites: ```kotlin for (i in 0..n) { use(i) } ``` roughly into: ```kotlin if (0 <= n) { var i = 0 while (true) { use(i) if (i == n) break i++ } } ``` No `IntRange` object, no iterator, no boxing — pure primitive ints. The same lowering applies to `until`, `downTo`, `step`, `indices`, and `withIndex` patterns the compiler understands. ## When you LOSE the optimization ```kotlin val r: Iterable<Int> = 0..n // erased to Iterable for (i in r) { ... } // iterator allocated, Int boxed (0..n).forEach { ... } // lambda + iterator; not lowered like for ``` Key triggers that defeat lowering: - Up-casting the progression to `Iterable<Int>`/`Sequence`/`Collection` before the loop. - Using `.forEach`/`.map`/functional operators instead of a `for`-statement. - Passing the progression through a generic function that erases the concrete type. ## Practical guidance - Prefer `for (i in a..b)` over `(a..b).forEach { }` in hot loops to keep it allocation-free. - Don't pre-store a literal range as `Iterable<Int>` if you only loop it. - The functional style is fine for readability off the hot path — measure before optimizing. ## Key takeaways - Iteration is defined via `IntIterator.nextInt()`; the snapped `last` and an overflow guard ensure safe termination. - The compiler lowers direct `for`-over-range to a primitive while-loop (no allocation/boxing). - Up-casting to `Iterable` or using `.forEach` reintroduces iterator allocation and boxing.

  • Does `(0..n).forEach { }` get the same allocation-free treatment as `for (i in 0..n)`?
    No. The for-statement lowering is special; forEach goes through a lambda and the iterator, so it allocates and may box. Use the for-loop in hot paths.
  • Why doesn't `for (i in 0..Int.MAX_VALUE)` loop forever?
    The progression stores a snapped `last`, and the iterator has an overflow-safe termination check, so stepping past Int.MAX_VALUE ends the loop instead of wrapping.

saying these in an interview costs you the question

  • Claiming every range for-loop allocates an iterator
  • Saying `.forEach` and a `for`-loop compile identically
  • Asserting `0..Int.MAX_VALUE` loops forever due to overflow
  • Believing up-casting to Iterable<Int> has no performance cost
  • Thinking boxing always happens when iterating an IntProgression

context

resolving links…