如何实现一个简单的垃圾回收器？

直接回答

最简单的垃圾回收器是标记-清除（Mark-Sweep）型：维护所有已分配对象的列表，从根集合（全局变量、栈上引用等）出发做图遍历，给可达对象打上标记；然后扫描全部对象，回收未标记的，并清除标记位。配套一个分配接口负责登记新对象。

展开解析

实现要点：每个对象头加一个 mark 位和一个引用列表；根集合要明确，比如解释器里的全局表和调用栈。标记阶段用 DFS/BFS，注意防止环导致死循环（标记位天然解决）。清除阶段把未标记对象释放回空闲列表。易错点包括：遍历中分配新对象导致状态不一致，通常加 GC 暂停（stop-the-world）规避；忘记重置标记位。进阶可谈引用计数（无法处理循环引用）、分代假设、三色标记与增量回收。一个极简实现两三百行 C/Python 即可完成，Toy GC 是常见练习。

示例

class GC:
    def __init__(self):
        self.objects, self.roots = [], []
    def mark(self):
        stack = list(self.roots)
        while stack:
            o = stack.pop()
            if not o.marked:
                o.marked = True
                stack.extend(o.refs)
    def sweep(self):
        alive = [o for o in self.objects if o.marked]
        for o in alive: o.marked = False
        self.objects = alive