垃圾回收弱表

wiki

摘自我在 Lua-L 上发表的一篇长文章，解释了为什么弱表不是解决特定问题的可行方案，因为键可能从值中访问。

弱表的问题在于它们在键和值之间建立了一种偶然关系，而垃圾回收算法不知道这种关系。

假设 w 是一个弱键表，我执行以下操作

do
  local t = {}
  w[t] = t
end

现在，即使 t 明显可以立即进行垃圾回收，它也不会被回收。原因如下

虽然 w 的键是弱的，但它的值是强的。因此，垃圾回收器会标记所有值。然后，它会检查键。但是，键 t 被标记了，因此它被保留。结果：t 永远不会被垃圾回收。

更一般地说，如果一个弱键可以从它自己的值中访问，那么该键将永远不会被回收。

这是否是一个错误取决于个人观点。一方面，弱表的目的是建立一种偶然关系

weak[k] = v

表示“如果 k 可访问，则 v 通过 weak 可访问”。

如果不是因为表迭代，故事就到此为止了，但理论上你可以遍历表；因此，说通过 weak 到 v 的唯一路径是通过 k 并不完全正确。

但是，我抛弃了这个论点，因为通常如果 k 变得不可访问，v 会从表中消失。我个人偏好（可能是强迫性的理论）是迭代路径不应该用于弱键表。但我离题了。

这个问题有一个解决方案，但它很丑陋。我在思考了将近一年后想出的最佳算法是给 *每个* 对象一个指向偶然列表的额外指针。当垃圾回收弱键表时（实际上，相同的论点适用于弱值表，但偶然关系是相反的），垃圾回收器不必标记所有值，而是必须构建一个偶然关系的链表，大致如下面的伪代码（Lua 语法，但当然这必须用 C 语言实现）

function mark_weak_keyed_table(weak)
  for k, v in weak
    if marked(k) then
      mark(v)
    else
      k.contingency = {obj = v, next = k.contingency)
    end
  end
end

现在，当一个对象被标记时，我们需要

function mark(obj)
  local other = obj.contingency
  while other do
    mark(other.obj)
    other = other.next
  end
  -- mark everything obj references
end

这个问题有两个方面。首先，垃圾收集器需要大量的可用内存来存储应急链表，其次，任何对象都可以拥有任意数量的引用，这会导致标记栈爆炸。

解决第二个问题有很多方法；最简单的方法是链接应急链表，这要求每个对象都拥有一个应急链表指针和一个下一个应急链表指针。

解决第一个问题的一个方法是在我们认为它们可能需要时分配应急对象，而不是在垃圾收集时分配。弱表中的每个元素都是一个潜在的应急对象，因此简单的解决方案是在每个部分弱表中的每个键值对中添加一个额外的链接指针。（但实际上它必须是每个表，因为 Lua 允许在任何时候将表设置为弱表。）

这是合理的，因为只需要链接字段（应急对象已经是键值对的一部分），并且由于对齐约束，Lua 哈希元素通常有很多空闲空间。只需要一个位来指示是键还是值是应急对象。

另一种方法是将所有应急信息保存在一个固定大小的存储区域中。可以使用一个固定大小的哈希表来维护应急链表头指针，并使用一个固定大小的向量来维护应急（对象，下一个）对。如果垃圾收集器在这个结构中用完了空间，它就会忽略剩余垃圾收集过程中的弱链接，并在下次分配更多空间用于应急结构。

所有这些都会对标记速度和存储产生影响。所以问题是，它值得吗？

我甚至在 Lua 实现弱表之前就遇到了这个问题，当时我试图编写利用弱表的代码。不幸的是，我正在编写的代码几乎肯定会创建弱键和对应值之间的循环引用，我意识到它在提出的实现中是不可行的。具体来说，我试图创建持久函数闭包。简单的解决方案是保留函数的未编译文本，并使用函数本身作为键来提取文本。但是，在 Lua 中，函数对象是闭包，而不仅仅是函数；在序列化闭包之前，有必要序列化其所有上值。此外，有必要以某种方式维护对象标识。所有这些意味着保留一个以闭包为键的弱表，其值为一个包含实际上值的复杂结构。现在，递归函数本身就是一个上值，我意识到递归函数永远不会被垃圾收集。

一方面，我认为这是一个必要的改变。现有的算法存在缺陷，可能会以意想不到的方式影响用户。通常很难知道一个键是否可以从一个值访问，而垃圾回收正是为了避免这种分析。另一方面，问题发生的场景在大多数人的代码中可能很少见，而额外的开销和复杂性无疑是需要考虑的因素。

--RiciLake

目前，当表在键和值中都被标记为弱时，当键或值不可达时，条目会被回收。是否可以添加一个新的选项，当键和值都不可达时，在不追踪它们的情况下回收条目，以解决上面提到的递归函数问题？这似乎可以解决消除键和值之间依赖关系的普遍问题。-- DougCurrie

另请参阅

• ["弱表中消除循环" by Barros & Ierusalimschy]