Why Java Needs a Garbage Collector

Objects outlive the method that made them#

A running Java program keeps its data in two places.

The stack. Every thread has its own, and each method call gets a block on that stack, called a frame, which holds that call's local variables. When the method returns, its frame is thrown away, so cleanup on the stack is automatic: it happens because the method ended.

The heap. This is one large area shared by every thread, and every new creates an object here.

Why not keep objects on the stack too? Because they often have to outlive the method that made them:

List<User> load() {
    List<User> users = new ArrayList<>();  // the list is created on the heap
    return users;                          // the list must survive after load() ends
}

The variable users lives in load()'s frame, but it doesn't hold the list itself. It holds a reference, which is the heap address where the list is stored. When load() returns, its frame is gone and so is the variable, but the list has to stay, because the caller is about to use it.

while load() runs                      after load() returns

STACK            HEAP                  STACK            HEAP
[load()  users ]──► ArrayList @0x1A40  (frame gone)     ArrayList @0x1A40
[main()  list  ]                       [main()  list ]──►      ▲ still needed

So a frame ends at a known moment, when its method returns, but a heap object has no such moment. Nothing about the object itself tells you when it's finished, and that's the whole problem a garbage collector exists to solve.

Freeing by hand breaks in three ways#

The heap has a size limit (it can grow, but only up to a maximum), so if objects are never removed, it fills up and the program fails.

The obvious fix is to let the programmer free each object when they're done with it, which is how C works, with free(). But it goes wrong in three ways:

1. Forget to free. The memory never comes back, and the heap slowly fills. That's a leak.
2. Free too early. Some other code still holds the address. The memory gets reused for a new object, and the old code now reads and writes the new object's data. Often nothing crashes at that moment; the data is just silently wrong.
3. Free twice. The memory manager's own records get corrupted.

1. code A ──► Order #17 ◄── code B
2. code A calls free(order)          code B still holds the address
3. a new object, User bob, is put in the same spot
4. code B reads order.total  ──►  gets bob's bytes. No crash, wrong data.

All three have one cause. In a large program, no single piece of code can know whether some other code still holds a reference to an object.

So Java takes the decision away from you: you never free anything, and the runtime decides instead. The part that decides is the garbage collector, or GC.

Garbage means unreachable#

What should the GC free? The ideal rule is "free what the program will never use again". The trouble is, that would need the GC to predict the future, so it can't be built.

The rule Java uses instead is this: free what the program can no longer reach. If no chain of references leads to an object, no code can ever get its address again. Freeing it is provably safe.

Every chain has to start somewhere. It starts at a GC root: a reference the program can use directly, without first going through another object. The roots are:

• local variables and parameters, in every frame of every thread's stack;
• static fields of loaded classes;
• a few references the JVM itself holds, for example objects held by native code, and objects currently used as locks.

An object is live if you can reach it from a root by following references. Everything else is garbage.

roots:   [local var a]          [static CACHE]
              |                       |
              v                       v
              A ----> B               C ----> D

              E ----> F        (nothing points to E)

Start at the roots and follow the arrows. From a you reach A and then B, and from CACHE you reach C and then D. Nothing leads to E, so E is garbage. And F? E points to F, but E is garbage, so that arrow doesn't count. F is garbage too.

That's the rule again, seen through the example. An object stays alive because something live points to it. What the object itself points to doesn't matter. E has a perfectly good arrow to F, and it saves neither of them.

Java can still leak memory#

The rule is about reach, not use, and that has a consequence people often miss.

static Map<String, Session> sessions = new HashMap<>();

void login(String id) {
    sessions.put(id, new Session(id));   // never removed
}

Every Session is reachable: from the static field sessions (a root), to the map, to the session. The user logged out an hour ago, and no code will ever look at that session again. But none of that matters to the GC. The session is reachable, so the GC is not allowed to free it. Each login adds one more, and the heap fills.

That's a memory leak in Java. The GC can't free memory you still point to. Common sources:

• static collections that only grow;
• caches with no eviction;
• listeners that are registered and never removed;
• ThreadLocal values on threads in a pool, which live as long as the thread does.

The rule again: reachable means alive, even when it's useless. The fix is always to cut the reference: remove the entry, add eviction, unregister the listener.

First try: count the references#

There's a simpler-sounding way to find unreachable objects. Give every object a counter: how many references point to it right now. Each new reference to the object adds 1, and each reference that goes away subtracts 1. When the count reaches 0, nothing points to it, so it can be freed.

A single assignment usually touches two counters, because it replaces a reference that was already there:

x = b;   // before this line, x pointed to a

• b gains a reference, because x now points to it. b's count goes up by 1.
• a loses one, because x doesn't point to it any more. a's count goes down by 1. If that reaches 0, a is freed, and everything a pointed to loses a reference too, which can free those objects in turn.

Two cases touch only one counter. If x was null before, only b changes. When a local variable disappears because its method returned, only the old object's count goes down.

But this idea has two problems: cycles, and cost.

   (no root points here)

   A [count 1]  ──►  B [count 1]
        ▲                 │
        └─────────────────┘

Cycles. A points to B, B points to A, and nothing else points to either. Each count is 1, from the other one, forever. Neither ever reaches 0, so neither is ever freed. Now apply the reachability rule: no root reaches A or B, so under that rule they're garbage, just like E and F. But counting can't see that, because it only looks at one object's number, never at the whole path back to a root. Cycles are everywhere: doubly linked lists, trees where each child points back to its parent, an object registered as its own listener.

What counting costs#

The second problem: even without cycles, counting is slow, because every reference write now does extra work on two counters. With several threads, two threads can change the same counter at the same moment, so every update must be atomic: done in one step another thread can't interrupt. Atomic updates are much slower than plain ones, and they now happen on every x = y in the program.

So Java traces instead#

That's why the standard JVM, HotSpot, doesn't count. It traces: it starts at the roots, follows every reference, and marks everything it reaches. Whatever isn't marked is garbage. A cycle with no path from a root never gets marked, so it's freed like anything else. And an assignment never has to update any counters.

Other languages chose differently, and each paid for it:

Tracing raises the next questions: how it finds everything quickly, how it turns garbage into free space once it knows what's garbage, and what happens to your program while it works. That's Part 2.

If this comes up in an interview#