GC 基础入门

什么是GC（Garbage Collection）？

内存管理方式通常分为两种：

手动内存管理（Manual Memory Management）
自动内存管理（Garbage Collection, GC）

手动内存管理

手动内存管理是指开发者直接管理内存的分配和释放。典型的语言如C、C++使用malloc/free、new/delete等来手动分配和释放内存。

优点：

精确控制内存的分配和释放。
可预测的性能，没有GC带来的额外开销。
不需要的内存可以立即释放，从而节省资源。

缺点：

存在**内存泄漏（Memory Leak）**问题。
存在**悬挂指针（Dangling Pointer）**问题。
开发复杂度增加。

内存泄漏： 分配的内存未被释放，导致程序运行期间内存占用持续增加，可能导致系统内存耗尽而崩溃。 悬挂指针： 已释放的内存被引用时，可能会引发不可预测的行为。

近年来，Rust通过所有权系统（Ownership System）提供了一种安全的内存管理方式，这并不是完全的手动内存管理，而是手动内存管理的一种新替代方案。

GC（垃圾回收）

GC是编程语言中自动回收不再使用的内存的功能。接下来我们将详细解释这一机制。

自由存储列表（Free-Storage List）

在任何时刻，只有一部分为列表结构预留的内存实际上用于存储S表达式（S-expressions）。其余的寄存器（在我们的系统中大约有15,000个）组成了一个称为**自由存储列表（free-storage list）**的单一列表。程序中的某个特定寄存器FREE包含该列表的第一个寄存器位置。

当需要额外的列表结构时，自由存储列表的第一个单词将被使用，并且寄存器FREE的值会更新为自由存储列表的第二个单词位置。用户不需要编程将寄存器返回到自由存储列表中。

——《Recursive Functions of Symbolic Expressions Their Computation by Machine, Part I》John McCarthy

GC的概念始于1960年，约翰·麦卡锡（John McCarthy）在其论文《Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I》中介绍了自由存储列表（Free-Storage List）的概念，这是后来GC（垃圾回收）的基础思想。

为什么需要这个概念？

LISP（LISt Processor）是一种高级语言，支持符号处理（Symbolic Processing）和递归调用（Recursion）。然而，当时的计算机技术难以应对LISP复杂的内存管理问题。LISP在运行过程中不断生成对象，未使用的对象（垃圾）堆积会导致严重的内存泄漏问题。由于程序员很难完全追踪所有的内存分配和释放，因此引入了自动内存管理技术。

自由存储列表（Free-Storage List）是早期LISP系统中实现自动内存管理的基础概念。当时LISP采用动态生成列表结构的方式，程序员显式释放内存非常困难。为了解决这个问题，引入了跟踪未使用内存块的Free-Storage List概念，这最终发展为自动内存管理的思想。其基本原理是使用特定寄存器（FREE）存储可用内存列表的起始位置，按需获取内存并在不再使用时将其返回。这种思想成为了后来Mark-and-Sweep方式GC的基础。

Newell-Shaw-Simon 的列表存储方式的一个重要特点是，即使相同的数据多次出现，也可以只在计算机内存中存储一次。也就是说，列表可以“重叠(overlapped)”。
然而，这种重叠会在删除(erasure)过程中引发问题。当不再需要某个列表时，必须选择性地删除那些没有与其他列表重叠的部分。在LISP中，麦卡锡(McCarthy)提出了一个优雅但低效的解决方案。
本文则描述了一种能够实现高效删除的通用方法。
——《A Method for Overlapping and Erasure of Lists》 (1963)，George E. Collins

尽管约翰·麦卡锡的论文奠定了Mark-and-Sweep方法的基础，但在执行GC时会导致程序暂停（Stop-the-World）现象。这使得实现实时GC变得困难。因此，Collins提出了引用计数(Reference Counting)的概念作为GC方法。
该方法通过为每个对象保存一个引用计数(Reference Count)，并在引用计数变为0时立即回收内存。

Collins（1960年）提出的引用计数GC虽然实现了即时内存回收，但由于循环引用问题，并不是一个完美的解决方案。
尽管如此，现代语言如Python和Swift仍然使用这种方法，但加入了一些补充技术来解决其缺陷。

