第 26 章：垃圾收集（Garbage Collection）

原文：Robert Nystrom, Crafting Interpreters, Chapter 26。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。

我想要，我想要， 我想要，我想要， 我想成为垃圾。

The Whip，《Trash》

Lox 是“高级”语言，因为实现替用户处理与问题无关的细节。动态内存分配正是适合自动化的工作：不可少、手工枯燥、又极易出错，错误会带来崩溃、内存损坏乃至安全漏洞。Lox 因而是托管语言：VM 自动分配、自动释放，程序员只看到近似无限的内存幻觉。现实内存有限，维持幻觉的部件就是垃圾收集器（GC）：在后台回收程序不再需要的内存以供复用。

26.1 可达性（Reachability）

GC 面临的问题是：如何判断哪段内存以后不再需要？只有未来会被读取的内存才有用，VM 却不能穿越未来。因此采用保守近似：只要某内存未来可能被访问，就保留它。这里的“保守”是一般意义；特指的 conservative GC 会把看似地址的任意内存都当指针，而本章的精确 GC明确知道哪些字是对象指针、哪些是数字、布尔或 nil。

var a = "first value";
a = "updated";
// GC here.
print a;

赋值完成后，"first value" 仍在堆中，却再无路径可从程序访问，故可安全回收。能通过用户程序引用的值称可达，否则称不可达。

VM 可直接访问的对象是根（root），例如全局表、值栈中的局部变量与临时值：

var global = "string";
{
  var local = "another";
  print global + local;
}

在拼接后、打印前暂停时，VM 可从全局表找到 "string"，从栈找到 "another" 与临时拼接结果。间接引用也必须保留：

fun makeClosure() {
  var a = "data";
  fun f() { print a; }
  return f;
}
{
  var closure = makeClosure();
  // GC here.
  closure();
}

此时 "data" 不在栈上，已位于闭包的已关闭上值；根是栈中的 closure，但 GC 必须沿闭包、上值数组和上值继续追到字符串。

可达性的归纳定义是：

• 所有根都可达。
• 可达对象引用的任何对象也可达。

据此，先从根遍历对象引用取得完整可达集，再释放未在集合中的对象。各类 GC 都大体包含这两件事，只是实施细节不同；深入可参考 The Garbage Collection Handbook。

26.2 标记-清扫垃圾收集（Mark-Sweep Garbage Collection）

Lisp 发明者 John McCarthy 为第一个 Lisp 实现设计了最简单的 mark-and-sweep：

1. 标记：从根遍历所有可达对象图，访问对象便留下标记。
2. 清扫：标记完成后，未标记对象必不可达，遍历并释放它们。

这种遍历对象图的算法称 tracing collector，与用引用计数跟踪对象的策略不同。

26.2.1 收集垃圾（Collecting garbage）

整个章节最终汇入：

void collectGarbage();
void freeObjects();

void collectGarbage() {
  /* mark roots, trace references, sweep */
}

何时调用收集器稍后讨论。先加入 DEBUG_STRESS_GC：每次 reallocate() 扩大内存时强制收集；释放或缩小不触发，尤其 GC 自己释放内存时不能递归收集：

void* reallocate(void* pointer, size_t oldSize, size_t newSize) {
  if (newSize > oldSize) {
#ifdef DEBUG_STRESS_GC
    collectGarbage();
#endif
  }
  /* realloc/free */
}

在分配前收集是经典接入点：内存管理器本已被调用，且只有需要新内存时才确实需要空间。若不由分配触发，就须保证所有“循环且可分配”的路径都有别的触发点，否则 VM 可能内存饥饿。更复杂的收集器可并发运行，或在函数调用、后向跳转等执行点穿插运行。

26.2.2 调试日志（Debug logging）

GC 很不透明：此前没 GC 程序也能运行，如何知道它是否做了正确的事？DEBUG_LOG_GC 可在收集开始/结束、对象分配/释放处打印信息：

void collectGarbage() {
#ifdef DEBUG_LOG_GC
  printf("-- gc begin\n");
#endif
  /* collection */
#ifdef DEBUG_LOG_GC
  printf("-- gc end\n");
#endif
}

/* allocateObject(): */
printf("%p allocate %zu for %d\n", (void*)object, size, type);
/* freeObject(): */
printf("%p free type %d\n", (void*)object, object->type);

26.3 标记根（Marking the Roots）

