即時遊戲中的垃圾回收

wiki

版本注意事項：Lua 5.1 已經導入漸進式 GC，因此其中許多事項可能僅供歷史參考。

• 對於實質上屬於軟即時系統的動作遊戲等應用，如果 Lua 能有漸進式 GC，將會大幅受益。

• 主機遊戲通常需要達到 60Hz，否則在 30Hz 時 PS2 會出現惱人的隔行掃描。60Hz 相當於每幀最多 16.7ms 的處理時間。主 CPU 的時間在很大程度上都花在遊戲玩法和圖形任務上，這些任務通常非常耗時。因此，為了進行 GC，腳本語言的延遲真的不能夠「永遠」超過 1 或 2ms。只要創造引擎時稍加注意，即使 Lua GC 偶爾暫停長達 120ms，也只有受過特別訓練的人會注意到。另一方面，始终以 60Hz 執行並且已編寫了逐幀動畫資料的格鬥遊戲，完全無法忍受任何長幀。因此，這取決於情況而定。

• 另一方面，GC 的總攤銷開銷並沒那麼關鍵。只要 GC 的延遲永遠不超過 1 或 2ms，它就可以每幀花費這個時間。顯然，攤銷成本較低是比較好的，但對遊戲來說，最差情況下的成本更重要。

• Lua 目前使用的垃圾收集器採用傳統的簡單非漸進式標記整理演算法。當開始收集週期時，它會在標記階段遍歷可觸及的堆疊物件，然後在整理階段遍歷整個堆疊。因此，時間成本會與堆疊上的物件數目加上可觸及的物件數目成正比。

• 其他收集器類型：複製收集器可能是可行的，但對於我們的目的來說，需要的開銷可能比標記整理還高。世代收集器大幅改善了平均情況，但無法防止最差情況下的中斷。而且，世代收集器較為複雜。在標準漸進式 GC 之後，漸進式世代 GC 會是一個不錯的下一步。

• 漸進式收集器：如何使現有的標記整理演算法成為漸進式的，這個問題已經獲得充分的研究。Johnstone 的論文相當徹底地概述了相關方法。對於 Lua 來說，最主要的額外成本是 Lua VM 在變更指標的值時必須使用「寫入障礙」。寫入障礙會查看收集器的內部狀態，然後在特定情況下標記新的指標或舊的指標。

為了維持低延遲操作，必須允許垃圾回收器定期執行少量的工作。對於遊戲來說，這表示遊戲迴圈應該在每個畫面中呼叫一次垃圾回收器。這是比文獻上通常討論的更粗略的顆粒度，文獻上通常著重於多處理器的演算法。不過 Johnstone 的論文明確指出了單處理器的案例。

寫入障礙相當簡單；有一些變異視的確切演算法而定，但最後會變成大概 5 或 10 行 C 程式碼和 10 或 20 條指令。

實作注意事項：對於 Lua 實作來說，在它寫入內部（表格）指標的任何位置使用巨集會很好（也許它已經做了）。然後，一個增量收集器外掛程式可以定義這個巨集為呼叫寫入障礙的函數（或寫入障礙本身的內聯程式碼）。

• 我之前為 Scheme 解譯器撰寫過這種收集器。那個專案最困難的部分是確保在所有變更指標的案例中都有寫入障礙。這絕對辦得到，而 Lua API 會阻止主機程式存取 Lua 的內部指標，所以應該不會太難。

• 如果增量收集器在當作一般收集器使用時，可以表現得像一般收集器，那是很好的。也就是說，如果從來沒有呼叫「做一些工作」，收集仍然應該會自動發生（儘管以偶爾的長延遲為代價，就像現在一樣）。如果增量收集器不用增加程式碼大小、收集時間和記憶體使用量，而且與一般收集器相比沒有額外開銷，那是特別好的，因為這樣一來，一般的收集器就可以完全在現有的 Lua 中替換，而不會有任何損失。我猜測可以使用編譯時期切換來確保沒有額外的開銷。此外，我懷疑只要仔細一點，增量收集器就可以編寫成避免任何額外的記憶體使用量。程式碼大小和時間開銷會是什麼樣子還有待觀察。我懷疑這兩項開銷都會很小，但會大於零。

• 參照計數收集器（可能與現有的標記清除一起用）可能會達到最佳點。參照計數很直接，通常用於 C++ 遊戲引擎（因此遊戲開發人員通常了解它）和確定性的。根據 C++ 遊戲引擎的經驗，它似乎已經夠增量了。參照計數最大的缺點是無法收集循環垃圾。為了應對這個問題，可以在方便的時候呼叫標記清除。此外，程式設計師可以注意不要無意中建立循環。弱表格可以幫上忙；在 C++ 遊戲引擎中，弱指標是解決這個問題的常見方法。
  • 參照計數在空間和時間上都有相當的開銷。延遲也是一個缺點 - 一次收集一個物件可能會引發收集許多其他物件。增量垃圾回收器沒有這些問題。
  • 這些有關參考計數的問題可藉由建立一工作清單，記錄待減少計數的物件，並逐步處理這個清單得到解決。你通常可以用要釋出的物件的儲存空間來儲存這個清單。