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. A root points at A, A at B. C and D point only at each other.
Step 1 of 4A tracing GC starts at the roots and follows every reference: it reaches A and B.
Step 2 of 4C 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 4Reference 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:
- It starts from the roots: the references the program certainly still has, like local variables of running functions and global variables.
- It follows every reference from there, and from those objects onward, marking what it reaches.
- 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
Sources
- Kotlin docs: Kotlin/Native memory management ("Tracing garbage collection is performed periodically to collect objects that are not reachable from the 'roots', like local and global variables")
- The Swift Programming Language: Automatic Reference Counting (ARC tracks "how many properties, constants, and variables are currently referring to each class instance"; a strong reference cycle happens "if two class instances hold a strong reference to each other, such that each instance keeps the other alive")
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.
Answer every question above correctly to unlock the next puzzle.
Something wrong or unclear on this page? Tell me: a puzzle that didn't click is a bug in the puzzle.