Who deletes your objects?
Every list, string and object your program creates takes up memory. Programs create them constantly: a web server may make thousands for a single request. If that memory were never given back, the program would grow until the machine ran out.
In languages like C, giving memory back is the programmer's job. Forget, and the program leaks. Do it twice, or too early, and it crashes or becomes a security hole.
Python, Java, JavaScript, Go, C# and many others take the job away from you. A part of the runtime called the garbage collector finds objects that can never be used again and frees them.
How can it possibly know what you will use again?
The trick: can you still reach it?
It cannot read your mind. But it can check something simpler, and safe: is there any way left for the program to get to this object?
A program can only use an object if it has a reference to it. So start from the places the program can touch directly:
- local variables in functions that are currently running,
- global variables.
These are the roots. An object referenced by a root is reachable. So is anything that object refers to, and so on along the chain.
If no chain of references leads from a root to an object, the program has no way of ever touching it again. It is garbage.
Mark, then sweep
The classic algorithm does exactly that, in two passes.
- root (a variable in use)
- marked: reachable
- being freed
Start. The program has created eight objects. Squares are roots: variables it can use right now. An arrow means one thing holds a reference to another.
- Phase
- waiting
- Marked as in use
- 0
- Freed
- 0
Mark
Start at every root. Follow every reference. Put a mark on each object you arrive at. Continue from there, until there is nothing new to follow.
Sweep
Go through all objects. Anything without a mark was never reached. Free it.
Notice how C is reached two ways, through A and through D. It only needs one. And E holds a reference to F, which did not help F at all, because E itself is unreachable.
The pair that point at each other
Look at F and G. Each holds a reference to the other. Neither can be reached from a root.
A simpler scheme than mark-and-sweep is reference counting: keep a count on every object of how many references point at it, and free it when the count reaches zero. It is quick and frees things immediately.
It fails on exactly this case. F is referenced by G, and G by F, so both counts are 1 for ever. They would never be freed.
Mark-and-sweep does not care how many arrows point at an object. It only asks whether a root can reach it, so cycles are collected like anything else.
Making it fast
Scanning every object in a large program takes time, and in the simplest design the program has to stop while it happens. Modern collectors use two observations.
Most objects die young. The temporary string made while formatting a message is garbage a moment later. So memory is split into a small area for new objects, checked often and cheaply, and a larger area for objects that have survived a while, checked rarely. This is generational collection.
Do the work alongside the program. Much of the marking can be done on other threads while the program keeps running, leaving only very short pauses.
You can still leak memory
A garbage collector frees what is unreachable. It cannot free what is reachable but useless. If your program keeps a reference to something it will never use again, the collector must assume you want it.
The usual culprits:
- A cache with no limit. Everything ever stored stays reachable through the cache. See Cache Eviction Policies.
- A list that only grows. Events appended "for later" and never removed.
- Listeners and callbacks never removed. The thing that will call you back holds a reference to you.
- Closures. A small function that holds on to a large variable keeps it alive.
The fix is always the same: drop the reference. Then the collector can do its job.
Good at
- Removes a whole class of bugs: leaks from forgetting, crashes from freeing twice or too early
- Less code to write and review
Where it bites
- Uses processor time, and can cause short pauses
- Memory is given back some time after it stops being needed, not at once
- Does not help when unwanted objects are still referenced
Key takeaways
- A garbage collector frees objects the program can no longer reach.
- Reachable means: connected to a root (a live variable) by a chain of references.
- Mark-and-sweep marks everything reachable from the roots, then frees the rest.
- It handles objects that refer to each other in a cycle, which simple reference counting cannot.
- Memory still leaks if you keep references to things you no longer need.