GC 算法 #05：引用计数与循环引用检测

引用计数（Reference Counting）是另一种内存管理策略：每个对象记录有多少指针指向它，计数归零时立即释放。CPython、Swift、Rust（Rc/Arc）都采用此方案。本文深入引用计数的实现细节、循环引用问题，以及 Python 的循环检测算法和 Rust 的编译期解决方案。

相关文章：三色标记与写屏障 · 分代 GC

目录

引用计数基础

每个对象有一个引用计数字段 ref_count，初始为 0：

创建引用（赋值）：ref_count += 1（incref）
删除引用（离开作用域/重新赋值）：ref_count -= 1（decref）
  if ref_count == 0：立即释放对象，并对其所有字段执行 decref

对比追踪式 GC（JVM/Go）：
  追踪式：定期扫描所有对象，确定可达性，批量回收
  引用计数：每次赋值/删除都立即更新，引用归零立即释放

引用计数的优势：
  1. 内存立即释放（析构函数立即调用，析构时机确定）
  2. 没有 STW 暂停（不需要全堆扫描）
  3. 与系统内存压力无关（不需要等 GC 触发）
  4. 实现简单，可嵌入语言核心

引用计数的代价：
  1. 每次指针赋值/删除都有计数修改开销
  2. 多线程环境需要原子操作（ARC 的主要开销）
  3. 循环引用导致内存泄漏（核心缺陷）
  4. 析构链可能很深，单次 decref 触发长链析构

完整伪代码

class Object:
    ref_count: int = 0
    data:      any
    fields:    list[Reference]    # 指向其他对象的引用

class Reference:
    obj: Object     # None 表示空引用

# 全局对象池（仅用于演示）
heap = set()

def new_object(data, fields=[]) -> Object:
    obj = Object(data=data, fields=fields)
    obj.ref_count = 0
    heap.add(obj)
    return obj

def incref(obj: Object):
    if obj is None:
        return
    obj.ref_count += 1

def decref(obj: Object):
    if obj is None:
        return
    obj.ref_count -= 1
    if obj.ref_count == 0:
        free(obj)

def free(obj: Object):
    # 释放前，先 decref 所有子引用（可能触发级联释放）
    for ref in obj.fields:
        decref(ref.obj)
    obj.fields = []
    heap.discard(obj)
    # 实际语言中：这里调用析构函数 __del__，然后归还内存

def assign(ref: Reference, new_obj: Object):
    """ref.obj = new_obj 时的完整流程"""
    old_obj = ref.obj
    incref(new_obj)     # 先 incref 新对象（防止 new_obj == old_obj 时提前释放）
    decref(old_obj)     # 再 decref 旧对象
    ref.obj = new_obj

执行追踪：

a = new_object("A")   # ref_count[A]=0
incref(a)             # ref_count[A]=1（a 持有）

b = new_object("B")
incref(b)             # ref_count[B]=1（b 持有）

assign(a.field, b)    # a.field = b
                      # incref(B)→2，decref(None)
                      # ref_count[B]=2

decref(b)             # b 变量超出作用域
                      # ref_count[B]=1（还有 a.field 持有）

decref(a)             # a 变量超出作用域
                      # ref_count[A]=0 → free(A)
                      # free(A): decref(A.field) → decref(B)
                      # ref_count[B]=0 → free(B) ✅

循环引用问题

# 创建循环：A → B → A
a = new_object("A")
b = new_object("B")
incref(a)  # ref_count[A]=1
incref(b)  # ref_count[B]=1

assign(a.field, b)   # A.field = B，ref_count[B]=2
assign(b.field, a)   # B.field = A，ref_count[A]=2

# 模拟 a, b 局部变量超出作用域
decref(a)  # ref_count[A]=1（还有 B.field 持有）
decref(b)  # ref_count[B]=1（还有 A.field 持有）

