Python 和 Ruby 的分代垃圾回收機制

Python部落(python.freelycode.com)組織翻譯，禁止轉載，歡迎轉發。

上周我根據上半年在 RuPy 中演講的內容寫了一篇筆記，主題為「Ruby 與 Python 的可視化垃圾回收」（譯者註：本文寫於 2013 年 10月）。我解釋了標準 Ruby（又稱為 MRI）是如何使用一套名為 標記和清掃的垃圾回收演算法，這套演算法的核心與 1960 年 Lisp 的原始版本所使用的相似。同時，我們也了解到 Python 是怎樣使用另外一套在53年前被發明，稱為 引用計數的垃圾回收演算法。 然而，除了引用計數，Python 還使用了另一種叫做分代垃圾回收的演算法。這意味著 Python 的垃圾回收器對新創建的對象和舊的對象的處理會有所不同。隨著 2.1 發布版本的到來，MRI Ruby 也將優先使用分代垃圾回收演算法。（另外兩個 Ruby 的實現版本，JRuby 和 Rubinius 已經使用了分代垃圾回收很長時間了。我將在下周的 RubyConf 談一下 JRuby 和 Rubinius 的垃圾回收機制）

當然，「對新創建的對象和舊的對象的處理會有所不同」有點讓人難以理解。究竟什麼是新對象，什麼是舊對象？實際上 Ruby 和 Python 是怎麼分別處理它們的呢？今天我將繼續講述這兩種垃圾回收器的工作原理和回答這些問題。在我們講述分代垃圾回收前，我們需要學習一些關於 Python 引用計數算計的理論問題。

我們目前已經知道 Python 使用一個整數為每個對象記錄其被引用的數目，並保存在對象裡面，這被稱為 引用計數。在你的程序里，當一個變數或其它對象引用一個對象時，Python 會增加這個計數；當你的程序停止使用這個對象時，Python 就會減小這個計數。當引用數量變為零時，Python 會析構這個對象並回收它佔用的內存。

自1960年代起，計算機科學家們就意識到這個演算法存在一些理論上的問題：當一個數據結構是一個循環引用的結構，即自己引用了自己，它們的引用計數是永遠不會變為零的。為了更好地了解這個問題，我們來看個例子。下面的代碼使用了一個 Node 類：

我們有個構造器（這在 Python 里稱為 init方法）把一個值保存到一個實例屬性里。然後我們創建了兩個 Node，「ABC」 和 「DEF」，我在左邊用矩形表示它們。在矩形里的數字 1 是它們的引用計數，因為它們分別被變數 n1、n2 引用了。

現在我們為它們倆增加一個額外的屬性，next 和 prev：

不像 Ruby，Python 可以讓你自由地定義實例變數或對象屬性。這些有趣的魔法是 Ruby 所缺少的。（聲明：本人並非使用 Python 的開發者，所以我使用的術語和命名可能存在錯誤）我們設置 n1.next 引用 n2，n2.prev 指向回 n1。現在我們的兩個 Node 通過使用循環指針變成了一個雙向鏈表。需要注意的是，這時它們的引用計數被加到 2。因為有兩個地方引用到它們：之前有 n1 和 n2，現在多了 next 和 prev。

現在我們假設我們的 Python 程序停止使用這些 Node；我們把 n1 和 n2 都設為 。（在 Python 的 是用 None 來表示）

現在 Python 像往常一樣，把它們的引用計數降到了 1。

注意上面的最後的圖例，裡面有個不尋常的情況：我們有很多不再使用但相互引用的對象，它們是已經沒有任何外部引用的。換句話說，我們的程序已經不需要再使用上面的 Node 對象了，因此我們希望 Python 的垃圾回收器可以智能地把它們析構並回收它們佔用的內存。但這並不會發生，因為它倆的引用計數是 1 而不是 0。Python 的引用計數機制無法處理這些互相引用的對象。

當然，像這樣的情況並不常見，但萬一你的程序出現循環引用的情況在一些很微妙的位置里，你是很難發現到的。在你的 Python 程序執行的過程中，它會產生不少的「漂浮垃圾」，那些不再使用但引用計數無法變為 0 而導致 Python 的回收器無法處理的對象。

這就是 Python 分代演算法出現的原因！類似 Ruby 使用一個鏈表去持續地跟蹤空閑對象的方法，Python 使用了不同的鏈表去跟蹤處於活動狀態的對象。Python 在它的 C 源碼中稱它為 零世代，而不是稱為活動列表。每當你在程序中創建一個對象或者其它的值，Python 會把它添加到零世代鏈表中：

上面你可以看到我們創建的 ABC，Python 把它添加到零世代里。注意，這並不是一個你可以在程序里看到或者接觸到的真實的列表；這個鏈表存在於 Python 的執行環境內部。

同樣地，當我們創建 DEF 時，Python 也把它添加到相同的鏈表：