（顺便提一句，“优雅但低效”这样的评价让我觉得有趣。程序员这个职业似乎总有一种特点，他们喜欢用“优雅”的方式讽刺对方。也许是因为讨论的是抽象概念，缺乏实体暴力的存在感？在韩国，如果有人这样说话，可能会被拳头教训吧。）

《A LISP Garbage Collector for Virtual-Memory Computer Systems》论文摘要

本文提出了一种适用于非常大的虚拟内存环境的列表处理系统的垃圾回收算法。
该算法的主要目的不是“释放空闲内存”，而是压缩活动内存(compaction) 。
在虚拟内存系统中，由于空闲内存实际上并不会耗尽，因此很难决定何时触发垃圾回收。因此，本文讨论了触发垃圾回收的各种条件。
——《A LISP Garbage Collector for Virtual-Memory Computer Systems》 (Fenichel & Yochelson, 1969)

（虚拟内存(Virtual Memory)：一种逻辑上管理超出物理内存大小的大容量内存的技术。）

这篇论文改进了Minsky的复制式GC(Copying GC)，使其能够在虚拟内存环境中高效运行。
本文实际实现了Minsky的垃圾回收器，它利用深度优先搜索(DFS, Depth-First Search)将可达数据复制到辅助存储器中，分配到新的连续地址后重新加载回内存。尽管有评论认为其实现完成度较低（因为稍后会详细解释，所以这里不需要完全理解），这篇论文是首次将Minsky的方法应用于现代虚拟内存环境中的“Copying GC”，如果没有这篇论文，Java和C#中的分代GC(Generational GC)概念可能就不会出现。

“提出了一种简单的非递归（nonrecursive）列表结构压缩方法或垃圾收集器。该算法适用于紧凑（compact）结构和LISP风格的列表结构。通过逐步利用部分结构来追踪复制的列表，从而消除了对递归的依赖。” — （C. J. Cheney, 1970）

随后，使用广度优先搜索（BFS, Breadth-First Search）而非深度优先搜索（DFS），设计了一种“非递归（Nonrecursive）”的GC，使其能够在没有栈的情况下运行。
这项研究对Java、C#、Python的Copying GC方式产生了重要影响，基于BFS的设计避免了栈溢出问题，并具有缓存友好的结构。

为什么BFS可以以非递归的方式实现，而DFS不能？

首先，大多数读者应该知道，栈是一种**后进先出（LIFO, Last In, First Out）的数据结构。最后添加的元素会最先被移除。
队列则是一种先进先出（FIFO, First In, First Out）**的数据结构。也就是说，最先添加的元素会最先被移除。

DFS的工作原理

DFS采用一种沿着某条路径深入探索到底，然后回溯（backtracking）的方式。为了实现这一点，DFS需要使用栈（Stack）或递归函数（Recursive Call）。
DFS基于栈的原理如下：

将当前节点存储在栈中（或通过递归调用）。
如果有下一个要访问的节点，则继续通过栈调用（或递归调用）进行处理。
当没有更多可前进的地方时，执行回溯（返回上一步）。

BFS的工作原理

BFS则是基于队列的原理：

将起始节点添加到队列中（Enqueue）。
从队列中取出一个节点（Dequeue），访问它，并将其相邻节点重新添加到队列中。
重复上述过程，直到访问完所有节点。

由于BFS使用队列，因此不需要额外的递归调用。

以洞穴探险为例

DFS

在洞穴探险时，DFS会选择一条路一直走到尽头，如果路被堵住，就会回溯并尝试新的路径。
当路被堵住时，必须记住（存储）返回的路径，否则无法回到原点。

BFS

BFS会在洞口布置一支队伍，同时探索所有的岔路。先确认第一层的所有路径，然后再进入下一层。
为了合理分配队伍，必须优先安排最早到达的岔路。

GC的发展历程