# 此时：
#   ref_count[A] = 1（只被 B.field 引用）
#   ref_count[B] = 1（只被 A.field 引用）
#   没有任何外部引用指向 A 或 B！
#   但计数不为 0 → 永远不会被释放 → 内存泄漏！

# 根本原因：
#   引用计数只能检测"外部是否有引用"
#   无法区分"被外部引用"和"被自己的循环引用"

Python 的循环检测

CPython 同时使用引用计数（主要路径）和周期性的循环检测 GC（辅助）。

可追踪对象

# 只有"容器对象"（可能包含其他引用的对象）才参与循环检测：
# list, dict, set, tuple（含可变对象时）, class instances, etc.
# int, str, float 等不含引用，不参与

分代循环检测

# Python gc 模块维护三代列表：
# gen0（最年轻）：所有新创建的容器对象
# gen1：经过一次 gen0 GC 存活的对象
# gen2（最老）：经过一次 gen1 GC 存活的对象

# 触发：gen0 中对象数 - 已释放对象数 > threshold0（默认 700）

def collect_generation(gen):
    # 候选集：本代 + 更年轻代的所有对象
    candidates = gen0 + gen1 (if gen >= 1) + gen2 (if gen == 2)

    # 第一步：计算每个对象的"内部引用数"
    for obj in candidates:
        obj._gc_ref = obj.ref_count     # 复制真实引用计数

    # 第二步：减去容器内部的引用
    for obj in candidates:
        for child in obj.fields:
            if child in candidates:
                child._gc_ref -= 1      # 这条引用是内部的，不算

    # 第三步：_gc_ref > 0 的对象有外部引用，标记为"可达"
    reachable = {obj for obj in candidates if obj._gc_ref > 0}
    # 从可达对象传播标记（BFS/DFS）
    to_visit = deque(reachable)
    while to_visit:
        obj = to_visit.popleft()
        for child in obj.fields:
            if child in candidates and child not in reachable:
                reachable.add(child)
                to_visit.append(child)

    # 第四步：剩余 _gc_ref == 0 且不可达 → 是孤立的循环 → 释放
    unreachable = set(candidates) - reachable
    for obj in unreachable:
        # 1. 处理 __del__ 方法（可能让对象"复活"）
        if has_finalizer(obj):
            finalize_and_maybe_resurrect(obj)
        else:
            decref(obj)    # 触发级联释放

Trial Deletion 算法

Bacon & Rajan（2001）提出的纯引用计数循环检测，无需单独的 Mark-Sweep：

核心思路：
  如果某对象的所有引用都来自循环内部，
  那么"假装删除"它后，循环内所有对象的计数都应降为 0

算法（简化）：
  1. 收集"可疑"对象（ref_count > 0 但可能在循环中）
  2. 对每个可疑对象，递归"试探性减少"计数（模拟删除）
  3. 若减完后 ref_count == 0 → 在循环中（无外部引用）
  4. 收集为垃圾
  5. 若减完后 ref_count > 0 → 有外部引用，恢复计数

伪代码：
def trial_deletion(suspect):
    suspect.color = PURPLE      // 可疑
    decrease_internal(suspect)  // 减去内部引用
    scan(suspect)               // 检查是否可达
    collect_white()             // 回收不可达的

def decrease_internal(obj):
    for child in obj.fields:
        child.ref_count -= 1
        if child.color != PURPLE:
            decrease_internal(child)

def scan(obj):
    if obj.ref_count > 0:
        scan_black(obj)      // 有外部引用，恢复为黑色（存活）
    else:
        obj.color = WHITE    // 无外部引用，可能是垃圾
        for child in obj.fields:
            scan(child)

Rust 的编译期解法

// Rust 用所有权系统在编译期预防大多数循环
// Rc<T>：单线程引用计数，Arc<T>：多线程（原子操作）

use std::rc::Rc;
use std::cell::RefCell;

