The idea: two ways to find garbage
An object is garbage when the program can no longer reach it: no chain of pointers leads to it from a root (a local variable, a register, a global). A memory manager must find garbage and give its memory back. Reference counting asks "does anything still point to this object?" and answers it all the time, one pointer change at a time. A tracing collector asks "can a root reach this object?" and answers it now and then, for the whole heap at once. This page runs one program on two copies of the same heap: roots a, b, c and objects A to H, with a cycle between B and C.
One Step moves both lanes by one unit of work. The scoreboard counts collector work (count updates, or objects marked and swept), objects freed, garbage held (unreachable objects still using memory, grey on the canvas) and the longest pause: the most collector work done inside one program step while the program waits. The red cells under each lane show the pause of the latest step.
Reference counting: free at the last pointer
Every object carries a count of the strong pointers to it. Storing a pointer adds 1 to the new target; overwriting or clearing one takes 1 from the old target. When a count reaches 0, the object is freed right there, and freeing it clears its own pointers, so the counts of the objects it points to go down too. (Demo: drop b, refcount frees at once.) Setting b = null takes D from 1 to 0; D is freed and drops E, which drops F: three objects freed in three units, and no garbage left. The tracing lane does nothing: D, E and F stay in its heap, grey, until the next GC.
CPython, Swift and Objective-C (ARC), Rust's Rc/Arc, C++ std::shared_ptr and COM all count references. Memory comes back at a predictable point, which also makes it the natural place to close files and sockets (destructors).
Mark-sweep: keep what the roots reach
A pointer store costs a tracing collector nothing. When the heap fills up (here: when you press Run GC), it stops the world, then works in two phases. Mark: start from every root, follow every strong pointer, and set the mark bit of each object reached. Sweep: walk every allocated object; a marked one survives and has its bit cleared for next time, an unmarked one is freed. Mark work grows with the live objects, sweep work with the whole heap. The JVM, Go, .NET and JavaScript engines trace; see Java garbage collectors for generations and concurrent marking, and Stack vs heap in Java for what the roots are.
Cycles: where reference counting leaks
(Demo: a cycle leaks under refcount.) A points to B, and B and C point to each other. Drop A → B: B's count goes from 2 to 1, because C still points to it, and C's count stays 1, because B points to it. Neither count can ever reach 0, yet the program can never reach B or C again. They leak. Run GC: the tracing lane marks A, H, D, E, F and G from the roots, never reaches B or C, and the sweep frees them.
This is why CPython adds a separate cycle collector (the gc module) on top of its counts, and why Swift and Rust programmers mark back pointers as weak.
Pauses and the cost of every pointer write
(Demo: one long GC pause vs short refcount pauses.) Drop b, drop c, then run GC. Refcount works during the drops: 3 units, then 2, so its longest pause is 3. The tracing collector waits, then stops the program for 4 marks and 8 sweeps: a 12-unit pause. On a real heap of millions of objects, that one pause is what concurrent and incremental collectors (G1, ZGC, Go) fight to shrink. Refcount is not pause-free either: dropping the last pointer to a big tree frees the whole tree in one go.
(Demo: busy pointer writes, refcount pays each time.) Moving A's pointer from H to G and back four times creates no garbage at all, but refcount still does 8 count updates: 1 up for the new target, 1 down for the old one, on every store. With threads those updates must be atomic, which is slower still. The plain mark-sweep collector does 0 work here. This per-write cost is the throughput price of reference counting.
Weak references
A weak pointer lets the program find an object without keeping it alive: refcount does not count it, and tracing does not follow it when marking. When its target is freed, it reads as null. (Demo: a weak pointer breaks the cycle.) Make C → B weak first: B's count drops to 1. Now dropping A → B takes B to 0, B is freed and drops C, and both lanes end with no garbage. Weak pointers are how parent links, caches and observer lists avoid cycles: Swift weak, Rust Weak, C++ std::weak_ptr, Python weakref, Java WeakReference.
When to pick which
| Question | Reference counting | Tracing (mark-sweep) |
|---|---|---|
| When is garbage freed? | at once, when the last pointer goes | at the next GC |
| Unreachable cycles | leak, unless weak pointers or a cycle collector | freed |
| Cost per pointer write | 1 inc + 1 dec (atomic with threads) | none (a write barrier in generational or concurrent GCs) |
| Pauses | short, spread out; a large cascade is one long pause | stop the world for mark + sweep, unless incremental or concurrent |
| Extra memory | a count in every object | a mark bit, plus headroom so the heap does not fill up between GCs |
| Destructors, closing files | run at a known point | finalizers run late, or never |
| Used by | CPython, Swift, Objective-C, Rust Rc/Arc, C++ shared_ptr | JVM, Go, .NET, JavaScript, Ruby |
For mark-sweep made concurrent with tri-colour marking and a write barrier, see Go's garbage collector.
See Python garbage collection for how that collector finds cycles by subtracting internal references (gc_refs).
What the page leaves out
The heap is fixed: no allocation, so no GC triggered by a full heap, and the GC only runs when you press Run GC. Units are a model: a count update and a mark are not the same cost on real hardware. Not shown: copying and compacting collectors (no sweep, no fragmentation), generations and write barriers, incremental and concurrent marking (tri-colour marking), CPython's cycle detector, deferred and coalesced reference counting, atomic counts across threads, finalizers and resurrection, and soft and phantom references.