年代	研究者	GC算法	改进点	问题
1960	John McCarthy	Mark-and-Sweep	首次引入GC概念	Stop-the-World，碎片化问题
1963	Marvin L. Minsky	Copying GC（基于DFS）	解决内存碎片化，优化缓存	循环引用问题，磁盘使用
1969	Fenichel & Yochelson	Copying GC（虚拟内存应用）	使用两个半空间（Semispaces）	内存不足时程序变慢
1970	C. J. Cheney	非递归Copying GC（基于BFS）	无需栈即可进行GC	BFS基础，内存重定位优化较少

GC算法发展的意义是什么？

通过减少“Stop-the-World”问题，并逐步向实时（Concurrent）GC发展，我们可以看到GC的进步过程。

那么现在让我们总结一下垃圾回收器有哪些算法，以及这些算法的概述。

在进入主题之前，先简单介绍一些基础知识：

我们通常将内存管理分为两个池：堆内存和栈内存。
栈内存主要用于存储小型（短生命周期）的数据（主要是值类型）。
堆内存则用于存储更大、更持久的数据（主要是引用类型）。

GC算法大致可以分为两类：

1. Tracing GC（追踪型GC）

这是最常见的GC类型。
垃圾回收通过可达性（Reachability）来判断某个对象是否为垃圾。
从根（Root，如全局变量、栈变量等）开始查找可达对象（Reachable），然后销毁不可达对象（Unreachable）。
如果没有有效的引用，对象会被标记为unreachable并被回收。
常用的算法主要有以下三种（附带代码仅为作者学习核心概念实现的伪代码，不保证实际运行效果）。

1-1. Mark-and-Sweep（标记-清除）

(ref: Demystifying memory management in modern programming languages | Technorage)

#include <iostream>
#include <vector>
#include <algorithm>

// Mark-and-Sweep GC 实现（使用原始指针）
class Object {
public:
    bool marked;                       // GC 标记状态
    std::vector<Object*> children;     // 子对象列表
    Object() : marked(false) {}
    
    // 添加子对象的方法
    void addChild(Object* child) {
        children.push_back(child);
    }
    
    // 析构函数：对象被删除时打印日志（用于调试）
    ~Object() {
        std::cout << "Deleting Object at " << this << std::endl;
    }
};

// 全局堆和根对象容器
std::vector<Object*> heap;
std::vector<Object*> roots;

// 递归标记对象及其子对象
void mark(Object* obj) {
    if (obj == nullptr || obj->marked) {
        return;
    }
    obj->marked = true;
    for (Object* child : obj->children) {
        mark(child);
    }
}

// 清除阶段：删除未标记的对象并从堆中移除
void sweep() {
    auto it = heap.begin();
    while (it != heap.end()) {
        Object* obj = *it;
        if (!obj->marked) {
            // 释放无法到达的对象
            delete obj;
            it = heap.erase(it);
        } else {
            // 复位标记以便下次 GC 运行
            obj->marked = false;
            ++it;
        }
    }
    
    // 更新根对象列表，仅保留仍在堆中的对象
    std::vector<Object*> newRoots;
    for (Object* root : roots) {
        if (std::find(heap.begin(), heap.end(), root) != heap.end()) {
            newRoots.push_back(root);
        }
    }
    roots = newRoots;
}

// 执行完整的 GC 过程：标记并清除
void gc() {
    for (Object* root : roots) {
        mark(root);
    }
    sweep();
}

int main() {
    // 创建对象并加入堆中
    Object* a = new Object();
    Object* b = new Object();
    Object* c = new Object();
    
    // 设定对象间的引用关系
    a->addChild(b);
    b->addChild(c);
    
    // 将所有对象加入堆
    heap.push_back(a);
    heap.push_back(b);
    heap.push_back(c);
    
    // 设定根对象（此处 a 作为根对象）
    roots.push_back(a);
    
    std::cout << "Heap size before GC: " << heap.size() << std::endl;
    
    // 执行垃圾回收
    gc();
    
    std::cout << "Heap size after GC: " << heap.size() << std::endl;
    
    // 释放剩余的对象（实际系统中最终 GC 运行时会处理）
    for (Object* obj : heap) {
        delete obj;
    }
    heap.clear();
    roots.clear();
    
    return 0;
}