对象像夜空星点散落在堆上，引用构成 GC 遍历的图。collectGarbage() 先调用 markRoots()；最主要的根是 VM 值栈：

static void markRoots() {
  for (Value* slot = vm.stack; slot < vm.stackTop; slot++) {
    markValue(*slot);
  }
}

void markValue(Value value) {
  if (IS_OBJ(value)) markObject(AS_OBJ(value));
}

数字、布尔和 nil 内联于 Value，无需 GC。对象头增加标志；新对象一律未标记：

typedef struct Obj {
  ObjType type;
  bool isMarked;
  struct Obj* next;
} Obj;

void markObject(Obj* object) {
  if (object == NULL) return;
  object->isMarked = true;
}

/* allocateObject(): */
object->isMarked = false;
object->next = vm.objects;

全局变量表也属于根，表项的键字符串和值均需标记：

static void markRoots() {
  /* stack */
  markTable(&vm.globals);
}

void markTable(Table* table) {
  for (int i = 0; i < table->capacity; i++) {
    Entry* entry = &table->entries[i];
    markObject((Obj*)entry->key);
    markValue(entry->value);
  }
}

26.3.1 不那么明显的根（Less obvious roots）

VM 还藏有用户不可见但可直接访问的引用。每个 CallFrame 持有正在执行的闭包；开放上值链表也直接由 VM 持有。更微妙的是，GC 可在编译器分配字面量或扩容常量表时运行，故必须标记当前编译器链的函数：

static void markRoots() {
  for (Value* slot = vm.stack; slot < vm.stackTop; slot++) markValue(*slot);
  for (int i = 0; i < vm.frameCount; i++) {
    markObject((Obj*)vm.frames[i].closure);
  }
  for (ObjUpvalue* upvalue = vm.openUpvalues;
       upvalue != NULL; upvalue = upvalue->next) {
    markObject((Obj*)upvalue);
  }
  markTable(&vm.globals);
  markCompilerRoots();
}

void markCompilerRoots() {
  Compiler* compiler = current;
  while (compiler != NULL) {
    markObject((Obj*)compiler->function);
    compiler = compiler->enclosing;
  }
}

compiler.h 需导出 markCompilerRoots()，其中包含 memory.h。遗漏一个根会让仍在运行的对象被回收，常在之后以随机崩溃呈现，因此是 GC 最危险的错误类别。

26.4 追踪对象引用（Tracing Object References）

仅标根还不够，要从根沿对象边继续标记。但递归遍历深图会耗尽 C 栈，VM 改用显式的灰色对象工作栈。先用三色抽象理解：

• 白色：尚未发现；收集结束仍白色的对象是垃圾。
• 灰色：已发现、已标记，但其引用尚未追踪。
• 黑色：已标记，且所有引用都已处理。

标根使它们变灰；反复处理一个灰对象，把其子对象标灰，自己变黑。灰色波前扫过可达图，未被波前触及的仍白：

26.4.1 三色抽象（The tricolor abstraction）

isMarked 记录“不是白色”，灰/黑的区分由其是否在工作栈中隐含。这个约定足以实现非递归 tracing。

26.4.2 灰色对象工作表（A worklist for gray objects）

VM 保存动态数组：

typedef struct {
  /* stack, frames, tables */
  int grayCount;
  int grayCapacity;
  Obj** grayStack;
  Obj* objects;
} VM;

初始化将计数/容量置零、指针置 NULL；freeVM() 释放 grayStack。markObject() 必须跳过空和已标记对象；否则循环引用会无限压栈。新对象标记后压入灰栈，扩容由 reallocate() 完成：

void markObject(Obj* object) {
  if (object == NULL) return;
  if (object->isMarked) return;
  object->isMarked = true;

  if (vm.grayCapacity < vm.grayCount + 1) {
    vm.grayCapacity = GROW_CAPACITY(vm.grayCapacity);
    vm.grayStack = (Obj**)reallocate(vm.grayStack,
        sizeof(Obj*) * vm.grayCount,
        sizeof(Obj*) * vm.grayCapacity);
  }
  vm.grayStack[vm.grayCount++] = object;
}

reallocate() 在 GC 内扩容灰栈时不能再次触发 GC，否则会重入；实现中借助 vm.grayStack 的分配时机避免此问题。DEBUG_LOG_GC 还可打印对象被标记的过程。

26.4.3 处理灰色对象（Processing gray objects）

traceReferences() 取尽灰栈，每取一个调用 blackenObject()：

