In a tracing garbage collector, what is a root, and why must a collection start from the root set?
answer
- where a trace has to begin
- found without following another reference
- stacks, registers, globals, registered handles
- mark the closure, reclaim the rest
- unmarked means reachable from no root
basics
~20 sA root is a reference the collector can find without tracing anything first — a running thread's stack slot or register, a global table entry, a handle registered by code outside the collected heap. Everything the program can still touch starts at one of them.
solid answer
~40 sCollection starts from the root set because those are the only references the collector can locate without following another reference first. Roots come from the program's directly addressable state: each paused thread's stack slots and registers, global and process-wide tables, and handles that code outside the collected heap has registered with the runtime. The collector marks every object a root names, then walks outgoing references transitively; whatever is never marked is reachable from no root, so no future instruction can name it, and reclaiming it cannot be observed. Starting anywhere else would be unsound — scanning the heap for objects that nothing points at, for instance, would keep a cycle of dead objects alive forever, because every member of the cycle still has an incoming reference from another member.
go deeper
Be able to define a root in one sentence and name two kinds: a local slot in a paused thread's frame and a global table entry. Then say that whatever those reach, directly or indirectly, is kept.
Explain the walk itself — seed the mark set from roots, follow outgoing references until nothing new is marked, reclaim the unmarked — and use it to explain why a group of objects that only reference each other is correctly reclaimed.
Show that you know which parts of a real process supply roots: every thread's stack and registers rather than one thread's, plus handles registered by code outside the collected heap, which no view of the program's own data structures will explain.
The trade worth raising is what the root set costs. Precise enumeration needs compiler-emitted metadata and a point where threads can be stopped safely, and every extra root category is somewhere a subsystem can pin memory indefinitely.
## The only question a collector can answer A collector is asked for memory the program no longer **needs**. Need is a property of the future, and nothing in memory records the future. So a tracing collector substitutes a question it *can* answer from the current state of the process: **which objects can the program still get to?** An object it can get to is one it might read. An object it cannot get to can never be named by any instruction the program will execute, so reclaiming it is unobservable. That substitution is the whole design, and it is usually written as one equation: **liveness = reachability**. Reachability is only defined relative to a starting set. That starting set is the roots. ## What makes a reference a root A **root** is a reference the collector can enumerate *without following another reference first* — that is the whole definition, and it is why the trace can begin there. In a running process, roots come from: - **Thread stacks and registers.** Every thread that exists at the moment of collection, not only the one that triggered it: each frame's local slots, plus the machine registers holding values the compiler never spilled to memory. - **Global and process-wide storage.** Module-level variables, process singletons, and the tables a runtime keeps for loaded code and its constant values. - **Handles registered by code outside the collected heap.** The collector cannot interpret foreign frames, so such code registers what it holds and the registry is scanned as roots. - **Runtime-internal structures.** Objects the runtime itself holds on the program's behalf while an operation is in flight. The second property that makes a root a root is that the program can name it directly on its very next instruction. Nothing else in the heap has that property; every other reference has to be found by starting at a root and walking. ## The walk 1. **Seed.** Mark every object named by a root and put it on a worklist. 2. **Drain.** Pop an object, look at its outgoing references, mark each target that is not already marked, and push the newly marked ones. 3. **Finish.** When the worklist empties, the marked set is exactly the set of objects reachable from at least one root. Everything unmarked is reachable from none. The walk terminates because the heap is finite and each object is marked at most once. Its cost is proportional to the **live set**, not to the size of the heap — a large heap that is mostly garbage costs the same to mark as a small one holding the same live objects. ## Why not "find the objects nobody points at"? This is the intuitive alternative, and it is wrong in a way worth being able to state: | Criterion | A cycle of dead objects | What it must examine | Needs a starting set? | |---|---|---|---| | Reachable from a root | Reclaimed — no root reaches any member | Live objects only | Yes: the root set | | Has no incoming reference | Retained forever — each member points at the next | Every object's inbound edges | No | A mutually-referencing group that the program has dropped entirely still has one incoming reference per member. Only a root-based criterion sees that the whole group has become unreachable. ## What this buys you in practice - **A single root can retain an arbitrarily large graph.** The unit of retention is the closure behind the reference, not the object. - **Reachable but never used again still survives.** That gap between reachability and usefulness is where memory that "should" be free lives. - **When memory will not go away, the question is which root still reaches it** — including roots the program's own data structures do not explain, such as a registered handle held by code outside the collected heap. - **Root enumeration is not free.** Identifying which stack words hold references needs either compiler-emitted metadata or a guess, and threads must be stopped at a point where that information is valid.
- Does every thread contribute roots, or only the one that triggered the collection?Every thread. A reference held in any paused thread's frame or registers can be used the moment that thread resumes, so all of them must be scanned. Missing one would let the collector free an object another thread is about to dereference, which is a correctness failure, not a performance one.
- Is the cost of marking driven by the size of the heap or by something else?By the live set. Marking visits each reachable object once and never touches unreachable ones, so a mostly-empty large heap marks as fast as a small heap with the same live objects. Reclaiming the unmarked space is the phase whose cost tracks heap size instead.
- What does it mean that reclaiming an unreachable object is "unobservable"?No sequence of instructions the program can still execute produces that object's address, because every path to it would have to start at a root and none does. The program therefore cannot read, compare or free it, so its memory can be reused without any behaviour changing.
saying these in an interview costs you the question
- Thinks an object dies the moment the program stops using it
- Calls any object with no incoming references a root
- Says the collector scans the heap for objects nobody points at
- Believes only the thread that triggered collection contributes roots
- Assumes a cycle of mutually referencing objects can never be reclaimed