Mark & Sweep — The classic GC algorithm. Phase 1: Mark — start from roots, traverse all reachable objects recursively, mark them alive.
Phase 2: Sweep — scan the entire heap, free any unmarked (unreachable) objects. Simple but causes fragmentation.
Reference Counting — Each object tracks how many references point to it. When the count drops to zero, the object is immediately freed.
Fatal flaw: circular references — objects referencing each other keep counts > 0 even when unreachable from roots. Demonstrated here.
Mark-Compact — Like mark-and-sweep, but after marking, compacts live objects to one end of the heap, eliminating fragmentation.
Three phases: Mark (find reachable), Compute forwarding (new addresses), Compact (move objects & update references).
Copying GC (Cheney's Algorithm) — Heap is split into from-space and to-space. During GC, live objects are copied from from-space to to-space.
After copying, spaces swap roles. No fragmentation, but uses only half the heap. O(live objects) — ignores garbage entirely.
Generational GC — Based on the generational hypothesis: most objects die young. Heap divided into Young Gen (nursery) and Old Gen (tenured).
New objects go to young gen. Surviving young objects get promoted. Minor GC (young only) is frequent and fast. Major GC (full) is rare but expensive.