自動回收弱表

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 中的雜湊元素通常會有大量的鬆弛度為對齊限制的結果。只需要一個位元表示它是作為防護物件的鍵或值即可。

另選方案是將所有防護資訊保存在一個固定大小的儲存區域中。一個定大小的雜湊表可以使用於維護防護清單頭指標，而一個定大小的向量則是用於維護防護（obj、next）對。如果垃圾回收器用盡了這個結構中的空間，它會在垃圾回收的其餘部分忽略弱連結，並且下次再為防護結構配置更多空間。

所有這些都會影響標記速度和儲存。所以問題是，這是值得的嗎？

我在 Lua 實作弱表之前就遇到了這個問題，當時我正在嘗試編寫可以利用這些弱表的程式碼。不幸的是，我正在編寫的程式碼幾乎可以保證建立弱鍵值與相對應值之間的循環參考，我了解到這在提議的實作方式中是不可行的。具體來說，我試圖建立持久的函式封包。簡單的方法是保留函式的未編譯文字，並使用函式本身作為鍵以提取文字。然而，在 Lua 中的函式物件是封包，而不仅仅是函式；在封包可以被序列化的之前，需要序列化它的所有提升值。此外，必須以某種方式維護物件身分識別。所有這些表示保留一個弱表，其鍵為封包，而值是一個複雜結構，包括實際的提升值。現在，一個遞迴函式本身有它自己作為提升值，我了解到，遞迴函式將永遠不會被垃圾回收。

一方面，我認為這是必要的變動。現有的演算法有缺陷，可能會在人們意想不到的情況下對他們造成影響。一般而言，很難知道一個鍵是否可以從一個值到達，而這正是垃圾收集應該避免的分析。另一方面，問題會發生的情況可能在多數程式碼中很少見，而額外的負擔和複雜度絕對是考量因素。

--RiciLake

目前當表格在鍵值和值都標示為 weak 時，當任一鍵或值無法存取時都會收集條目。新的選項是否為當鍵和值都無法存取時才收集條目，而不會追蹤它們中的任何一個，解決上述遞迴函式問題？這樣看似會解決鍵值之間消除列印關係的普遍問題。 — DougCurrie

另請參閱

• ["Barros 與 Ierusalimschy 編寫的 Eliminating Cycles in Weak Tables"]