幾乎所有的高級編程語言都有自己的垃圾回識訓制，開發者不需要關注記憶體的申請與釋放，Python 也不例外，Python 官方團隊的文章 https://devguide.python.org/internals/garbage-collector 詳細介紹了 Python 中的垃圾回收演算法，本文是這篇文章的譯文，
摘要
CPython 中主要的垃圾回收演算法是參考計數，參考計數顧名思義就是統計每個物件有多少個參考，每個參考可能來自另外一個物件，或者一個全域（或靜態）C 變數，或者 C 語言函式中的區域變數，當一個變數的參考計數變成 0，那么這個物件就會被釋放，如果被釋放的物件包含對其他物件的參考，那么其他物件的參考計數就會相應地減 1，如果其他物件的參考計數在減 1 之后變成 0，這些物件也會級聯地被釋放掉，在 Python 代碼中可以通過 sys.getrefcount 函式獲取一個物件的參考計數（函式的回傳值會比實際的參考計數多 1，因為函式本身也包含一個對目標物件的參考），
>>> x = object()
>>> sys.getrefcount(x)
2
>>> y = x
>>> sys.getrefcount(x)
3
>>> del y
>>> sys.getrefcount(x)
2
參考計數最大的問題就是不能處理回圈參考，下面是一個回圈參考的例子：
>>> container = []
>>> container.append(container)
>>> sys.getrefcount(container)
3
>>> del container
在這個例子中，container 物件包含一個對自己的參考，所以即使我們移除了一個參考（變數 container）container 物件的參考計數也不會變成 0，因為 container 物件內部仍然有一個對自身的參考，因此如果僅僅通過簡單的參考計數，container 物件永遠不會被釋放，鑒于此，當物件不可達的時候（譯注：當代碼中沒有對實際物件的參考時），我們需要額外的機制來清除這些不可達物件間的回圈參考，這個額外的機制就是回圈垃圾收集器，通常簡稱為垃圾收集器（Garbage Collector，GC），雖然參考計數也是一種垃圾回收演算法，
記憶體布局和物件結構
一般的 Python 物件在 C 語言中的結構體表示如下
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| ob_refcnt | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
為了支持垃圾回收，在一般 Python 物件的記憶體布局前面加了一些額外的資訊
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| *_gc_next | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
| *_gc_prev | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ob_refcnt | \
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
通過這種方式，object 可以被看做一般的 Python 物件，當需要垃圾回收相關的資訊時可以通過簡單的型別轉換來訪問前面的欄位：((PyGC_Head *)(the_object)-1)，
在后面的章節 優化：通過復用欄位來節省記憶體 會介紹這兩個欄位通常用來串聯起被垃圾收集器管理的物件構成的雙向鏈表（ 每個鏈表對應垃圾回收中的一個分代，更多細節在優化：分代回收 中有介紹），但是在不需要鏈表結構的時候這兩個欄位會被用作其他功能來減少記憶體的使用，
使用雙向鏈表是因為其能高效地支持垃圾回收對鏈表的一些高頻操作，所有被垃圾收集器管理的物件被劃分成一些不相交的集合，每個集合都在各自的雙向鏈表中，不同的集合表示不同的分代，物件所處的分代反映了其在垃圾回收中存活了多久，每次垃圾回收的時候，每個分代中的物件會進一步劃分成可達物件和不可達物件，雙向鏈表的一些操作比如移動物件、添加物件、完全洗掉一個物件（垃圾收集器管理的物件一般情況下會在兩次垃圾回收之間通過參考計數系統回收）、合并鏈表等，都會在常量時間復雜度完成，并且雙向鏈表支持在遍歷的時候添加和洗掉物件，垃圾收集器在運行的時候這也是一個非常頻繁的操作，
為了支持物件的垃圾回收，Python 的 C 介面提供了一些 API 來分配、釋放、初始化、添加和移除被垃圾收集器維護的物件，這些 API 的詳情參見 https://docs.python.org/3/c-api/gcsupport.html，
除了上面的物件結構之外，對于支持垃圾回收的物件的型別物件必須要在 tp_flags 欄位中設定 Py_TPFLAGS_HAVE_GC 標記，并且實作 tp_traverse 句柄，另外這些型別物件還要實作 tp_clear 句柄，除非能夠證明僅僅通過該型別的物件不會形成回圈參考或者支持垃圾回收的物件是不可變型別，
回圈參考的識別
CPython 中識別回圈參考的演算法在 gc 模塊中實作，垃圾收集器只關注清除容器型別的物件（也就是那些能夠包含對其他物件的參考的物件），比如陣列、字典、串列、自定義類實體和擴展模塊中的類等等，雖然回圈參考并不常見， 但是 CPython 解釋器自身也會由于一些內部參考的存在形成回圈參考，下面是一些典型場景
- 例外物件 exception 會包含堆疊跟蹤物件 traceback，堆疊跟蹤物件包含堆疊幀的串列，這些堆疊幀最終又會包含例外物件，
- 模塊級別的函式會參考模塊的字典 dict（用于決議全域變數），模塊字典反過來又會包含模塊級別的函式，
- 類的實體物件會參考其所屬的類物件，類物件會參考其所在的模塊，模塊會包含模塊內的所有物件（可能還會包含其他的模塊）從而最侄訓參考到最初的類實體物件，
- 當要表示圖這類資料結構的時候，很容易產生對自身的參考，
如果想要正確釋放不可達的物件，第一步就是要識別出不可達物件，在識別回圈參考的函式中維護了兩個雙向鏈表：一個鏈表包含所有待掃描的物件，另一個鏈表包含暫時不可達的物件，
為了理解演算法的原理，我們看一下下面的示例，其中 A 參考了一個回圈鏈表，另外還有一個不可達的自我參考的物件：
>>> import gc
>>> class Link:
... def __init__(self, next_link=None):
... self.next_link = next_link
>>> link_3 = Link()
>>> link_2 = Link(link_3)
>>> link_1 = Link(link_2)
>>> link_3.next_link = link_1
>>> A = link_1
>>> del link_1, link_2, link_3
>>> link_4 = Link()
>>> link_4.next_link = link_4
>>> del link_4
# 回收不可達的 Link 物件 (和它的字典 __dict__)，
>>> gc.collect()
2
當垃圾收集器開始作業的時候，會將所有要掃描的容器物件放在第一個鏈表中，這樣做是為了將所有不可達物件移除，因為正常情況下大多數物件都是可達的，所以移除不可達物件會涉及更少的指標操作，因此更高效，
演算法開始的時候會為所有支持垃圾回收的物件另外初始化一個參考計數欄位（下圖中的 gc_ref），初始值設定為物件實際的參考計數，因為演算法在識別回圈參考的計算中會修改參考計數，通過使用一個另外的欄位 gc_ref 解釋器就不會修改物件真正的參考計數，
垃圾收集器會遍歷第一個串列中的所有容器物件，每遍歷一個物件都會將其所參考的所有的其他物件的 gc_ref 欄位減 1，為了找到容器物件所參考的其他物件需要呼叫容器類的 tp_traverse 方法（通過 C API 實作或者由超類繼承），在遍歷完之后，只有那些被外部變數參考的物件的 gc_ref 的值才會大于 0，
需要注意的是即使 gc_ref == 0 也不能說明物件就是不可達的，因為被外部變數參考的物件（gc_ref > 0）仍然可能參考它們，比如在我們的例子中，link_2 物件在第一次遍歷之后 gc_ref == 0，但是 link_1 物件仍然會參考 link_2，而 link_1 是從外部可達的，為了找到那些真正不可達的物件，垃圾收集器需要重新遍歷容器物件，這次遍歷的時候會將 gc_ref == 0 的物件標記為暫時不可達并且移動到暫時不可達的鏈表中，下圖描述了垃圾收集器在處理了 link_3 和 link_4 物件但是還沒處理 link_1 和 link_2 物件時的狀態，
垃圾收集器接下來會處理 link_1 物件，由于 gc_ref == 1，垃圾收集器不會對其做特殊處理因為知道其可達（并且已經在可達物件鏈表中），
當垃圾收集器遇到可達物件時（gc_ref > 0），會通過 tp_traverse 找到其所參考的其他物件，并且將這些物件移動到可達物件鏈表（它們最初所在的鏈表）的末尾，同時設定 gc_ref 欄位為 1，link_2 和 link_3 物件就會被這樣處理，因為它們都被 link_1 參考，在上圖所示狀態之后，垃圾收集器會檢查被 link_1 參考的物件從而知道 link_3 是可達的，所以將其移回到原來的鏈表中并且設定 gc_ref 欄位值為 1，那么垃圾收集器下次遇到 link_3 的時候就知道它是可達的，為了避免重復處理同一個物件，垃圾收集器在處理被可達物件參考的物件的時候會標記它們已經被訪問過（通過清除 PREV_MASK_COLLECTING 標記），
需要注意的是那些開始被標記為暫時性不可達后來又被移回到可達物件鏈表的物件，會再次被垃圾收集器訪問到，因為按照演算法邏輯現在被這些物件參考的其他物件也要被處理，第二次遍歷實際上是對這些物件間參考關系構成的圖的廣度優先搜索，在第二遍遍歷結束后，垃圾收集器就可以確定現在還留在暫時性不可達物件鏈表中的物件是真的不可達，因此可以被回收掉，
值得注意的是，整個演算法中沒有遞回操作，也不需要相對于物件數量、指標數量或參考鏈長度的線性記憶體空間，除了臨時的 C 變數占用 O(1) 的常量空間外，物件本身的欄位都已經包含了演算法需要的所有資料，
為什么選擇移動不可達的物件
因為大多數物件都是可達物件，因此移動不可達物件看起來很合理，但是真正的原因并非想象的那么簡單，
假設我們依次創建了 A、B 和 C 三個物件，那么它們在第一代（譯注：這里的第一代指的是分代回收）中的順序就是創建順序，如果 B 參考 A，C 參考 B，并且 C 有外部參考，那么在垃圾回收演算法的第一輪遍歷之后 A、B 和 C 的 gc_ref 值分別為 0、0 和 1，因為只有 C 是外部可達物件，
在演算法的第二輪遍歷中，會先訪問 A，因為 gc_ref 為 0 會被移動到暫時性不可達物件鏈表中，B 也一樣，當訪問到 C 的時候會將 B 移回到可達物件鏈表中，當再次訪問 B 的時候 A 也會被移回到可達物件鏈表中，
本可以不用移動，A 和 B 卻來回移動了兩次，為什么要這么做呢？如果演算法直接移動可達物件的話，那么只用將 A、B 和 C 分別移動一次即可，這么做的關鍵是在垃圾回收結束的時候這幾個物件在鏈表中的順序依次為 C、B 和 A，與它們最初的創建順序相反，在后續的垃圾回收中，它們不再需要做任何移動，因為大多數物件之間都沒有回圈參考，這樣做只會在第一次垃圾回收的時候開銷比較大，在后續的垃圾回收中能節省很多移動的開銷，
銷毀不可達物件
一旦垃圾收集器確定了最終的不可達物件串列，就開始銷毀這些物件，銷毀的大體程序如下
- 處理并且清除弱參考（如果有的話），如果要銷毀的不可達物件有弱參考的回呼，那么需要處理回呼函式，這個處理程序需要特別小心，因為一個小小的錯誤就可能讓狀態不一致的物件被復活或者被回呼函式所呼叫的 Python 函式參考，如果弱參考物件本身也是不可達的（弱參考和其參考的物件在不可達的回圈參考中），那么這個弱參考物件需要馬上被清理并且不用呼叫回呼函式，如果不馬上清理的話，那么在后來呼叫
tp_clear的時候會造成嚴重后果，當弱參考和其參考的物件都不可達的時候，那么兩者都會被銷毀，因此可以先銷毀弱參考，這個時候其參考的物件還存在，所以可以忽略弱參考的回呼， - 如果物件有老版本的終結器（
tp_del）需要將其移到gc.garbage串列中， - 呼叫不可達物件的終結器（
tp_finalize函式）并且標記這些物件已終結，避免物件被復活后或者在其他物件的終結器已經移除該物件的情況下重復呼叫tp_finalize， - 處理被復活的物件，如果有些不可達物件在上一步被復活，垃圾收集器需要重新計算出最終的不可達物件，
- 對于每個最終的不可達物件，呼叫
tp_clear來打破回圈參考使每個物件的參考計數都變成 0，從而觸發基于參考計數的銷毀邏輯，
優化：分代回收
為了避免每次垃圾回收的時候耗時太久，垃圾收集器使用了一個常用的優化：分代回收，分代回收有個前提假設，認為大多數物件的生命周期都很短，會在創建后很快就被回收，這個假設與現實中很多 Python 程式的情況一致，因為很多臨時物件會被很快地創建和銷毀，存活越久的物件越不容易因為不可達而被回收，
為了充分利用這一點，所有容器物件都會被分成三代中的某一代，每個新建的容器物件都處于第一代（generation 0），上面描述的垃圾回收演算法只在某一個具體的分代中進行，那些沒有被回收的物件會進入下一代（generation 1），這一代中的物件相對于上一代執行垃圾回收的次數會更少，如果物件在新一代中仍然沒有被回收就會移動到最后一代（generation 2），在最后一代中執行垃圾回收的次數是最少的，
垃圾收集器會記錄在上次垃圾回收之后新增物件與銷毀物件數量之差，也就是凈新增物件數量，如果超過了 threshold_0 垃圾收集器就會執行，最初的時候垃圾回收只在 generation 0 中執行，如果 generation 1 在上次執行垃圾回收之后， generation 0 中執行垃圾回收的次數超過了 threshold_1 那么就會再次在 generation 1 中執行垃圾回收，對于 generation 2 的處理稍微復雜點，在第三代中的垃圾回收 中單獨介紹，前面說的閾值 threshold_0 和 threshold_1 可以通過函式 gc.get_threshold 查看（譯注：原文這里描述有誤，我在 issue https://github.com/python/devguide/issues/1027 中提出并被作者采納）：
>>> import gc
>>> gc.get_threshold()
(700, 10, 10)
每個分代中的物件可以通過函式 gc.get_objects(generation=NUM) 查看，另外可以通過呼叫函式 gc.collect(generation=NUM) 指定在哪個分代中執行垃圾回收，
>>> import gc
>>> class MyObj:
... pass
...
# 為了更容易觀察年輕代中的物件需要將第一代和第二代中的物件都移動到第三代
>>> gc.collect()
0 # 譯注：不同版本執行的時候的結果不一樣
# 創建回圈參考
>>> x = MyObj()
>>> x.self = x
# x 最初在第一代中
>>> gc.get_objects(generation=0)
[..., <__main__.MyObj object at 0x7fbcc12a3400>, ...]
# 在第一代中執行垃圾回收之后，x 就移動到了第二代
>>> gc.collect(generation=0)
0
>>> gc.get_objects(generation=0)
[] # 譯注：在互動模式下，每次鍵入的代碼都會經過編譯再執行，所以輸出中還有編譯程序生成的一些被垃圾收集器管理的物件
>>> gc.get_objects(generation=1)
[..., <__main__.MyObj object at 0x7fbcc12a3400>, ...]
第三代中的垃圾回收
在上面提到的各種閾值的基礎之上，只有當比率 long_lived_pending / long_lived_total 的值高于一個給定值（硬編碼為 25%）的時候，才會在第三代中進行一次全量回收，因為盡管對于非全量的回收（比如創建很多被垃圾收集器管理的物件并且都放進一個串列中，那么垃圾回收的時間復雜度不是線性的，而是 O(N2)，（譯注：這里的時間復雜度不是上面說的一次垃圾回收的時間與分代中物件數量的關系，而是指在創建很多物件到串列中這種程式模式下，所有垃圾回收的總耗時與創建的物件數量的關系，詳情見 https://mail.python.org/pipermail/python-dev/2008-June/080579.html）），如果使用上面的比率，就會變成攤還之后的線性復雜度（這種做法可以總結為：盡管隨著創建的物件越來越多全量垃圾回識訓變得越來越慢，但是全量垃圾回收的次數也會變得越來越少），
優化：通過復用欄位來節省記憶體
為了節省記憶體，支持垃圾回收的物件中的用于鏈表的兩個指標也會被用作其他用途，這種常見的優化叫做胖指標或標記指標：在指標中存盤額外的資料，能夠這樣做也是利用了記憶體尋址的特性，大多數架構會將資料的記憶體同資料的大小對齊，通常是一個字或多個字對齊，對齊之后就會使得指標的最低幾位不會被使用，而這些低位就可以用作標記或存盤其他資訊 —— 通常作為位域（每一位都是一個獨立的標記）—— 只要程式在使用指標尋址前屏蔽掉這些位域即可，例如在 32 位架構上，一個字大小是 32 位 4 位元組，所以字對齊的地址都是 4 的倍數，也就是以 00 結尾，因此最低 2 位可以用作他用；類似的在 64 位結構上，一個字大小是 64 位 8 位元組，字對齊的地址以 000 結尾，最低 3 位可以用來保存其他資料，
CPython 的垃圾收集器的實作就使用了記憶體布局和物件結構 中描述的 PyGC_Head 結構體中的兩個胖指標：
_gc_prev欄位正常情況下用于指向雙向鏈表中的前一個元素，低 2 位會用來保存PREV_MASK_COLLECTING和_PyGC_PREV_MASK_FINALIZED標記，在沒有進行垃圾回收的時候只有表示物件是否被釋放的標記_PyGC_PREV_MASK_FINALIZED會被使用，在垃圾回收期間，_gc_prev會被臨時用來保存參考計數gc_ref，在此期間垃圾收集器維護的物件鏈表只能當做單鏈表使用，直到_gc_prev恢復原來的值，_gc_next欄位用于指向雙向鏈表中的下一個元素，垃圾回收演算法在檢測回圈參考時，它的最低位會用來保存表示物件是否暫時性不可達的標記NEXT_MASK_UNREACHABLE，垃圾回收演算法中使用雙向鏈表使得大多數操作都能在常量時間復雜度內完成，但是無法高效地判斷一個物件是在可達鏈表中還是在暫時性不可達鏈表中，由于有標記NEXT_MASK_UNREACHABLE的存在，當需要判斷物件在哪個鏈表中的時候只用檢查該標記即可，
注意事項
因為胖指標或標記指標保存了其他資料，所以不能直接用來尋址，必須在清除這些其他資料之后才能得到真正的地址，尤其需要注意那些直接操作鏈表的函式，因為這些函式經常會假設鏈表中的指標狀態一致，
優化：延遲管理容器物件
有些容器物件不會產生回圈參考，所以垃圾收集器沒必要管理它們，解除對這些物件的管理會提高垃圾收集器的性能，但是判斷一個物件是否可以解除管理也是有成本的，因此必須要權衡一下成本和由此給垃圾收集器帶來的收益，有兩個可能的時機可以解除對容器物件的管理：
- 容器物件創建的時候
- 垃圾回收的時候
大的原則是原子型別不需要被垃圾收集器管理，非原子型別（容器、用戶自定義物件等）需要，也有一些針對特定型別的優化避免垃圾收集器在垃圾回收時對一些簡單物件做不必要的檢查，下面是一些對內置型別延遲管理的例子：
- 只包含不可變物件（整數、字串或者只包含不可變物件的元組）的元組不需要被管理，解釋器會創建大量的元組，其中很多在垃圾回收之前就銷毀了，因此沒必要在創建時就對符合條件的元組解除管理，因此除了空元組之外的所有元組在創建時都會被垃圾收集器管理，直到垃圾回收的時候才會確定是否有存活的元組需要解除管理，如果一個元組中的所有元素都沒有被垃圾收集器管理，那么元組本身也可以解除管理，每個分代中的垃圾回收都會對元組做是否需要解除管理的檢查，因此一個元組可能在多次檢查之后才會被解除管理，
- 只包含不可變物件的字典也不需要被垃圾收集器管理，字典是在創建時解除管理的，如果另一個被管理的物件加入到字典中（無論是作為鍵還是值），那么垃圾收集器都會重新管理字典，另外，在全量垃圾回收（所有分代中）時，垃圾收集器也會檢查字典中的內容是否都沒有被管理，如果滿足條件也會對字典解除管理，
垃圾回收模塊提供了 Python 函式 is_tracked(obj) 回傳物件當前是否被垃圾收集器管理，當然后續垃圾回收的時候可能會改變管理狀態，
>>> gc.is_tracked(0)
False
>>> gc.is_tracked("a")
False
>>> gc.is_tracked([])
True
>>> gc.is_tracked({})
False
>>> gc.is_tracked({"a": 1})
False
>>> gc.is_tracked({"a": []})
True
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/542508.html
標籤：其他
上一篇：Python工具箱系列(二十三)