[[402065]]

本文轉(zhuǎn)載自微信公眾號「小菜學(xué)編程」，作者fasionchan。轉(zhuǎn)載本文請聯(lián)系小菜學(xué)編程公眾號。

Python 內(nèi)部采用 引用計數(shù)法 ，為每個對象維護(hù)引用次數(shù)，并據(jù)此回收不再需要的垃圾對象。由于引用計數(shù)法存在重大缺陷，循環(huán)引用時有內(nèi)存泄露風(fēng)險，因此 Python 還采用 標(biāo)記清除法 來回收存在循環(huán)引用的垃圾對象。此外，為了提高垃圾回收( GC )效率，Python 還引入了 分代回收機制 。

對象跟蹤

將程序內(nèi)部對象跟蹤起來，是實現(xiàn)垃圾回收的第一步。那么，是不是程序創(chuàng)建的所有對象都需要跟蹤呢?

一個對象是否需要跟蹤，取決于它會不會形成循環(huán)引用。按照引用特征，Python 對象可以分為兩類：

• 內(nèi)向型對象 ，例如 int 、float 、 str 等，這類對象不會引用其他對象，因此無法形成循環(huán)引用，無須跟蹤;
• 外向型對象 ，例如 tuple 、 list 、 dict 等容器對象，以及函數(shù)、類實例等復(fù)雜對象，這類對象一般都會引用其他對象，存在形成循環(huán)引用的風(fēng)險，因此是垃圾回收算法關(guān)注的重點;

這是一個典型的例子，橘紅色外向型對象存在循環(huán)引用的可能性，需要跟蹤;而綠色內(nèi)向型對象在引用關(guān)系圖中只能作為葉子節(jié)點存在，無法形成任何環(huán)狀，因此無需跟蹤：

Python 為外向型對象分配內(nèi)存時，調(diào)用位于 Modules/gcmodule.c 源文件的 _PyObject_GC_Alloc 函數(shù)。該函數(shù)在對象頭部之前預(yù)留了一些內(nèi)存空間，以便垃圾回收模塊用 鏈表 將它們跟蹤起來。預(yù)留的內(nèi)存空間是一個 _gc_head 結(jié)構(gòu)體，它定義于 Include/objimpl.h 頭文件：

typedef union _gc_head { 
    struct { 
        union _gc_head *gc_next; 
        union _gc_head *gc_prev; 
        Py_ssize_t gc_refs; 
    } gc; 
    long double dummy;  /* force worst-case alignment */ 
    // malloc returns memory block aligned for any built-in types and 
    // long double is the largest standard C type. 
    // On amd64 linux, long double requires 16 byte alignment. 
    // See bpo-27987 for more discussion. 
} PyGC_Head; 

• gc_next ，鏈表后向指針，指向后一個被跟蹤的對象;
• gc_prev ，鏈表前向指針，指向前一個被跟蹤的對象;
• gc_refs ，對象引用計數(shù)副本，在標(biāo)記清除算法中使用;
• dummy ，內(nèi)存對齊用，以 64 位系統(tǒng)為例，確保 _gc_head 結(jié)構(gòu)體大小是 16 字節(jié)的整數(shù)倍，結(jié)構(gòu)體地址以 16 字節(jié)為單位對齊;

以 list 對象為例，_PyObject_GC_Alloc 函數(shù)在 PyListObject 結(jié)構(gòu)體基礎(chǔ)上加上 _gc_head 結(jié)構(gòu)體來申請內(nèi)存，但只返回 PyListObject 的地址作為對象地址，而不是整塊內(nèi)存的首地址：

就這樣，借助 gc_next 和 gc_prev 指針，Python 將需要跟蹤的對象一個接一個組織成 雙向鏈表 ：

這個鏈表也被稱為 可收集 ( collectable )對象鏈表，Python 將從這個鏈表中收集并回收垃圾對象。

分代回收機制

Python 程序啟動后，內(nèi)部可能會創(chuàng)建大量對象。如果每次執(zhí)行標(biāo)記清除法時，都需要遍歷所有對象，多半會影響程序性能。為此，Python 引入分代回收機制——將對象分為若干“代”( generation )，每次只處理某個代中的對象，因此 GC 卡頓時間更短。

那么，按什么標(biāo)準(zhǔn)劃分對象呢?是否隨機將一個對象劃分到某個代即可呢?答案是否定的。實際上，對象分代里頭也是有不少學(xué)問的，好的劃分標(biāo)準(zhǔn)可顯著提升垃圾回收的效率。

考察對象的生命周期，可以發(fā)現(xiàn)一個顯著特征：一個對象存活的時間越長，它下一刻被釋放的概率就越低。我們應(yīng)該也有這樣的親身體會：經(jīng)常在程序中創(chuàng)建一些臨時對象，用完即刻釋放;而定義為全局變量的對象則極少釋放。

因此，根據(jù)對象存活時間，對它們進(jìn)行劃分就是一個不錯的選擇。對象存活時間越長，它們被釋放的概率越低，可以適當(dāng)降低回收頻率;相反，對象存活時間越短，它們被釋放的概率越高，可以適當(dāng)提高回收頻率。

Python 內(nèi)部根據(jù)對象存活時間，將對象分為 3 代(見 Include/internal/mem.h )：

#define NUM_GENERATIONS 3 

每個代都由一個 gc_generation 結(jié)構(gòu)體來維護(hù)，它同樣定義于 Include/internal/mem.h 頭文件：