// 错误示例：循环引用导致内存泄漏（Rust 不阻止，但会泄漏）
let a = Rc::new(RefCell::new(vec![]));
let b = Rc::new(RefCell::new(vec![]));
a.borrow_mut().push(Rc::clone(&b));  // A → B，ref_count[B]=2
b.borrow_mut().push(Rc::clone(&a));  // B → A，ref_count[A]=2
// a, b 离开作用域后，各自 ref_count=1，永不释放 → 泄漏

// 正确做法：用 Weak<T> 打破循环
use std::rc::Weak;

struct Node {
    children: Vec<Rc<Node>>,
    parent: Option<Weak<Node>>,   // 弱引用：不增加 ref_count
}

let child = Rc::new(Node { children: vec![], parent: None });
let parent = Rc::new(Node {
    children: vec![Rc::clone(&child)],
    parent: None
});
// child.parent 用 Weak，不增加 parent 的 ref_count
// → parent 释放时 child.parent 自动变为 None（Weak 指针失效）

// Weak::upgrade：尝试获取强引用（如果对象还存活）
if let Some(p) = child.parent.as_ref().and_then(|w| w.upgrade()) {
    println!("parent still alive");
}

Swift ARC

Swift 使用 ARC（Automatic Reference Counting）在编译期自动插入 retain/release：

class A {
    var b: B?           // strong（强引用，增加计数）
    deinit { print("A freed") }
}

class B {
    weak var a: A?      // weak（弱引用，不增加计数，对象释放后自动 nil）
    // 也可用 unowned：不增加计数，对象释放后不置 nil（危险，用于确定比自己活得久的）
    deinit { print("B freed") }
}

var x: A? = A()
var y: B? = B()
x!.b = y
y!.a = x    // weak 引用，ref_count[A] 不增加

x = nil     // ref_count[A] → 0 → free A → "A freed"
            // A.b(B) 也随之 decref → ref_count[B] → 0 → free B → "B freed"
y = nil     // 此时 B 已被释放，这行 decref 是安全的（ref_count 已是 0 后的行为由语言保证）

异常场景

多线程引用计数竞争

问题：两线程同时 incref 和 decref 同一对象

单线程（CPython GIL 保护）：
  GIL 保证 incref/decref 不会并发执行 → 安全

多线程（无 GIL / C++ / Rust Arc）：
  必须用原子操作（fetch_add, fetch_sub）
  原子操作比普通整数操作慢约 10 倍（需要 CPU 缓存一致性协议）

Rust Arc vs Rc：
  Arc：原子引用计数，线程安全，有额外开销
  Rc：非原子，单线程，无额外开销，跨线程时编译报错

Python 3.12+ 无 GIL 方案（PEP 703）：
  使用"偏置引用计数"：本地线程操作无锁，跨线程才加锁
  大幅降低多线程开销

析构链过深导致栈溢出

# 场景：单链表 1000 个节点
head = Node(1)
cur = head
for i in range(999):
    cur.next = Node(i+2)
    cur = cur.next

# 释放 head：
# decref(head) → free(head) → decref(head.next)
# → free(head.next) → decref(head.next.next)
# → ... 递归 1000 次 → 栈溢出！

# CPython 的解法：
# decref 时不直接释放，而是将对象加入"待释放队列"
# 队列用迭代方式（非递归）逐一处理
# Py_TRASHCAN_SAFE_BEGIN / Py_TRASHCAN_SAFE_END 宏实现

# Rust Rc 的解法：
# drop 时检测递归深度，超过阈值时将剩余对象收集到 Vec 后迭代析构

与追踪式 GC 的对比

参考资料

• Collins, G.E. (1960). A method for overlapping and erasure of lists（引用计数发明）
• Bacon, D. & Rajan, V.T. (2001). Concurrent Cycle Collection in Reference Counted Systems
• CPython gc 模块源码：Modules/gcmodule.c
• Rust 文档：Rc, Arc, Weak: https://doc.rust-lang.org/std/rc/