Back to series
· 11 min read

Garbage Collection (GC)


I. What Is Garbage Collection?

Garbage Collection (GC) is a mechanism by which a runtime system automatically manages memory.

While a program runs, it continuously creates objects, allocates memory, and changes the reference relationships between objects. When some objects are no longer used by the program, the memory they occupy may be reclaimed and reused.

In the manual memory management model, developers usually need to explicitly request and release memory, for example malloc() and free() in the C language.

In languages or runtimes that use automatic garbage collection, GC is responsible for identifying objects that are no longer needed and reclaiming their memory at the appropriate time.

For example:

public class Main {
    public static void main(String[] args) {
        Object obj = new Object();

        obj = null;
    }
}

After obj = null is executed, the object originally created is no longer referenced by the local variable obj.

If no other valid references exist, that object may become a candidate for garbage collection.

Note:

  • An object no longer being referenced does not mean its memory is released immediately.
  • An object meeting the conditions for reclamation does not mean GC will execute immediately.
  • When GC runs is usually decided by the runtime system.
  • GC mainly manages memory under its jurisdiction; it does not mean that all resources in a program will be released automatically.

II. Why Is Garbage Collection Needed?

Memory management is an important responsibility during program runtime.

Improper memory management can lead to problems such as memory leaks, dangling pointers, and double frees.

1. The Complexity of Manual Memory Management

Take the C language as an example:

#include <stdlib.h>

int main() {
    int *ptr = malloc(sizeof(int));

    if (ptr == NULL) {
        return 1;
    }

    *ptr = 100;

    free(ptr);

    return 0;
}

Developers need to ensure that:

  • Memory is used correctly after successful allocation.
  • It is released promptly when no longer in use.
  • The same block of memory is not released twice.
  • It is not accessed after being released.
  • All possible execution paths handle resources correctly.

If a release operation is missed, a memory leak may occur.

If memory is accessed after being released, a Use-After-Free may occur.

If the same block of memory is released twice, a Double Free may occur.

2. The Problems GC Solves

GC reduces the complexity of memory management by automatically identifying unreachable objects.

Problem Manual Memory Management Automatic Garbage Collection
Memory allocation Developer or runtime Usually allocated by the runtime
Memory release Developer's responsibility GC automatically reclaims managed objects
Memory leaks Easily caused by missed releases Can still occur if objects remain reachable
Dangling references Developer must guard against them GC usually guarantees reference safety for managed objects
Double free Developer must guard against it Managed objects usually do not need explicit release
Memory management cost Developer bears more responsibility Runtime bears the reclamation cost

GC does not completely eliminate memory problems; rather, it shifts part of the memory management responsibility to the runtime.

For example, even with GC, if a program continuously keeps data that is no longer needed in a global collection, those objects may remain reachable and eventually form a logical memory leak.

III. The Core Principle of GC: Object Reachability

The most central question for GC is not whether an object is currently executing, but whether the object can still be accessed from the starting points defined by the program.

This set of starting points is usually called GC Roots.

1. What Are GC Roots?

GC Roots are a set of root references used by the garbage collector to determine whether an object is alive.

Common roots include:

  • Local variable references in the stack frames of current threads.
  • References from active threads.
  • Static variable references.
  • References held by native interfaces such as JNI.
  • Special references inside the virtual machine.
  • Other root objects explicitly registered by the runtime.

The specific root set depends on the language runtime and the GC implementation.

For example, in the Java Virtual Machine, GC Roots are an important starting point for reachability analysis.

2. What Is Object Reachability?

Suppose the following object reference relationships exist in a program:

GC Root
   |
   v
Object A
   |
   v
Object B
   |
   v
Object C

Starting from the GC Root, A, B, and C can be accessed through references, so these objects are all reachable objects.

If object D has no reference path starting from the GC Root, then D is an unreachable object.

3. The Reachability Analysis Process

