A lesson from the Computer Memory module of the bootcamp. About a 12 minute read.
When heap memory is no longer needed, something has to give it back. You can do it by hand, the runtime can count references, or a collector can trace what is still reachable. This lesson is those three, why reference counting leaks cycles, and why a program with a garbage collector can still leak memory until it falls over.
An object is GARBAGE when the program can never use it again. That is undecidable in general, so every automatic scheme uses a safe stand-in: an object is LIVE if you can reach it by following references from the ROOTS, the program's global variables and the variables in its stack frames. Anything unreachable is certainly garbage and can be freed. GARBAGE COLLECTION is any mechanism that finds it automatically, and there are two families: count references as they come and go, or periodically trace what is reachable. John McCarthy introduced the tracing idea in 1960 in the paper that defined Lisp, where a reclamation routine followed the reachable list cells and returned every other cell to the free list. Every collector since is a refinement of that one sentence about reachability.
The rest of this lesson continues with 6 further sections. See the full curriculum.
Browse all 546 practice puzzles