struct gc_generation { 
    PyGC_Head head; 
    int threshold; /* collection threshold */ 
    int count; /* count of allocations or collections of younger 
                  generations */ 
}; 

• head ，可收集對象鏈表頭部，代中的對象通過該鏈表維護(hù);
• threshold ，僅當(dāng) count 超過本閥值時，Python 垃圾回收操作才會掃描本代對象;
• count ，計數(shù)器，不同代統(tǒng)計項目不一樣;

Python 虛擬機運行時狀態(tài)由 Include/internal/pystate.h 中的 pyruntimestate 結(jié)構(gòu)體表示，它內(nèi)部有一個 _gc_runtime_state ( Include/internal/mem.h )結(jié)構(gòu)體，保存 GC 狀態(tài)信息，包括 3 個對象代。這 3 個代，在 GC 模塊( Modules/gcmodule.c ) _PyGC_Initialize 函數(shù)中初始化：

struct gc_generation generations[NUM_GENERATIONS] = { 
    /* PyGC_Head,                                 threshold,      count */ 
    {{{_GEN_HEAD(0), _GEN_HEAD(0), 0}},           700,            0}, 
    {{{_GEN_HEAD(1), _GEN_HEAD(1), 0}},           10,             0}, 
    {{{_GEN_HEAD(2), _GEN_HEAD(2), 0}},           10,             0}, 
}; 

為方便討論，我們將這 3 個代分別稱為：初生代、中生代 以及 老生代。當(dāng)這 3 個代初始化完畢后，對應(yīng)的 gc_generation 數(shù)組大概是這樣的：

每個 gc_generation 結(jié)構(gòu)體鏈表頭節(jié)點都指向自己，換句話說每個可收集對象鏈表一開始都是空的;計數(shù)器字段 count 都被初始化為 0 ;而閥值字段 threshold 則有各自的策略。這些策略如何理解呢?

Python 調(diào)用 _PyObject_GC_Alloc 為需要跟蹤的對象分配內(nèi)存時，該函數(shù)將初生代 count 計數(shù)器加一，隨后對象將接入初生代對象鏈表;當(dāng) Python 調(diào)用 PyObject_GC_Del 釋放垃圾對象內(nèi)存時，該函數(shù)將初生代 count 計數(shù)器減一;_PyObject_GC_Alloc 自增 count 后如果超過閥值( 700 )，將調(diào)用 collect_generations 執(zhí)行一次垃圾回收( GC )。

collect_generations 函數(shù)從老生代開始，逐個遍歷每個生代，找出需要執(zhí)行回收操作( count>threshold )的最老生代。隨后調(diào)用 collect_with_callback 函數(shù)開始回收該生代，而該函數(shù)最終調(diào)用 collect 函數(shù)。

collect 函數(shù)處理某個生代時，先將比它年輕的生代計數(shù)器 count 重置為 0 ;然后將它們的對象鏈表移除，與自己的拼接在一起后執(zhí)行 GC 算法(本文后半部分介紹);最后，將下一個生代計數(shù)器加一。

• 系統(tǒng)每新增 701 個需要 GC 的對象，Python 就執(zhí)行一次 GC 操作;
• 每次 GC 操作需要處理的生代可能是不同的，由 count 和 threshold 共同決定;
• 某個生代需要執(zhí)行 GC ( count>hreshold )，在它前面的所有年輕生代也同時執(zhí)行 GC ;
• 對多個代執(zhí)行 GC ，Python 將它們的對象鏈表拼接在一起，一次性處理;
• GC 執(zhí)行完畢后，count 清零，而后一個生代 count 加一;

下面是一個簡單的例子：初生代觸發(fā) GC 操作，Python 執(zhí)行 collect_generations 函數(shù)。它找出了達(dá)到閥值的最老生代是中生代，因此調(diào)用 collection_with_callback(1) ，1 是中生代在數(shù)組中的下標(biāo)。

collection_with_callback(1) 最終執(zhí)調(diào)用 collect(1) ，它先將后一個生代計數(shù)器加一;然后將本生代以及前面所有年輕生代計數(shù)器重置為零;最后調(diào)用 gc_list_merge 將這幾個可回收對象鏈表合并在一起：

最后，collect 函數(shù)執(zhí)行標(biāo)記清除算法，對合并后的鏈表進(jìn)行垃圾回收，具體細(xì)節(jié)在本文后半部分展開介紹。

這就是分代回收機制的全部秘密，它看似復(fù)雜，但只需略加總結(jié)就可以得到幾條直白的策略：

• 每新增 701 個需要 GC 的對象，觸發(fā)一次新生代 GC ;
• 每執(zhí)行 11 次新生代 GC ，觸發(fā)一次中生代 GC ;
• 每執(zhí)行 11 次中生代 GC ，觸發(fā)一次老生代 GC (老生代 GC 還受其他策略影響，頻率更低);
• 執(zhí)行某個生代 GC 前，年輕生代對象鏈表也移入該代，一起 GC ;
• 一個對象創(chuàng)建后，隨著時間推移將被逐步移入老生代，回收頻率逐漸降低;

由于篇幅關(guān)系，分代回收部分代碼無法逐行解釋，請對照圖示閱讀相關(guān)重點函數(shù)，應(yīng)該不難理解。

現(xiàn)在，我們對 Python 垃圾回收機制有了框架上的把握，但對檢測垃圾對象的方法還知之甚少。垃圾對象識別是垃圾回收工作的重中之重，Python 是如何解決這一關(guān)鍵問題的呢?