Wait, What?
A garbage collector does not know which objects you “still care about.” It knows only which objects remain reachable under the runtime’s rules.
Automatic memory management can make memory look effortless. Underneath, a runtime is continually deciding which objects may be reclaimed, how to find them, whether to move survivors, how much application time to interrupt and how to keep pointer relationships correct while the program continues changing the heap.
Garbage collection is therefore a rich algorithmic subject: graph reachability, copying, compaction, generations, concurrent algorithms, barriers, locality and latency all meet inside one runtime service.
Quick Answer
Learn garbage-collection algorithms through the route allocation → heap objects → roots → reachability → reference counting → tracing → mark–sweep → copying → compaction → generations → remembered sets → write barriers → tri-colour marking → incremental/concurrent collection → region-based collectors → latency/throughput trade-offs → diagnostics → professional runtime selection. A beginner should be able to draw an object graph and identify unreachable objects. A professional should be able to explain collector invariants, barriers, pause behaviour, allocation pressure and the workload assumptions behind a runtime’s GC strategy.
1. Memory Allocation Creates a Second Algorithmic Problem: Reclamation
Creating an object consumes memory. If that object becomes useless, the memory eventually needs to be reused. Manual-memory systems make the program explicitly free memory. Garbage-collected systems ask the runtime to determine when memory can be reclaimed automatically.
The convenience does not remove the work. It relocates the work into a collector that must operate correctly alongside the application.
2. Reachability Is the Core Beginner Model
Model heap objects as vertices and references as directed edges. Begin from a root set such as active stack references, globals and runtime handles. Follow references outward. Objects reached by this traversal are live for collection purposes; unreachable objects may be reclaimed.
V8 describes this directly: its collector begins from roots and follows references to mark reachable JavaScript objects. See Trash talk: the Orinoco garbage collector.
3. “Unreachable” Is Not the Same as “Semantically Useless”
An object can remain reachable because a cache, listener, global collection or accidental reference still points to it even though the application no longer needs it. The collector must keep it.
This explains why garbage-collected programs can still have memory leaks. GC removes unreachable memory; it does not read programmer intention.
4. Reference Counting Reclaims Objects When Their Count Reaches Zero
Reference counting stores how many references point to each object. Increment the count when a reference is created; decrement it when a reference disappears. When the count reaches zero, the object can be reclaimed immediately.
The method is intuitive and can provide prompt reclamation, but every pointer update may incur accounting work.
5. Cycles Reveal the Fundamental Limitation of Plain Reference Counting
Two unreachable objects can point to each other. Their reference counts remain nonzero even though no root can reach them. Plain reference counting therefore fails to collect cycles unless supplemented with additional cycle-detection machinery.
This is the perfect first counterexample for learners: local counts do not always reveal global reachability.
6. Tracing Collectors Solve the Global Reachability Problem
Tracing starts from roots and traverses reachable objects. Everything not reached is garbage. The underlying idea is graph search, but real runtimes must integrate it with moving objects, threads, write barriers and memory layout.
The existing How to Learn Graph Algorithms article owns generic traversal. Garbage collection turns reachability into a runtime invariant over a mutating heap.
7. Mark–Sweep Separates Discovery From Reclamation
In the mark phase, reachable objects are marked. In the sweep phase, memory occupied by unmarked objects is returned to free-space structures.
The attraction is simplicity: surviving objects do not necessarily move. The cost is that free memory can become fragmented into gaps of different sizes.
8. Fragmentation Is a Layout Problem, Not a Liveness Problem
A heap may contain plenty of total free memory but still fail a large allocation if the free space is split into small non-contiguous regions. Mark–sweep can therefore reclaim enough bytes while leaving an awkward physical layout.
This is why collectors sometimes compact or copy survivors rather than merely sweeping dead objects.
9. Copying Collection Trades Extra Space for Fast Allocation and Compaction
A copying collector divides memory into regions and copies live objects from one region into another. The copied survivors become densely packed, and allocation can often proceed by simply advancing a pointer.
The cost depends strongly on how much data survives. Copying a small live set is cheap; copying a large live set can be expensive.
10. Mark–Compact Moves Survivors After Marking
Mark–compact identifies live objects and then relocates them to remove holes. References must be updated to the new addresses.
The algorithm improves locality and fragmentation but adds relocation work and complicates interactions with external pointers or runtime handles.
11. Object Movement Requires Pointer Repair
If an object moves, every reference to it must continue to identify the same logical object. Runtimes solve this through handles, forwarding pointers, relocation metadata or carefully coordinated pointer updates.
V8’s embedding documentation notes that when the collector moves objects, handles referring to them are updated: V8 embedding and handles.
12. Generational Collection Exploits a Workload Regularity
Many programs allocate numerous short-lived objects and a smaller set that survives for a long time. Generational collectors exploit this by collecting young objects frequently and older objects less often.
Microsoft’s current .NET documentation explains generations 0, 1 and 2, promotion of survivors and the focus on reclaiming short-lived objects efficiently: Fundamentals of garbage collection.
13. Promotion Is an Inference About Likely Lifetime, Not a Proof
An object that survives several young collections is treated as more likely to live longer and may be promoted. Some promoted objects still die soon; some young objects live for the whole program.
Generational collection is effective because the statistical pattern is useful often enough—not because age perfectly predicts lifetime.
14. Old-to-Young References Break the Naïve Generational Shortcut
If a young collection traced only young roots, it could miss a young object referenced from an old object. The runtime therefore needs a record of cross-generation references.
This motivates remembered sets, card tables and write barriers.
15. Write Barriers Turn Pointer Updates Into Collector Information
A write barrier is a small piece of runtime logic triggered when the application writes certain references. It records information the collector will need later—for example, that an old region may now point into a young region.
Oracle’s G1 documentation explains that remembered sets track references into regions and that post-write barriers help maintain them: Garbage First Garbage Collector Tuning.
16. Barriers Move Work From Collection Time Into Application Time
A barrier makes ordinary pointer updates slightly more expensive so later GC phases can avoid scanning the entire heap. This is a classic algorithmic trade: spend small incremental cost to reduce a large future search.
Professional GC design therefore considers mutator overhead as well as collector overhead. The “mutator” is the application thread that keeps changing the heap while the collector tries to reason about it.
17. Tri-Colour Marking Gives a Useful Concurrent Invariant
In a common conceptual model, white objects have not yet been proven reachable, grey objects are known reachable but not fully scanned, and black objects are reachable and fully scanned.
The collector advances by turning grey objects black and discovering new grey objects. Concurrent mutation is dangerous because an application write can create a reference that invalidates the marking invariant unless a barrier records it.
18. Stop-the-World Collection Makes Correctness Easier and Latency Worse
If application threads are paused, the heap stops changing and tracing is easier to reason about. But the pause directly affects response latency.
Small applications may tolerate pauses that are unacceptable in interactive, trading, game, service or large-memory workloads. Collector design is therefore partly about moving work away from long global pauses.
19. Incremental Collection Breaks Long Work Into Smaller Slices
An incremental collector alternates between application work and small pieces of GC work. This can reduce individual pause length while increasing coordination overhead.
The algorithm must preserve its marking or relocation invariants across interruptions while the heap changes between slices.
20. Concurrent Collection Lets the Collector Work While the Application Runs
Concurrent marking and sweeping move substantial work onto threads that run alongside the application. That reduces pause time but introduces races between heap mutation and collector observation.
V8’s Orinoco project transformed a sequential stop-the-world collector into one using parallel, concurrent and incremental techniques. The article is a useful professional bridge from textbook phases to production runtime engineering: Orinoco garbage collector.
21. Parallel and Concurrent Are Not the Same Thing
Parallel GC uses multiple collector threads at the same time, often while the application is paused. Concurrent GC performs collector work while application threads are also running.
A collector can be both. Learners should keep these axes separate: “How many collector workers?” and “Does the application keep running?” are different questions.
22. Region-Based Collectors Avoid Treating the Heap as One Monolithic Space
G1 divides the heap into regions and chooses collections with attention to reclaimable space and pause-time goals. Its remembered sets track references into regions so a region can be processed without scanning the whole heap.
Oracle describes G1 as generational, incremental, parallel, mostly concurrent and evacuating, designed to balance latency and throughput: Garbage-First Garbage Collector.
23. Low-Latency Collectors Push More Work Into Concurrent Phases
Modern collectors such as ZGC aim to keep pauses small even on large heaps by using load barriers, coloured pointers or other runtime techniques that permit relocation and marking to occur with substantial concurrency.
Current OpenJDK work also treats ZGC as generational and explores automatic heap sizing based on GC intensity: OpenJDK draft JEP: Automatic Heap Sizing for ZGC. The professional point is not one specific collector flag; it is that production GC is an adaptive control problem as well as a reachability algorithm.
24. Throughput, Latency and Footprint Pull in Different Directions
A collector can maximise application throughput by doing large efficient collections but produce longer pauses. A low-latency collector may spend more CPU concurrently. A larger heap may reduce collection frequency while increasing memory footprint and possibly full-heap work.
Oracle’s G1 guidance explicitly discusses latency versus throughput. Professionals choose a collector against workload objectives, not against a generic ranking.
25. Allocation Rate Can Matter as Much as Live-Heap Size
Two applications with the same 2 GB of live data can behave differently if one allocates 50 MB per second and the other allocates 5 GB per second. High allocation rates force young collections and copying work more frequently.
A professional GC investigation therefore measures allocation rate, survival rate and promotion—not just total heap size.
26. Weak References Deliberately Weaken the Reachability Rule
A weak reference can refer to an object without necessarily keeping it alive. This is useful for caches and metadata but makes program behaviour more dependent on GC timing.
V8’s documentation warns that weak references and finalizers depend on nondeterministic garbage-collection behaviour: Weak references and finalizers.
27. Finalization Is Not a Reliable Substitute for Explicit Resource Management
Memory reclamation timing is generally nondeterministic. External resources such as files, sockets and database transactions often require deterministic release semantics.
A professional distinguishes memory lifetime from resource lifetime and uses language-specific structured cleanup where appropriate.
28. GC and Manual Memory Reclamation Have Different Failure Modes
Manual reclamation risks use-after-free, double-free and dangling pointers. Tracing GC reduces those classes of errors but can introduce pauses, retention leaks and larger runtime overhead. Reference counting can be prompt but struggles with cycles.
The question is not which approach is morally superior. It is which ownership, latency and safety model fits the system.
29. Concurrent Data-Structure Reclamation Is a Neighbouring but Different Job
Lock-free algorithms in manually managed environments may use hazard pointers, epochs or read-copy-update style techniques so memory is not freed while another thread may still access it.
The existing How to Learn Concurrent Algorithms article owns those concurrency-specific reclamation concerns. This article owns automatic heap garbage collection.
30. Cache Locality Can Change the Real Cost of a Collector
Copying and compaction can improve locality by packing surviving objects. Tracing a pointer-rich heap can also cause irregular memory access. Card tables and remembered sets add metadata with their own cache behaviour.
The existing How to Learn Cache-Efficient Algorithms article owns the general memory-hierarchy job; GC is one production system where those costs become visible.
31. Common Learning Failure States
- Thinking GC collects objects the programmer no longer wants rather than objects the runtime can no longer reach.
- Assuming garbage-collected programs cannot leak memory.
- Using reference counting without testing a cycle.
- Confusing mark–sweep with mark–compact.
- Confusing parallel GC with concurrent GC.
- Ignoring write-barrier overhead when praising short pauses.
- Assuming generational collection means all young objects die young.
- Optimising heap size without measuring allocation and survival rates.
- Using finalizers as deterministic resource cleanup.
- Comparing collectors with only average throughput and no tail-latency or footprint data.
32. A Beginner-to-Professional Learning Ladder
- Level 1: draw roots and heap objects and mark what is reachable.
- Level 2: simulate reference counting and construct a cycle it cannot reclaim.
- Level 3: trace mark–sweep on a small object graph.
- Level 4: simulate copying collection and update moved references.
- Level 5: explain fragmentation and compare sweep with compaction.
- Level 6: model a young and old generation and identify cross-generation references.
- Level 7: explain why a write barrier or remembered set is necessary.
- Level 8: trace a tri-colour concurrent-marking race and the barrier that repairs it.
- Level 9: compare G1-style regional collection with a low-latency concurrent collector using workload metrics.
- Level 10: diagnose a production memory problem using allocation rate, live set, promotion, pause distribution, CPU overhead and retention evidence.
33. Teach Reachability Before Collector Names
Give learners a paper heap graph. Ask them to predict which objects survive after one root disappears. Then run mark–sweep, copying and reference-counting procedures on the same graph. The contrast makes each algorithm’s invariant visible.
This prediction-first approach fits PRIMM’s Predict–Run–Investigate–Modify–Make sequence: Using PRIMM to teach programming.
34. Use Worked Heap Traces, Then Fade Them
At first, label roots, colours, generations, cards and copied addresses explicitly. Later remove the labels and ask the learner to reconstruct them. Finally provide a new heap shape with a different allocation pattern.
Research on worked examples and metacognitive scaffolding in programming found benefits from faded worked examples combined with metacognitive support: Shin et al. (2023). Adaptive Parsons problems can similarly scaffold implementation of a toy tracer without making syntax the main barrier: Hou, Ericson and Wang, ICER 2022.
35. Immediate, Delayed and Transfer Checks
- Immediate: identify live and dead objects from a root set.
- Counterexample: construct a reference-counting cycle.
- Trace: perform one mark, sweep or copy phase by hand.
- Delayed: reconstruct why remembered sets and write barriers are needed.
- Transfer: choose different collector priorities for a command-line tool, interactive UI and latency-sensitive server.
- Professional: explain pause distribution, throughput, footprint, allocation rate, promotion and live-heap evidence together.
Use spaced and interleaved retrieval so learners repeatedly distinguish collector families instead of recognising one diagram in isolation. See A Spaced, Interleaved Retrieval Practice Tool.
36. AI Assistance Boundary
AI can generate object graphs, explain GC logs, compare collector concepts and suggest experiments. The learner should still be able to determine reachability, state the collector invariant, identify the purpose of a barrier, distinguish latency from throughput and independently verify whether a claimed memory leak is unreachable garbage or reachable retention.
Professional Direction
Advanced study includes concurrent and incremental tracing, SATB and incremental-update barriers, generational and regional collectors, evacuation failure, compaction algorithms, concurrent relocation, weak/soft/phantom references, object pinning, large-object spaces, NUMA-aware GC, real-time collectors, GC ergonomics, heap sizing, language interoperability and collector-aware application design. Production collectors such as G1, ZGC and V8 Orinoco show how foundational graph-reachability ideas evolve into highly concurrent runtime systems.
Algorithm-learning rule: when memory seems automatic, ask what counts as a root, how reachability is discovered, what work happens on each pointer update, when application threads must pause, and which performance goal the collector is actually optimising.
eduKate Sengkang 