（如果在代码中使用C++的RAII特性并通过shared_ptr管理内存，则很难观察到GC的实际操作，因此需要使用原始指针。）

Mark阶段 ：识别正在使用的对象。
Sweep阶段 ：删除不可达对象。
出现内存碎片化（Fragmentation）问题。

简而言之，从Root Space找到连接的对象，并删除未连接的对象。
优点是实现相对简单，且能有效保留必要的对象，避免浪费内存。
缺点是会出现“Stop-the-World”现象，并产生内存碎片化问题。

内存碎片化 ：当内存单元在堆中分配时，其大小取决于存储变量的大小。回收内存时，堆内存会分裂成碎片。

内部碎片化 ：已分配内存块中未使用的空间（例如分配4KB但只使用1KB）。
外部碎片化 ：可用内存分散，无法分配大块内存。

(img ref: Visualizing memory management in V8 Engine (JavaScript, NodeJS, Deno, WebAssembly) | Technorage )

1-2. Mark-Compact（标记-整理）

在Mark阶段之后，将存活对象移动到内存的一侧以进行整理（Compaction），从而解决碎片化问题。
缺点是整理过程中会产生额外的开销，GC时间较长。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

constexpr std::size_t HEAP_SIZE = 1024;

// 对象类 (简单链表结构)
class Object {
public:
    int value;
    Object* next;
    explicit Object(int val) : value(val), next(nullptr) {}

    // 析构函数 (调试用途)
    ~Object() {
        std::cout << "Deleting Object with value " << value << " at " << this << std::endl;
    }
};

// 使用两个半空间 (Semispace) 进行内存管理
std::vector<char> fromSpace(HEAP_SIZE);
std::vector<char> toSpace(HEAP_SIZE);

std::size_t fromIndex = 0;
std::size_t toIndex = 0;

// 在给定的空间中分配对象 (使用 placement new)
Object* allocate(int val, std::vector<char>& space, std::size_t& idx) {
    if (idx + sizeof(Object) > space.size()) {
        return nullptr; // 空间不足
    }
    Object* obj = new (&space[idx]) Object(val);
    idx += sizeof(Object);
    return obj;
}

// 递归复制对象及其链接
Object* copy(Object* obj, std::vector<char>& targetSpace, std::size_t& targetIdx) {
    if (obj == nullptr) {
        return nullptr;
    }
    Object* newObj = allocate(obj->value, targetSpace, targetIdx);
    if (newObj == nullptr) {
        return nullptr;
    }
    newObj->next = copy(obj->next, targetSpace, targetIdx);
    return newObj;
}

// 复制垃圾回收 (Copying GC) - 复制所有可达对象到新的空间
void gc(Object*& root) {
    toIndex = 0;
    Object* newRoot = copy(root, toSpace, toIndex);

    // 交换空间，使新分配的空间成为新的堆
    std::swap(fromSpace, toSpace);
    fromIndex = toIndex;
    root = newRoot;
}

int main() {
    // 在 fromSpace 中分配对象
    Object* a = allocate(10, fromSpace, fromIndex);
    if (a == nullptr) {
        std::cerr << "Allocation failed for object a." << std::endl;
        return 1;
    }
    Object* b = allocate(20, fromSpace, fromIndex);
    if (b == nullptr) {
        std::cerr << "Allocation failed for object b." << std::endl;
        return 1;
    }
    a->next = b;

    std::cout << "Before GC, root object value: " << a->value << std::endl;

    // 运行 GC
    gc(a);

    std::cout << "After GC, copied root object value: " << a->value << std::endl;

    return 0;
}

1-3. Copying GC（复制型GC）

将内存分为两个半空间（Semi-Space），分别称为From-Space和To-Space。
仅将可达对象复制到新空间（To-Space），然后销毁旧空间。
优点是没有内存碎片化，分配速度快；缺点是内存使用效率低（仅使用一半的内存）。

2. Reference Counting（引用计数）

#include <iostream>
#include <unordered_map>

// 对象类：存储简单整数值
class Object {
public:
    int value;
    explicit Object(int val) : value(val) {}

