Kotlin Multiplatform, from the compiler up · Puzzle 7 · 8 of 16

Counting or tracing

Kotlin on iOS and Swift free unused objects in two completely different ways. Before they meet in your app, here's each one on its own, and the one shape of objects that only one of them can free.

The problem

Objects take memory, and memory is finite. Something must notice when an object isn't needed anymore and free it. On Android you never think about it. Swift, and Kotlin when it runs on iOS, each have their own answer. What are the two answers, and where do they differ?

See it

Objects in the heap with references from a root; a tracing collector follows references from the root and frees the unreachable pair that points at each other; reference counting gives each object a count and frees at zero, but the pair keeps each other at 1 forever rootABCD tracing: follow from the root C and D unreachable: freed count 1count 1counting: never zero, never freed
  1. Objects in the heap. A root points at A, A at B. C and D point only at each other.

    Step 1 of 4
  2. A tracing GC starts at the roots and follows every reference: it reaches A and B.

    Step 2 of 4
  3. C and D, a cycle pointing only at each other, were never reached: both are freed. Predict: what does counting do with C and D?

    Step 3 of 4
  4. Reference counting sees each with one strong reference: count 1, forever. The cycle is never freed.

    Step 4 of 4

The building block

Your objects live in the heap: the memory area where objects are created and kept. Variables hold references to them, arrows pointing at objects.

Tracing (what Android, the JVM and Kotlin/Native do). From time to time a tracing GC, a garbage collector, runs:

  1. It starts from the roots: the references the program certainly still has, like local variables of running functions and global variables.
  2. It follows every reference from there, and from those objects onward, marking what it reaches.
  3. Whatever it didn't reach is unused: freed.

Two objects pointing only at each other, with nothing pointing at them from a root, are unreachable: freed too.

Reference counting (what Swift does, called ARC). Every object keeps a count of its strong references, the references that keep it alive. A new reference: +1. One goes away: −1. At zero, it's freed at once. No passes, no waiting.

But it only ever sees counts. Two objects holding strong references to each other each have a count of 1, forever, even when nothing else uses them. A cycle like that is never freed: a leak. The next puzzle shows how Swift breaks it.

The analogy

Tracing is a park ranger who, every evening, walks every path from the entrance and removes any bench nobody can walk to. Counting is a bench that disappears the moment its last visitor leaves; two benches chained to each other keep each other "visited" forever.

Check yourself

Two objects point only at each other; nothing else points at them. What does a tracing GC do?

Not quite. Neither is reachable, so both are freed.

Not quite. Tracing doesn't count; it frees what it can't reach from the roots.

Right. Unreachable means freed, cycles included.

The same two objects under reference counting. What happens?

Not quite. Counting can't see that; it only sees each count, still 1.

Not quite. Counting has no passes; it frees only at zero, and neither reaches zero.

Right. A cycle never reaches zero.

What's the difference between tracing and reference counting?

Not quite. That's the two swapped. Re-read that part ↑

Right. Reachability vs counts.

Sources

What you now know

A tracing garbage collector starts from the roots, the references a program always has (local and global variables), follows every reference, and frees whatever it couldn't reach, even objects that point at each other. Reference counting keeps a count of strong references on every object and frees it the moment the count hits zero, but two objects holding each other never reach zero: a cycle it can't free.