現在零世代里包含兩個 Node 對象。（其實它會包含每個我們使用 Python 代碼創建的值，和 Python 內部使用的值）

Python 會循環遍歷零世代鏈表，每個被遍歷到的對象都會遞減它的引用計數。通過這種方式，Python 解除了從一個對象到另一個對象的內部引用，使得 Python 能及早地釋放對象。

為了更簡單地理解，我們來舉個例子：

你可以在從上面看到 ABC 和 DEF 的引用計數都是 1。還有其它三個對象也在零世代鏈表裡。藍色箭頭表示有其它的對象在引用著它們，這些對象處於另外一個地方 —— 來自零世代以外的地方。（我們等下將會看到 Python 也使用了稱為 一世代 和 二世代 的鏈表。）因為有來自其他的引用，這些被引用的對象有著更高的引用計數。

下面你能看到在 Python 垃圾回收器處理零世代後發生的事情。

通過識別內部引用，Python 能夠減少零世代里所有對象的引用計數。在上圖的第一行，你能看到 ABC 和 DEF 現在的引用計數已經為 0。這意味著回收器將析構它們並回收內存。那些仍然存活的對象將轉移至一個新的鏈表：一世代。

某種程度上來說，Python 的垃圾回收演算法類似 Ruby 所使用 標記和清掃演算法。它定期跟蹤對象與其它對象的引用，決定這些對象是否可以保留，存活的對象是我們的程序仍在使用的——就像 Ruby 的標記處理。

Python 是什麼時候進行這個標記操作的呢？在你的 Python 程序執行的過程中，解釋器會一直跟蹤有多少個新對象被創建，多少個對象因為引用計數為 0 而被它釋放。理論上，這兩個值應該始終一致：每個由你的程序創建的都應該從根本上被釋放。

當然，現實並不是這樣子。由於循環引用和程序中部分長期使用的對象的存在，構建和被釋放的數字差距將被慢慢拉開。當這個差值達到一個閾值，Python 的回收器就會被觸發並使用減法處理零世代鏈表裡的對象，釋放那些「漂浮的垃圾」和轉移剩餘的對象到一世代。

隨著時間的推移，你的 Python 程序中被長時間使用的對象會被從零世代轉移至一世代。Python 當構建和被釋放的差值達到一個更高的閾值時，使用同樣的方式處理一世代里的對象。Python 把剩下的對象轉移到二世代鏈表。

某種程度上，Python 程序中長時間被使用的對象將從零世代轉移到一世代再到二世代。使用不用的閾值來決定 Python 處理這些對象的間隔。Python 會頻繁的處理零世代里的對象，一世代會相對沒那麼頻繁，二世代則更久才執行一次。

這種行為是分代垃圾回收演算法的難點：相對新對象，回收器會更頻繁處理舊對象。一個新的或年輕的對象是程序中剛創建的，而舊的或成熟的對象是已經存活了一段時間的。Python 會升級對象，當它從零世代轉移至一世代，或者從一世代轉移至二世代。

為什麼要這樣做？這個演算法的關鍵思路源於弱世代假設。這個假設實際由這個思路組成：大部分的新對象要在年輕時死掉，而舊對象可能將存活一段更長的時間。

假設我使用 Python 或者 Ruby 創建了一個對象：

根據假設，我的代碼可能只在短時間內使用 ABC。對象可能只是為了作為一個函數的參數值，而當函數返回時就會成為垃圾。大部分的對象都是這樣很快地變成垃圾。偶爾地，我的程序創建少量且重要的對象並長時間使用 —— 例如 Web 應用中 session 變數或配置項里的值。

Python 的回收器花更多的時間，更頻繁的處理新對象是有很大的好處：它使得短壽命的新對象能夠更快更迅速地變成垃圾。極少情況下，當構建閾值上升到一定程度，使得 Python 的回收器去處理舊對象。

隨著 Ruby 發布版本 2.1 的到來，現在 Ruby 也在第一時間使用分代垃圾回收演算法進行垃圾回收！（記住，像 JRuby 和 Rubinius 這些其它的 Ruby 實現，已經使用這種方式好多年了。）為了了解它是如何運作的，讓我們回顧一下我上一篇文章中空閑對像鏈表的示例圖：

通過這個示例圖，我們看到有三個分別被 n1、n2 和 n3 引用的活躍對象。這些剩下的白色方塊代表垃圾對象。（當然，空閑對象鏈表使用了更複雜的模式來包含成千上萬的互相引用的對象。這個簡單的示例圖是為了幫助我們更好理解 Ruby 垃圾回收演算法的基礎原理，而不被具體的實現所干擾。）

Ruby 會把垃圾對象放置到空閑對象鏈表，當它需要構建新對象時就可以循環利用這些垃圾對象了。

Ruby 2.1 的分代垃圾收回

