前言
一般面試python的時候談到垃圾回收機(jī)制桨嫁，我們的回答可能就是簡單的：引用計數(shù)、標(biāo)記清除和分代回收玻蝌。
本文就圍繞這三個機(jī)制來詳細(xì)解釋python是如何實現(xiàn)并處理不需要的內(nèi)存對象的蟹肘。
引用計數(shù)
Python垃圾回收主要以引用計數(shù)為主，分代回收為輔俯树。
引用計數(shù)法的原理是每個對象維護(hù)一個ob_refcnt帘腹，python中一切都是對象（包括對象自己，類型的類型是PyType_Type）所有對象都擁有一些相同內(nèi)容這些信息都在PyObject中定義许饿，PyObject是python對象機(jī)制的核心阳欲。
// object.h
typedef struct _object {
PyObject_HEAD
} PyObject;
* PyObject_HEAD defines the initial segment of every PyObject. */
#define PyObject_HEAD \
_PyObject_HEAD_EXTRA \
Py_ssize_t ob_refcnt; \
struct _typeobject *ob_type;
//----------------------------------------------------
#define _PyObject_HEAD_EXTRA \
struct _object *_ob_next; \
struct _object *_ob_prev;
// 雙向鏈表結(jié)構(gòu), 垃圾回收
從PyObject定義可以看到python的秘密都在PyObject_HEAD這個宏，所以實際PyObject對象機(jī)制核心十分簡單就是一個引用計數(shù)和一個類型信息的結(jié)構(gòu)體指針米辐。PyObject是每個對象必有的內(nèi)容胸完，其中ob_refcnt就是做為引用計數(shù)。當(dāng)一個對象有新的引用時翘贮，它的ob_refcnt就會增加赊窥，當(dāng)引用它的對象被刪除，它的ob_refcnt就會減少狸页。
需要注意的是锨能，類型對象是超越引用計數(shù)規(guī)則的，類型對象“跳出三界外芍耘，不在五行中”永遠(yuǎn)不會被析構(gòu)址遇。
//增加計數(shù)
#define Py_INCREF(op) ( \
_Py_INC_REFTOTAL _Py_REF_DEBUG_COMMA \
((PyObject*)(op))->ob_refcnt++)
//減少計數(shù)
#define _Py_DEC_REFTOTAL _Py_RefTotal--
#define _Py_REF_DEBUG_COMMA ,
#define Py_DECREF(op) \
do { \
if (_Py_DEC_REFTOTAL _Py_REF_DEBUG_COMMA \
--((PyObject*)(op))->ob_refcnt != 0) \
_Py_CHECK_REFCNT(op) \
else \
_Py_Dealloc((PyObject *)(op)); \
} while (0)
發(fā)現(xiàn)ob_refcnt變成0的時候, 該對象生命就結(jié)束了會調(diào)用_Py_Dealloc，調(diào)用各自類型的tp_dealloc斋竞。
PyAPI_FUNC(void) _Py_Dealloc(PyObject *);
#define _Py_REF_DEBUG_COMMA ,
#define _Py_Dealloc(op) ( \
_Py_INC_TPFREES(op) _Py_COUNT_ALLOCS_COMMA \
(*Py_TYPE(op)->tp_dealloc)((PyObject *)(op)))
#endif /* !Py_TRACE_REFS */
Python基本類型的tp_dealloc倔约，通常都會與各自的緩沖池機(jī)制相關(guān)，釋放會優(yōu)先放入緩沖池中(對應(yīng)的分配會優(yōu)先從緩沖池取)坝初。
這個內(nèi)存分配與回收同緩沖池機(jī)制相關(guān)浸剩。
當(dāng)無法放入緩沖池時, 會調(diào)用各自類型的tp_free來釋放自己占用的內(nèi)存以dict為例子：
PyTypeObject PyDict_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"dict",
sizeof(PyDictObject),
0,
(destructor)dict_dealloc, /* tp_dealloc */
....
}
static void
dict_dealloc(register PyDictObject *mp)
{
.....
// 如果滿足條件, 放入到緩沖池freelist中
if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
free_list[numfree++] = mp;
// 否則, 調(diào)用tp_free
else
Py_TYPE(mp)->tp_free((PyObject *)mp);
Py_TRASHCAN_SAFE_END(mp)
}
綜上，當(dāng)計數(shù)變?yōu)?code>0鳄袍，觸發(fā)內(nèi)存回收動作绢要，python底層調(diào)用_Py_Dealloc會調(diào)用對應(yīng)對象類型的tp_dealloc當(dāng)調(diào)用tp_free開始釋放內(nèi)存。
tp_free涉及函數(shù)PyObject_Del和PyObject_GC_Del拗小，并且自定義類以及容器類型(dict重罪、list、 tuple、 set等)使用的都是后者PyObject_GC_Del其他類型使用的是PyObject_Del如str剿配。
PyObject_Del 只會釋放內(nèi)存不會調(diào)用底層的析構(gòu)函數(shù)搅幅，因此自定義的類型和容器都會用PyObject_GC_Del。
void
PyObject_GC_Del(void *op)
{
PyGC_Head *g = AS_GC(op);
// Returns true if a given object is tracked
if (IS_TRACKED(op))
// 從跟蹤鏈表中移除
gc_list_remove(g);
if (generations[0].count > 0) {
generations[0].count--;
}
PyObject_FREE(g);
}
IS_TRACKED涉及到標(biāo)記清除的機(jī)制呼胚。generations涉及到了分代回收盏筐。PyObject_FREE則和Python底層內(nèi)存池機(jī)制相關(guān)。
標(biāo)記清除
Python中的循環(huán)引用總是發(fā)生在container對象之間砸讳，所謂containser對象即是內(nèi)部可持有對其他對象的引用，如list界牡， class簿寂， dict，instance等宿亡。
垃圾收集帶來的開銷依賴于container對象的數(shù)量常遂，必需跟蹤所創(chuàng)建的每一個container對象，并將這些對象組織到一個集合中挽荠。
標(biāo)記清除（Mark—Sweep）算法是一種基于追蹤回收（tracing GC）技術(shù)實現(xiàn)的垃圾回收算法克胳。
它分為兩個階段：
第一階段是標(biāo)記階段，GC會把所有的活動對象打上標(biāo)記
第二階段是把那些沒有標(biāo)記的對象非活動對象進(jìn)行回收圈匆。
那么GC又是如何判斷哪些是活動對象哪些是非活動對象的呢漠另？
對象之間通過引用（指針）連在一起，構(gòu)成一個有向圖跃赚，對象構(gòu)成這個有向圖的節(jié)點笆搓，而引用關(guān)系構(gòu)成這個有向圖的邊。從根對象（root object）出發(fā)纬傲，沿著有向邊遍歷對象满败，可達(dá)的（reachable）對象標(biāo)(unreachable)記為活動對象，不可達(dá)的對象就是要被清除的非活動對象叹括，根對象就是全局變量算墨、調(diào)用棧、寄存器汁雷。這種簡單粗暴的標(biāo)記清除算法也有明顯的缺點：清除非活動的對象前它必須順序掃描整個堆內(nèi)存净嘀，哪怕只剩下小部分活動對象也要掃描所有對象。
在上圖中摔竿，把小黑圈視為全局變量面粮，也就是把它作為root object。
從小黑圈出發(fā)继低，對象1可直達(dá)熬苍，那么它將被標(biāo)記。
對象2、3可間接到達(dá)也會被標(biāo)記柴底。
而4和5不可達(dá)婿脸，那么1、2柄驻、3就是活動對象狐树，4和5是非活動對象會被GC回收。
Python使用一個雙向鏈表將這些容器對象組織起來持續(xù)追蹤活躍的對象鸿脓，Python的內(nèi)部C代碼將其稱為零代(Generation Zero)抑钟。
上一節(jié)我們已經(jīng)知道任何一個python對象都含有一個PyObject_HEAD，除此之外另一部分就是對象自身的數(shù)據(jù)野哭。然而對于一個需要被跟蹤的container而言這還不夠在塔，因為這個對象必須被鏈入到雙向鏈表。想要成為一個可收集的對象必須加入額外的信息這個信息位于PyObject_HEAD之前叫做PyGC_Head它已經(jīng)在上文PyObject_GC_Del函數(shù)中出現(xiàn)過拨黔。
Modules/gcmodule.c
/* GC information is stored BEFORE the object structure. */
typedef union _gc_head {
struct {
// 建立鏈表需要的前后指針
union _gc_head *gc_next;
union _gc_head *gc_prev;
// 在初始化時會被初始化為 GC_UNTRACED
Py_ssize_t gc_refs;
} gc;
long double dummy; /* force worst-case alignment */
} PyGC_Head;
對于創(chuàng)建的可收集container對象蛔溃，其內(nèi)存分布可以從創(chuàng)建過程窺見一二。
python為container對象申請內(nèi)存時篱蝇，為PyGC_Head也申請了且其位置在container之前贺待。
PyObject *
_PyObject_GC_New(PyTypeObject *tp)
{
PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
if (op != NULL)
op = PyObject_INIT(op, tp);
return op;
}
=> _PyObject_GC_Malloc
#define _PyGC_REFS_UNTRACKED (-2)
#define GC_UNTRACKED _PyGC_REFS_UNTRACKED
PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
PyObject *op;
PyGC_Head *g;
if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
return PyErr_NoMemory();
// 為 對象本身+PyGC_Head申請內(nèi)存, 注意分配的size
g = (PyGC_Head *)PyObject_MALLOC(
sizeof(PyGC_Head) + basicsize);
if (g == NULL)
return PyErr_NoMemory();
// 初始化 GC_UNTRACED
g->gc.gc_refs = GC_UNTRACKED;
generations[0].count++; /* number of allocated GC objects */
// 如果大于閾值, 執(zhí)行分代回收
if (generations[0].count > generations[0].threshold &&
enabled &&
generations[0].threshold &&
!collecting &&
!PyErr_Occurred()) {
collecting = 1;
collect_generations();
collecting = 0;
}
op = FROM_GC(g);
return op;
}
所以對于PyListObject 、PyDictObject等對象內(nèi)存的分布推車應(yīng)該如下圖所示零截。
每次當(dāng)你創(chuàng)建一個對象或值的時候Python會將其加入零代鏈表麸塞。這種簡單粗暴的標(biāo)記清除算法也有明顯的缺點：清除非活動的對象前它必須順序掃描整個堆內(nèi)存，哪怕只剩下小部分活動對象也要掃描所有對象瞻润。
當(dāng)container實例化的時候喘垂，也就是new的時候就會將對象加入鏈表。以List為例：
PyObject *
PyList_New(Py_ssize_t size)
{
PyListObject *op;
op = PyObject_GC_New(PyListObject, &PyList_Type);
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}
// => _PyObject_GC_TRACK
// objimpl.h
// 加入到可收集對象鏈表中
#define _PyObject_GC_TRACK(o) do { \
PyGC_Head *g = _Py_AS_GC(o); \
if (g->gc.gc_refs != _PyGC_REFS_UNTRACKED) \
Py_FatalError("GC object already tracked"); \
g->gc.gc_refs = _PyGC_REFS_REACHABLE; \
g->gc.gc_next = _PyGC_generation0; \
g->gc.gc_prev = _PyGC_generation0->gc.gc_prev; \
g->gc.gc_prev->gc.gc_next = g; \
_PyGC_generation0->gc.gc_prev = g; \
} while (0);
現(xiàn)在绍撞，我們得到了一個鏈表正勒，python將收集限制在該鏈表，循環(huán)引用一定發(fā)生在鏈表的一群對象之間傻铣。在執(zhí)行_PyObject_GC_TRACK之后我們創(chuàng)建的container對象也就在垃圾回收機(jī)制的掌控之中了章贞。同時還有一個從鏈表移除對象的方法，該方法在對象被銷毀的時候調(diào)用非洲。
上文我們看到_PyObject_GC_New被執(zhí)行時調(diào)用_PyObject_GC_Malloc分配內(nèi)存鸭限，如果超過閾值會觸發(fā)GC，在collect_generations中會調(diào)用collect其中包含標(biāo)記清除邏輯两踏。
gcmodule.c
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
collect(int generation)
{
// 第1步: 將所有比當(dāng)前代年輕的代中的對象都放到當(dāng)前代的對象鏈表中
/* merge younger generations with one we are currently collecting */
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
}
// 第2步,update_refs
update_refs(young);
// 第3步,計算有效引用計數(shù)
subtract_refs(young);
// 第4步败京，垃圾標(biāo)記根據(jù)有效引用計數(shù)分為不等于0(root對象)和等于0(非root對象, 垃圾, 可回收)
gc_list_init(&unreachable);
move_unreachable(young, &unreachable);
// 第5步，將存活對象放入下一代
/* Move reachable objects to next generation. */
if (young != old) {
if (generation == NUM_GENERATIONS - 2) {
long_lived_pending += gc_list_size(young);
}
gc_list_merge(young, old);
}
else {
/* We only untrack dicts in full collections, to avoid quadratic
dict build-up. See issue #14775. */
untrack_dicts(young);
long_lived_pending = 0;
long_lived_total = gc_list_size(young);
}
// 第6步梦染，執(zhí)行回收釋放內(nèi)存
delete_garbage(&unreachable, old);
}
分代回收
分代機(jī)制是一種為了提高垃圾收集的效率以空間換時間的操作方式赡麦。從前面標(biāo)記清除這種垃圾收集機(jī)制來看朴皆，這種垃圾收集機(jī)制所帶來的額外操作實際上與系統(tǒng)中總的內(nèi)存塊的數(shù)量是相關(guān)的，當(dāng)須要回收的內(nèi)存塊越多時泛粹，垃圾檢測帶來的額外操作就越多遂铡，而垃圾回收帶來的額外操作就越少；反之晶姊，當(dāng)需回收的內(nèi)存塊越少時扒接，垃圾檢測就將比垃圾回收帶來更少的額外操作。
將系統(tǒng)中的所有內(nèi)存塊根據(jù)其存貨的時間劃分為不同的集合们衙，每個集合就成為一個代钾怔， 垃圾收集的頻率隨著代的存活時間的增大而減小（活得越長的對象蒙挑，就越不可能是垃圾蒂教，就應(yīng)該減少去收集的頻率）。存活時間通常是利用經(jīng)過了幾次垃圾回收動作來衡量脆荷，如果一個對象經(jīng)過的回收次數(shù)越多，顯然其存活時間就越長懊悯。
python為了支持分代機(jī)制定義了一個結(jié)構(gòu)體gc_generation蜓谋，對于每一個gc_generation，其內(nèi)部的count記錄了當(dāng)前這條可收集對象鏈中一共有多少個對象和一個閾值threshold代表對象鏈最多可以容納的對象數(shù)量炭分，超過閾值即可觸發(fā)回收桃焕。
gcmodule.c
struct gc_generation {
PyGC_Head head;
int threshold; /* collection threshold */ // 閾值
int count; /* count of allocations or collections of younger
generations */ // 實時個數(shù)
};
Python中，總共三個代捧毛。一個代就是一個鏈表观堂，所有屬于同代的內(nèi)存塊都鏈接在同一個鏈表中。
#define NUM_GENERATIONS 3
#define GEN_HEAD(n) (&generations[n].head)
// 三代都放到這個數(shù)組中
/* linked lists of container objects */
static struct gc_generation generations[NUM_GENERATIONS] = {
/* PyGC_Head, threshold, count */
{{{GEN_HEAD(0), GEN_HEAD(0), 0}}, 700, 0}, //700個container,超過立即觸發(fā)垃圾回收機(jī)制
{{{GEN_HEAD(1), GEN_HEAD(1), 0}}, 10, 0}, // 10個
{{{GEN_HEAD(2), GEN_HEAD(2), 0}}, 10, 0}, // 10個
};
PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);
上文_PyObject_GC_TRACK中有一個_PyGC_generation0的變量呀忧，這個就是python內(nèi)部維護(hù)的一個指針师痕，指向的正是第0代內(nèi)存塊集合。
第0代最多可以容納700個container對象一旦超過就會觸發(fā)回收機(jī)制而账，這點正是上文_PyObject_GC_Malloc表現(xiàn)出的行為胰坟。
雖然是由第0代觸發(fā)的回收，但是python會借此對所有的代內(nèi)存鏈表都進(jìn)行垃圾回收泞辐，當(dāng)然這只能是在某代的鏈表count滿足越界條件才進(jìn)行笔横。
static Py_ssize_t
collect_generations(void)
{
int i;
Py_ssize_t n = 0;
/* Find the oldest generation (highest numbered) where the count
* exceeds the threshold. Objects in the that generation and
* generations younger than it will be collected. */
// 從最老的一代, 開始回收
for (i = NUM_GENERATIONS-1; i >= 0; i--) { // 遍歷所有g(shù)eneration
if (generations[i].count > generations[i].threshold) { // 如果超過了閾值
/* Avoid quadratic performance degradation in number
of tracked objects. See comments at the beginning
of this file, and issue #4074.
*/
if (i == NUM_GENERATIONS - 1
&& long_lived_pending < long_lived_total / 4)
continue;
n = collect(i); // 執(zhí)行收集
break; // notice: break了
}
}
return n;
}
從collect_generations我們可以看到python找到滿足越界條件的最老一代進(jìn)行回收這一代對應(yīng)的內(nèi)存和所有年輕代對應(yīng)的內(nèi)存，但是源碼中找到最老一代并處理后直接就break咐吼，這個問題的關(guān)鍵就是collect函數(shù)及它接受的參數(shù)該函數(shù)是垃圾回收的關(guān)鍵實現(xiàn)吹缔。
上文collect中，首先將所有比當(dāng)前代年輕的代中的對象都放到當(dāng)前代的對象鏈表中一起處理锯茄，并遍歷對象鏈表計算得到有效引用計數(shù)厢塘。然后通過move_unreachable函數(shù)根據(jù)引用計數(shù)得到計數(shù)大于0的和等于0的對象并將它移動到unreachable鏈表，完成之后一條鏈表被切分成了2條，在unreachable鏈表中就是需要回收的目標(biāo)俗冻。如果可能并將當(dāng)前代中的reachable對象合并到更老的代礁叔。