static void traceReferences() {
  while (vm.grayCount > 0) {
    Obj* object = vm.grayStack[--vm.grayCount];
    blackenObject(object);
  }
}

blackenObject() 根据对象类型标记其边：

static void blackenObject(Obj* object) {
  switch (object->type) {
    case OBJ_CLOSURE: {
      ObjClosure* closure = (ObjClosure*)object;
      markObject((Obj*)closure->function);
      for (int i = 0; i < closure->upvalueCount; i++) {
        markObject((Obj*)closure->upvalues[i]);
      }
      break;
    }
    case OBJ_FUNCTION: {
      ObjFunction* function = (ObjFunction*)object;
      markObject((Obj*)function->name);
      markArray(&function->chunk.constants);
      break;
    }
    case OBJ_UPVALUE:
      markValue(((ObjUpvalue*)object)->closed);
      break;
    case OBJ_NATIVE:
    case OBJ_STRING:
      break;
  }
}

markArray() 遍历常量值数组并调用 markValue()。开放上值的 closed 为 nil，关闭上值才需要该字段的对象边。以后新增类、实例、绑定方法等对象时，必须同步增加其引用边；否则对象图不完整，GC 会错误释放活对象。

完整收集管线现为：

void collectGarbage() {
  markRoots();
  traceReferences();
  tableRemoveWhite(&vm.strings);
  sweep();
}

26.5 清扫未使用对象（Sweeping Unused Objects）

vm.objects 是所有堆对象的单链表，既记录分配也提供清扫入口。遍历时，已标记对象保留并清除标记以备下一轮；未标记对象从链表摘下并 freeObject()：

static void sweep() {
  Obj* previous = NULL;
  Obj* object = vm.objects;
  while (object != NULL) {
    if (object->isMarked) {
      object->isMarked = false;
      previous = object;
      object = object->next;
    } else {
      Obj* unreached = object;
      object = object->next;
      if (previous != NULL) {
        previous->next = object;
      } else {
        vm.objects = object;
      }
      freeObject(unreached);
    }
  }
}

26.5.1 弱引用与字符串池（Weak references and the string pool）

字符串驻留表 vm.strings 不能成为永久根，否则历史上创建过的每个字符串都会存活。该表应是弱表：标记完成、清扫前，删除未标记键；真正被程序引用的驻留字符串仍会被其他根标记，只有仅被表引用的字符串才会被清扫：

void tableRemoveWhite(Table* table) {
  for (int i = 0; i < table->capacity; i++) {
    Entry* entry = &table->entries[i];
    if (entry->key != NULL && !entry->key->obj.isMarked) {
      tableDelete(table, entry->key);
    }
  }
}

调用它必须位于 traceReferences() 后、sweep() 前；若先清扫，表将留下指向已释放字符串的悬挂指针。

26.6 何时收集（When to Collect）

收集频率是在吞吐量与延迟之间取舍。吞吐量是单位时间完成的用户工作；延迟是最倒霉用户等待服务的最长时间。stop-the-world GC 在清扫期间暂停用户程序：等待越久再运行，垃圾越多、单次暂停越长，延迟更高；但运行太频繁又反复访问同一批活对象，几乎不产生新垃圾，吞吐量下降。增量 GC 可交错少量 GC 和少量用户代码；并发 GC 让别的线程清扫，却需复杂协调以避免回收器与执行线程争用对象。

批处理重吞吐，手机交互重低延迟；没有免费午餐，算法与触发频率共同决定取舍。

26.6.1 延迟与吞吐（Latency and throughput）

本章收集器是 stop-the-world。频繁运行降低最长停顿，稀疏运行减少扫描活对象的无效工作；理想频率位于中间，且因程序的内存需求和分配速率而异。

26.6.2 自调节堆（Self-adjusting heap）

将调优参数交给用户并不可靠。常见简单策略是按存活堆大小自调节：记录累计托管内存，越过阈值就收集；收集后以剩余活字节的某个倍数设下次阈值。活堆变大则降低收集频率，避免总重访越来越大的活对象集合；活堆变小则更频繁收集，控制延迟：

#define GC_HEAP_GROW_FACTOR 2

typedef struct {
  /* ... */
  size_t bytesAllocated;
  size_t nextGC;
} VM;

void initVM() {
  vm.bytesAllocated = 0;
  vm.nextGC = 1024 * 1024;
}