從 Ruby 2.1 開始，垃圾回收增加了一個步驟：它會升級剩下的活躍對象到成熟世代。（MRI C 源碼中的表述實際是 舊 而不是 成熟。）這個示例圖展示了 Ruby 2.1 對象世代的概念視圖：

左邊是空閑對象鏈表的另一個表現方式。我們看到垃圾對象是白色的，而剩下存活的、活躍的對象則是灰色的。這些灰色的對象就是被標記了的。

當標記和掃描處理完成，Ruby 2.1 將認為被標記的對象是成熟的：

跟 Python 的使用三個世代不同，Ruby 2.1 的垃圾回收器只使用兩個。這些世代並不由不同區域的物理內存組成。（一些其他編程語言的垃圾回收演算法和其它 Ruby 實現，使用一種被稱為複製式垃圾回收器，在對象升級時會對對象進行複製。）相反，Ruby 2.1 內部代碼並不會保存之前在標記和掃描中被標記的對象。對象一旦被標記，將不再參與下次的標記與掃描處理。

現在假設你的 Ruby 程序一直在執行，創建更多的新對象。這些對象也會在年輕世代中出現：

跟 Python 相似， Ruby 的回收器專註於年輕世代的處理。它在標記與掃描演算法中只關注那些在最近一次垃圾回收處理後被創建的年輕新對象。這是因為很多新對象有很大的可能已經變成垃圾（如圖中左邊的白色盒子）。Ruby 不會重複標記圖中右邊的成熟對象。因為它們已經免除了一次垃圾回收的處理，意味著它們有可能會保持活躍並存活很長的一段時間。因為只標記年輕的對象，使得 Ruby 的垃圾回收代碼能執行的更快。它跳過了對成熟對象的處理，減少了程序等待垃圾收回完成的時間。

Ruby 會偶爾執行「完全回收」，連同成熟對象一起進行標記與掃描。Ruby 通過監控成熟對象的數量來決定什麼時候執行完全回收。當成熟對象的數量達到上次完全收回後剩餘數量的兩倍時，Ruby 會清除所有的標記讓所有成熟的對象重新處於年輕狀態。

寫屏障

這個演算法的實現有一個重要的難題，很值得我們進行進一步的解釋。假設你的代碼創建了一個新的年輕的對象並同時使它被一個已存在的成熟對象引用。舉個例子，當你往一個存在了很長時間的數組中添加新值時就會出現這種情況。

我們看到新的年輕的對象在圖的左邊，而成熟的對象在右邊。左邊有5個新對象已經被用灰色標記為仍然活躍的對象，還有兩個用白色標記垃圾對象。但中間的那個新對象是什麼回事呢？它是白色的同時中間有個問號。這個新對象究竟是垃圾還是存活的？

當然，它是存活的，因為它被右邊的一個成熟對象所引用。但我們記得 Ruby 2.1 的標記和掃描處理是不包含成熟對象的（除了完全回收）。這意味著這個新對象會被錯誤的認為是垃圾並被回收，從而導致你的程序出現數據丟失！

Ruby 2.1 解決了這個問題，通過監控成熟對象來得知它們是否引用了一個新的年輕的對象。Ruby 2.1 使用了一種成為 寫屏障 的舊的垃圾回收技術來監控成熟對象的變化 —— 當你把一個對象引用另外一個對象時（無論是新建或者修改引用），寫屏障就會被觸發。這個屏障會檢查源對象是否成熟的，如果是則把它添加到一個特殊的列表。然後，Ruby 2.1 會把這些剛被修改的成熟對象投入到下一次標記和掃描處理中，防止新的活躍的對象被錯誤的刪除。

Ruby 2.1 對寫屏障實現實際是相當複雜的，主要是因為沒現成的 C 擴展。Koichi Sasada 和 Ruby 的核心團隊使用了一系列聰明的解決方案來解決了這個難題。想學習更多的這些技術細節，可以看 EuRuKo 2013 Koichi 那令人著迷的演講

第一眼看上去，Ruby 和 Python 的垃圾回收實現十分不同。Ruby 使用了 John McCarthy 原始的標記與掃描演算法，而 Python 使用的是引用計數。但當我們再靠近一點，我們能夠看到 Python 也利用了一些標記與掃描的原理來處理循環引用問題，而且 Ruby 和 Python 都通過相似的方式來使用分代垃圾回收。Python 使用了三個獨立的世代，而 Ruby 2.1 使用了兩個。

不需要為這些相似感到驚訝。兩個語言都是使用了幾十年前的計算機科學研究成果 —— 遠遠早於 Ruby 或 Python 被發明的時間。我發現令人著迷的是，當你深入了解不同的編程語言，你常常會發現它們都使用了相似的基本思路和演算法。現代編程語言很大程度上歸功於 John McCarthy 和他的同時代人在20世紀60年代和70年代所做的開創性的計算機科學研究。

英文原文：http://patshaughnessy.net/2013/10/30/generational-gc-in-python-and-ruby 譯者：天

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！