flowchart TB
    A["Identify GC Roots"] --> B["Traverse references starting from root objects"]
    B --> C["Mark reachable objects"]
    C --> D["Check other objects in the heap"]
    D --> E{"Is the object marked?"}
    E -->|"Yes"| F["Keep the object"]
    E -->|"No"| G["Determine it as an unreachable candidate"]
    G --> H["Proceed to subsequent reclamation processing"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style G fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style H fill:#E8EDF2,stroke:#B8C3CE,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

There is an important concept here:

Unreachable does not mean the object is not referenced by any variable; it means there is no valid reference path starting from GC Roots.

An object may still be referenced by other objects, but if the entire reference chain cannot be reached from GC Roots, those objects may still be reclaimed as a whole.

4. Why can circular references be reclaimed by GC?

This is an important distinction between understanding GC and reference counting.

For example:

class Node {
    Node next;
}

public class Main {
    public static void main(String[] args) {
        Node a = new Node();
        Node b = new Node();

        a.next = b;
        b.next = a;

        a = null;
        b = null;
    }
}

Object A references object B, and object B references object A, forming a circular reference.

Although references still exist between the two objects, there is no longer a path from GC Roots to reach them.

Therefore, GC based on reachability analysis can identify that both objects are unreachable and treat them as reclamation candidates.

This is also an important reason why tracing GC can handle circular references.

IV. Main Garbage Collection Algorithms

GC has a variety of implementation algorithms, and different algorithms make different trade-offs in terms of memory utilization, collection efficiency, pause time, and space overhead.

The most fundamental algorithms include:

  1. Mark-Sweep.
  2. Mark-Compact.
  3. Copying.
  4. Reference Counting.

1. Mark-Sweep Algorithm

Mark-Sweep is a classic tracing garbage collection algorithm.

It is divided into two main phases:

Mark phase

Traverse object references starting from GC Roots and mark all reachable objects as alive.

Sweep phase

Scan the memory region and reclaim the space occupied by unmarked objects.

flowchart TB
    A["Start garbage collection"] --> B["Mark phase"]
    B --> C["Traverse from GC Roots"]
    C --> D["Mark all reachable objects"]
    D --> E["Sweep phase"]
    E --> F["Scan the heap memory"]
    F --> G["Reclaim unmarked objects"]
    G --> H["Reclamation complete"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style G fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

Advantages:

  • The algorithm is simple in principle.
  • Surviving objects do not need to be moved.
  • Circular references can be handled.

Disadvantages:

  • Memory fragmentation is easily produced after reclamation.
  • Objects and memory regions need to be scanned.
  • The marking and sweeping processes may introduce noticeable execution overhead.

The memory fragmentation problem

Suppose there are multiple objects in the heap memory:

Before collection: ```text ┌──────┬──────┬──────┬──────┬──────┐ │ A │ B │ C │ D │ E │ └──────┴──────┴──────┴──────┴──────┘ ``` After collecting B and D: ```text ┌──────┬──────┬──────┬──────┬──────┐ │ A │ Free │ C │ Free │ E │ └──────┴──────┴──────┴──────┴──────┘ ```

Although free memory exists, it may be scattered across different locations.

When a program needs to allocate a larger contiguous block of memory, even if the total amount of free space is sufficient, the allocation request may not be satisfiable directly.

2. Mark-Compact Algorithm

The mark-compact algorithm marks live objects and then moves them into a contiguous memory region.

The original fragmented space is consolidated into contiguous free space.

flowchart TB
    A["Start collection"] --> B["Mark live objects"]
    B --> C["Determine new object locations"]
    C --> D["Move live objects"]
    D --> E["Update object references"]
    E --> F["Consolidate free memory"]
    F --> G["Finish collection"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style E fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style G fill:#E8EDF2,stroke:#B8C3CE,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

Advantages:

  • It can eliminate external memory fragmentation.
  • Free memory becomes more contiguous.
  • It facilitates subsequent memory allocation.

Disadvantages:

  • Moving objects incurs additional overhead.
  • References need to be updated after objects are moved.
  • Object reference relationships must remain correct during the move.

Note that moving an object does not mean every program must update ordinary pointers. A specific implementation may use object reference updates, handles, indirection, or other mechanisms to keep references valid.

3. Copying Algorithm

The copying algorithm divides heap memory into two regions:

  • From Space: the currently used region.
  • To Space: the target region.

During collection, live objects in From Space are copied to To Space, and then the roles of the two regions are swapped.

flowchart TB
    A["Current From Space"] --> B["Identify live objects"]
    B --> C["Copy live objects to To Space"]
    C --> D["Update object references"]
    D --> E["Swap From and To"]
    E --> F["The entire original From Space becomes free space"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style D fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style E fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

Advantages:

  • It does not produce external memory fragmentation in the traditional sense.
  • Live objects are concentrated together.
  • Allocating space is simple and can usually be done by moving an allocation pointer.

Disadvantages:

  • It requires additional target space.
  • Live objects must be copied.
  • When there are many live objects, the copying cost is high.

The copying algorithm is especially suitable for memory regions with a low proportion of live objects.

4. Reference Counting Algorithm

Reference counting determines whether an object can be reclaimed by recording the number of references to it.

When an object is created, its reference count is usually initialized to a certain value.

Each time a valid reference is added, the count increases; each time a reference becomes invalid, the count decreases.

When the reference count drops to zero, the object can be released.

For example:

a = []
b = a
c = a

del b
del c

Under the reference counting model, after the references corresponding to variables b and c are removed, the reference counts change.

Note, however, that the actual object lifetime in Python is also affected by implementation details, temporary references, and runtime mechanisms. The above code is only intended to illustrate the basic idea of reference counting.

Advantages:

  • Memory can be released quickly when an object's reference count reaches zero.
  • It does not necessarily require periodically scanning the entire object graph.
  • It can be relatively easily combined with some manual resource management mechanisms.

Disadvantages:

  • Every reference change may incur counting update overhead.
  • Additional space is required to store reference counts.
  • Circular references cannot be resolved by normal reference counting alone.

Circular Reference Problem

flowchart TB
    A["Object A<br/>reference count is 1"] --> B["Object B<br/>reference count is 1"]
    B --> A
    C["External reference becomes invalid"] --> D["A and B still reference each other"]
    D --> E["Reference count cannot drop to zero"]
    E --> F["An additional cycle detection mechanism is required"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style C fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style D fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style E fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style F fill:#E8EDF2,stroke:#B8C3CE,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

The case where the reference count is 1 is only illustrative; the actual count depends on how many references the object holds.

5. Comparison of Four Algorithms

Algorithm Core Mechanism Memory Fragmentation Object Movement Main Issue
Mark-Sweep Mark live objects and clear unreachable objects May occur Not required Memory fragmentation
Mark-Compact Mark and then move live objects Can eliminate external fragmentation Required Cost of moving and updating references
Copying Algorithm Copy live objects to another space Usually does not produce external fragmentation Required Requires additional space
Reference Counting Count the number of references to an object Depends on the allocator Not required Circular references

Practical GC usually does not simply use a single algorithm; instead, it combines multiple techniques based on object lifetime, heap memory regions, and pause goals.

V. Generational Garbage Collection (Generational GC)

Generational garbage collection is an optimization strategy widely used by modern garbage collectors.

It is based on an empirical observation:

Most objects have short lifetimes, and only a few objects survive for a long time.

This is known as the Weak Generational Hypothesis.

For example:

  • Temporary objects created during function execution usually lose their references quickly.
  • Intermediate data created while processing a request may no longer be used after the request ends.
  • Objects such as global caches and the state of long-running services may remain alive for a long time.

If every GC scans the entire heap, it may waste a lot of time checking long-lived objects.

Generational GC divides objects into different regions based on their lifetime and prioritizes collecting young objects.

1. Young Generation and Old Generation

In the classic generational GC model, the heap is usually divided into:

  • Young Generation: stores newly created objects.
  • Old Generation: stores objects that remain alive after multiple collections.

The young generation may further be divided into:

  • Eden space: mainly used for allocating new objects.
  • Survivor From: used to hold objects that survived the previous collection.
  • Survivor To: used to receive objects that survive the current collection.

2. Object Promotion Process

Objects usually enter the young generation first.

If they remain alive after multiple young-generation GCs, they may be promoted to the old generation.

flowchart TB
    A["Create new object"] --> B["Enter Eden space"]
    B --> C["Minor GC occurs"]
    C --> D{"Is the object alive?"}
    D -->|"No"| E["Reclaim object"]
    D -->|"Yes"| F["Copy to Survivor space"]
    F --> G["Continue through young-generation GC"]
    G --> H{"Has it met the promotion condition?"}
    H -->|"No"| F
    H -->|"Yes"| I["Promote to old generation"]
    I --> J["Participate in old-generation collection"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style C fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#E8EDF2,stroke:#B8C3CE,color:#334155
    style F fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style G fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style H fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style I fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style J fill:#E8EDF2,stroke:#B8C3CE,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

The promotion conditions here may include:

  • The object's age reaches the threshold.
  • Survivor space is insufficient.
  • The object's size exceeds a specific threshold.
  • Other adaptive strategies used by the GC implementation.

Not all GCs strictly use the young generation, old generation, and Survivor space structure described above.

3. Why is generational GC efficient?

Suppose there are 1 million objects in the heap, of which 900,000 are short-lived objects.

If every collection scanned all objects, a large number of long-lived objects would need to be processed frequently.

Generational GC can scan the young generation first, concentrating collection work on the region where the object mortality rate is higher.

Its core idea is:

  • Frequently collect young objects.
  • Reduce repeated processing of long-lived objects.
  • Perform larger-scale collections when necessary.

4. Cross-generational reference problem

Generational GC has an important challenge: old-generation objects may reference young-generation objects.

For example:

Old-generation object A
     |
     v
Young-generation object B

If GC only scans root references in the young generation but ignores references from the old generation to the young generation, it may incorrectly reclaim B.

Therefore, GC needs to record or track cross-generational references.

Common techniques include:

  • Card Table.
  • Write Barrier.
  • Remembered Set.

These mechanisms help young-generation GC quickly identify references from the old generation without having to scan the entire old generation every time.

VI. Stop-the-World (STW) and Safepoints

Garbage collection involves not only object identification but also the consistency of memory state during program execution.

When GC needs to traverse object references, move objects, or update references, it must ensure that errors are not caused by application threads concurrently modifying object relationships.

A common approach is to pause application threads.

This pause is called Stop-the-World, or STW for short.

1. What is STW?

STW means that the garbage collector pauses application threads at certain stages so that GC can complete necessary operations in a relatively stable state.

For example:

flowchart TB
    A["Application running normally"] --> B["GC requests thread pause"]
    B --> C["Threads reach a safepoint"]
    C --> D["Pause application threads"]
    D --> E["Execute GC phase"]
    E --> F["Complete necessary object processing"]
    F --> G["Resume application threads"]
    G --> H["Application continues running"]

    style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style B fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style C fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style D fill:#F3EDFC,stroke:#C4B2E3,color:#334155
    style E fill:#E5F4EC,stroke:#A3CBB5,color:#334155
    style F fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
    style G fill:#FFF5DE,stroke:#E8D29A,color:#334155
    style H fill:#E8EDF2,stroke:#B8C3CE,color:#334155

    linkStyle default stroke:#A3B8AC,stroke-width:1.5px

During STW, application threads cannot continue executing normal business logic, which affects program response time.

2. What Is a Safepoint?

A safepoint is a point at which the runtime can safely suspend a thread and inspect its execution state.

At a safepoint, the runtime can usually determine:

  • What code the current thread is executing.
  • Which registers and stack locations contain object references.
  • The current stack frame structure.
  • How to safely walk the thread stack.

Safepoints are an important foundation for GC to correctly identify object references.

Note that a safepoint is not just any machine instruction, nor does it mean that all threads can be suspended immediately at any time.

3. The Performance Impact of STW

STW mainly affects:

  • Request response time.
  • Application throughput.
  • The execution determinism of real-time systems.
  • The stability of latency-sensitive services.

For example, if an online service has an average response time of 20 ms and a GC pause causes some requests to wait an extra 200 ms, tail latency can be noticeably affected.

Therefore, GC optimization usually requires a trade-off among throughput, memory footprint, and pause time.

VII. Concurrent Garbage Collection and Incremental Garbage Collection

To reduce STW time, modern GCs introduce concurrent collection and incremental collection mechanisms.

1. Concurrent GC

Concurrent GC means that garbage collection threads and application threads execute at the same time.

Traditional fully stop-the-world collection may require stopping the application for an extended period.

Concurrent GC, by contrast, attempts to run some GC phases in parallel with the application.