void* reallocate(void* pointer, size_t oldSize, size_t newSize) {
  vm.bytesAllocated += newSize - oldSize;
  if (newSize > oldSize && vm.bytesAllocated > vm.nextGC) {
    collectGarbage();
  }
  /* realloc/free */
}

清扫会经 reallocate() 降低 bytesAllocated，故收集结束时已知活字节量：

size_t before = vm.bytesAllocated;
markRoots();
traceReferences();
tableRemoveWhite(&vm.strings);
sweep();
vm.nextGC = vm.bytesAllocated * GC_HEAP_GROW_FACTOR;
printf("collected %zu bytes (from %zu to %zu) next at %zu\n",
       before - vm.bytesAllocated, before, vm.bytesAllocated, vm.nextGC);

初始 1 MiB 与增长倍数都只是经验数；真实 VM 必须拿真实、大型而混乱的程序画像和调优，正如调赛车需要上赛道。

26.7 垃圾收集错误（Garbage Collection Bugs）

理论上 GC 已完成，现实却更痛苦。若漏收死对象，VM 缓慢泄漏；若误收活对象，程序访问无效内存，常不会立刻崩溃，因而难以回溯。GC 可在任何最终导致分配的调用中运行，就像抢椅子：每个想保留的堆对象都必须先成为根或被可达对象引用。

最常见的“GC 看不见而 VM 之后仍会用”的路径，是对象指针仅存在 C 栈局部变量中。GC 遍历 VM 的值栈、帧栈，却看不见 C 栈。Boehm-Demers-Weiser 这类保守收集器会扫描原生栈；精确 GC 也可能扫描 C 栈和寄存器，但更难可靠。本书此前许多“压栈、做一点工作、再弹栈”的代码，正是让临时对象在分配可能触发 GC 时成为可见根。

26.7.1 加入常量表（Adding to the constant table）

addConstant() 的动态常量数组扩容会分配；新常量对象此时只在 C 参数中，GC 会在其写入常量表前回收它。修复是临时压入 VM 栈：

int addConstant(Chunk* chunk, Value value) {
  push(value);
  writeValueArray(&chunk->constants, value);
  pop();
  return chunk->constants.count - 1;
}

写入后，编译器根会标记当前函数，常量便安全。chunk.c 因而需引入 vm.h。

26.7.2 驻留字符串（Interning strings）

新字符串准备加入驻留表时，表扩容也可触发 GC；字符串尚无其他可达路径。allocateString() 同样先压栈、写表后弹栈：

push(OBJ_VAL(string));
tableSet(&vm.strings, string, NIL_VAL);
pop();

26.7.3 拼接字符串（Concatenating strings）

OP_ADD 拼接字符串若先 pop() 两个操作数，再分配新字符数组，GC 可能看不见两字符串。应先 peek() 保留它们于栈，分配结果后再弹出并压入结果：

static void concatenate() {
  ObjString* b = AS_STRING(peek(0));
  ObjString* a = AS_STRING(peek(1));
  int length = a->length + b->length;
  /* allocate chars and takeString */
  pop();
  pop();
  push(OBJ_VAL(result));
}

这些修复简单，真正困难在发现“本该存在却不在”的对象；压力 GC 与优秀测试套件极其重要。至此 clox 拥有健壮、自调节的标记-清扫收集器。

挑战（Challenges）

1. Obj 头现在有 type、isMarked、next 三字段。测量它们在你的机器上占多少内存；能否压缩表示，代价是什么？
2. 清扫幸存对象时会清除 isMarked 供下一轮使用。设计更高效的替代方案。
3. 替换或扩展现有收集器，研究引用计数、Cheney copying algorithm 或 Lisp 2 mark-compact algorithm。

设计笔记：分代收集器（Generational Collectors）

收集器反复扫描活对象会损失吞吐；延迟收集又会累积大堆垃圾、增加停顿。对象寿命的实测研究发现分代假说（也叫不太文雅的“婴儿死亡率”）：绝大多数对象寿命很短，撑过早期后往往长期存活；活得越久，继续存活概率越高。

分代 GC 因此把新对象置入小型 nursery，频繁只扫描这里；nursery 常用复制收集器，分配和释放更快。对象每次存活就老一代，存活若干轮（常仅一轮）后被 tenure，复制到更大的老年代；老年代也收集，但远少于新生代，因为其中多数对象仍活着。它本质是两个独立调优的 GC 加一个对象晋升策略，是经验数据与算法设计的漂亮结合。