    // 析构函数: 当对象被释放时打印日志
    ~Object() {
        std::cout << "Deleting Object with value " << value << " at " << this << std::endl;
    }
};

// 全局引用计数表
std::unordered_map<Object*, int> refTable;

// 创建对象并初始化其引用计数
Object* createObject(int val) {
    Object* obj = new Object(val);
    refTable[obj] = 1;
    return obj;
}

// 增加对象的引用计数
void addRef(Object* obj) {
    if (obj != nullptr) {
        auto it = refTable.find(obj);
        if (it != refTable.end()) {
            ++(it->second);
        }
    }
}

// 释放对象的引用：当引用计数为0时删除对象
void releaseRef(Object* obj) {
    if (obj != nullptr) {
        auto it = refTable.find(obj);
        if (it != refTable.end()) {
            if (--(it->second) == 0) {
                refTable.erase(it);
                delete obj;
            }
        }
    }
}

int main() {
    // 创建对象
    Object* a = createObject(10);
    Object* b = createObject(20);

    // 增加 b 的引用计数 (模拟多个地方使用)
    addRef(b);

    // 释放 b 的引用：两次调用后计数变为0，对象被释放
    releaseRef(b);
    releaseRef(b);

    // 释放 a
    releaseRef(a);

    std::cout << "Remaining objects in refTable: " << refTable.size() << std::endl;
    return 0;
}

（使用全局引用表unordered_map，在创建对象时将引用计数初始化为1，并通过addRef和releaseRef调整引用计数。当引用计数为0时调用delete。）

每个对象存储一个引用计数（Reference Count），当引用计数为0时立即释放内存。
由于可以立即释放内存，因此没有“Stop-the-World”现象，且对象的使用量清晰可见。
缺点是存在循环引用问题，并且在处理大型对象时性能下降。
Swift中使用了改进版的ARC（Automatic Reference Counting）。

核心总结

分类	Tracing GC (Mark & Sweep)	Reference Counting GC
基本概念	从根开始追踪并清理对象	根据对象的引用计数释放内存
内存泄漏可能性	可能存在循环引用（GC自动解决）	循环引用导致内存泄漏
GC执行成本	与对象数量和引用图大小成正比	对象越多计算负担越大
性能	对象越多性能越可能下降	引用计数立即归零时快速释放
Stop-the-World(STW)	GC执行时暂停	立即释放，无需暂停
典型应用场景	C#, Java, Python	Objective-C (ARC), Swift

此外，除了基本的GC算法外，还有一些优化策略。

GC优化策略有哪些？

最常见的是Generational GC（分代GC） 。

1. Generational GC（分代GC）

根据对象的生存周期将其分为Young Generation和Old Generation，并对新生代（Young）快速GC，对老年代（Old）缓慢GC。
接下来我们看看Young和Old是如何划分的。

1-1. Young Generation（Eden + Survivor Space）

Eden（伊甸园）区域
新创建的对象首先分配到这里。大多数对象在这里生成后很快就会被销毁，因此GC频繁发生。
Survivor（幸存者）区域
Eden区域中经过GC后存活的对象会移动到这里。通常有两个Survivor区域。对象多次经历GC后最终晋升到Old Generation。
Survivor区域通常分为两个：Survivor0（From Space）和Survivor1（To Space）。
在这里，新创建的对象存储在此，大部分对象会快速销毁。此区域使用Copying GC快速移除对象。
当该区域中的对象被移除时，称为Minor GC。

1-2. Old Generation（老年代）

Tenured（老年）区域
多次在Young Generation中经历GC后存活的对象会移动到这里。
此区域GC较少发生，但一旦发生，涉及的对象较多，处理成本较高。
老年代对象存储在这里，使用Mark-Sweep或Mark-Compact方式进行清理。
利用对象生命周期模式进行性能优化。当此区域中的对象被移除时，称为Major GC（或Full GC）。
Young GC快速执行，Old GC较慢执行，但在Old Generation中发生GC时可能会出现“Stop-the-World”。

通常，Old区域分配较大，因此GC发生的频率低于Young区域。

可以用人类一生的例子来说明：