Python 之垃圾回收机制

Python 作为一门解释型语言，以代码简洁易懂著称。我们可以直接对名称赋值，而不必声明类型。名称类型的确定、内存空间的分配与释放都是由 Python 解释器在运行时进行的。Python 这一自动管理内存功能极大地减小了程序员负担。

Python 采用的是 引用计数 机制为主，标记-清除 和 分代收集 两种机制为辅的策略。

大管家 refchain

在 Python 的 C 源码中有一个名为 refchain 的环状双向链表，这个链表就比较厉害了，因为 Python 程序中一旦创建对象都会把这个对象添加到 refchain 链表中。也就是说他保存着所有的对象。例如：

age = 18
hobby = "python"

引用计数(Reference Counting)

Python 默认采用的垃圾收集机制是 引用计数法，该算法最早由 George E. Collins 在 1960 的时候首次提出，直到今天，该算法依然被很多编程语言使用。

原理：每个对象维护一个 ob_refcnt 字段，用来记录该对象当前被引用的次数，每当新的引用指向该对象时，它的引用计数 ob_refcnt 加1，每当该对象的引用失效时计数 ob_refcnt 减1，一旦对象的引用计数为 0，该对象立即被回收，对象占用的内存空间将被释放。

Python 中一切皆对象，也就是说，在 Python 中你用到的一切变量，本质上都是类对象。实际上每一个对象的核心就是一个结构体 PyObject，它的内部有一个引用计数器 ob_refcnt，程序在运行的过程中会实时的更新 ob_refcnt 的值，来反映引用当前对象的名称数量。当某对象的引用计数值为 0,说明这个对象变成了垃圾，那么它会被回收掉，它所用的内存也会被立即释放掉。

typedef struct _object {  
    int ob_refcnt;//引用计数  
    struct _typeobject *ob_type;  
} PyObject;

当发生以下四种情况的时候，该对象的 引用计数器+1

• 对象被创建 a=14
• 对象被引用 b=a
• 对象被作为参数,传到函数中 func(a)
• 对象作为一个元素，存储在容器中 List={a, "a", "b", 2}

与上述情况相对应，当发生以下四种情况时，该对象的 引用计数器-1

• 当该对象的别名被显式销毁时 del a
• 当该对象的引别名被赋予新的对象 a=26
• 一个对象离开它的作用域，例如 func 函数执行完毕时，函数里面的局部变量的引用计数器就会减一（但是全局变量不会）
• 将该元素从容器中删除时，或者容器被销毁时。

当指向该对象内存的引用计数器为 0 的时候，该对象内存将会被 Python 虚拟机销毁。可以通过 sys 模块的 getrefcount() 函数来获得对象的引用计数。

引用计数法优点：

• 高效、实现逻辑简单、具备实时性，一旦一个对象的引用计数归零，内存就直接释放了。不用像其他机制等到特定时机。
• 将垃圾回收随机分配到运行的阶段，处理回收内存的时间分摊到了平时，正常程序的运行比较平稳。

引用计数也存在着一些缺点：

• 逻辑简单，但实现有些麻烦。每个对象需要分配单独的空间来统计引用计数，这无形中加大的空间的负担，并且需要对引用计数进行维护，在维护的时候很容易会出错。
• 在一些场景下，可能会比较慢。正常来说垃圾回收会比较平稳运行，但是当需要释放一个大的对象时，比如字典，需要对引用的所有对象循环嵌套调用，从而可能会花费比较长的时间。
• 循环引用。这将是引用计数的致命伤，引用计数对此是无解的，因此必须要使用其它的垃圾回收算法对其进行补充。
  也就是说，Python 的垃圾回收机制，很大一部分是为了处理可能产生的循环引用，是对引用计数的补充。

循环引用

引用计数 会产生循环引用，比如有两个对象 a 和 b，其中 a 引用了 b，b 引用了 a，这样 a 和 b 的引用计数都为 1，并且永远都不会为 0，这就意味着这两个对象永远都不会被回收了，这就是循环引用，a 与 b 形成了一个引用循环，示例如下 :

a = [1, 2]      # 计数为 1  
b = [2, 3]      # 计数为 1  
a.append(b)     # 计数为 2  
b.append(a)     # 计数为 2  
del a           # 计数为 1  
del b           # 计数为 1

除了上述两个对象互相引用之外，还可以引用自身：

list3 = [1,2,3]  
list3.append(list3)

循环引用导致变量计数永不为 0，造成引用计数无法将其删除。因此必须要使用其它的垃圾回收算法对其进行补充。

标记清除(Mark and Sweep)

Python 采用了 标记-清除 算法，解决容器对象可能产生的循环引用问题。(注意，只有容器对象才会产生循环引用的情况，比如列表、字典、用户自定义类的对象、元组等。而像数字，字符串这类简单类型不会出现循环引用。作为一种优化策略，对于只包含简单类型的元组也不在标记清除算法的考虑之列)

跟其名称一样，该算法在进行垃圾回收时分成了两步，分别是：

• 标记阶段：遍历所有的对象，如果是可达的（reachable），也就是还有对象引用它，那么就标记该对象为可达；
• 清除阶段：再次遍历对象，如果发现某个对象没有标记为可达，则就将其回收。

优点：

• 可以解决循环引用的问题，并且在整个算法执行的过程中没有额外的开销。

缺点：

• 当执行标记清除时正常的程序将会被阻塞。另外一个缺点在于，标记-清除 算法在执行很多次数后，程序的堆空间会产生一些小的内存碎片。

那怎么判断对象是否为可达呢？有两种思路

按照对象引用关系构建有向图（Java 使用）

对象之间都会通过引用（指针）连在一起，这样就构成了一个有向图，对象是这个有向图的节点，而引用关系是这个有向图的边。从 root object 出发，沿着有向边遍历对象，可达的（reachable）对象标记为活动对象，不可达（unreachable）的对象就是要被清除的非活动对象。所谓 root object，就是一些全局变量、调用栈、寄存器，这些对象是不可被删除的。

我们把小黑圈视为 root object，从小黑圈出发，对象 1 可达，那么它将被标记，对象 2、3可间接可达也会被标记，而 4 和 5 不可达，那么 1、2、3 就是活动对象，4 和 5 是非活动对象会被 GC 回收。

创建特殊链表专门用于保存 列表、元组、字典、集合、自定义类等对象，之后再去检查这个链表中的对象是否存在循环引用，如果存在则让双方的引用计数器均-1。(Python 使用)

如下所示，在 标记清除 算法中，为了追踪容器对象，需要每个容器对象维护两个额外的指针，用来将容器对象组成一个双端链表，指针分别指向前后两个容器对象，方便插入和删除操作。

Python 解释器(Cpython)维护了两个这样的双端链表，一个链表存放着需要被扫描的容器对象，另一个链表存放着临时不可达对象。这两个链表分别被命名为 Object to Scan 和 Unreachable。

以图为例：link1,link2,link3 组成了一个引用环，同时 link1 还被一个变量 A (其实这里称为名称A更好)引用。link4 自引用，也构成了一个引用环。

从图中我们还可以看到，每一个节点除了有一个记录当前引用计数的变量 ref_count 还有一个 gc_ref 变量，这个 gc_ref 是 ref_count 的一个副本，所以初始值为 ref_count 的大小。

1. gc 启动的时候，会逐个遍历 Object to Scan 链表中的容器对象，并且将当前对象 所引用的所有对象 的 gc_ref 减一。(扫描到 link1 的时候，由于 link1 引用了 link2，所以会将 link2 的 gc_ref 减一，接着扫描 link2，由于 link2 引用了 link3，所以将 link3 的 gc_ref 减一……)。
   像这样将 Object to Scan 链表中的所有对象考察一遍之后，两个链表中的对象的 ref_count 和 gc_ref 的情况如下图所示。这一步操作就相当于解除了循环引用对引用计数的影响。
   

2. 接着，gc 会再次扫描所有的容器对象，如果对象的 gc_ref 值为 0，那么这个对象就被标记为 GC_TENTATIVELY_UNREACHABLE，并且被移至 Unreachable 链表中。如下图中的 link3、link4。
   

3. 如果对象的 gc_ref 不为0，那么这个对象就会被标记为 GC_REACHABLE。同时当 gc 发现有一个节点是可达的，那么他会递归式的将从该节点出发可以到达的所有节点标记为 GC_REACHABLE，如下图中 link2 和 link3。
   

4. 除了将所有可达节点标记为 GC_REACHABLE 之外，如果该节点当前在 Unreachable 链表中的话，还需要将其移回到 Object to Scan 链表中，下图就是 link3 移回之后的情形。
   

5. 第二次遍历的所有对象都遍历完成之后，存在于 Unreachable 链表中的对象就是真正需要被释放的对象。如上图所示，此时link4 存在于 Unreachable 链表中，gc 随即释放之。

上面描述的垃圾回收的阶段，会暂停整个应用程序，等待 标记清除 结束后才会恢复应用程序的运行。

分代回收(Generational garbage collector)

因为 标记清除 每次运行需要暂停程序，作者不希望它被调用太频繁所以引入 分代回收。

分代回收 技术是上个世纪 80 年代初发展起来的一种垃圾回收机制，也是 Java 垃圾回收的核心算法。分代回收是基于这样的一个统计事实，对于程序，存在一定比例的内存块的生存周期比较短；而剩下的内存块，生存周期会比较长，甚至会从程序开始一直持续到程序结束。

生存期较短对象的比例通常在 80%～90% 之间。因此，简单地认为：对象存在时间越长，越可能不是垃圾，应该越少去收集。这样在执行 标记-清除 算法时可以有效减小遍历的对象数，从而提高垃圾回收的速度，是一种以空间换时间的方法策略。

分代回收原理：对标记清除中的链表进行优化，将那些可能存在循引用的对象拆分到3个链表，链表称为：0/1/2三代。所有的新建对象都是 0 代对象。每代都可以存储对象和阈值，当达到阈值时，就会对相应的链表中的每个对象做一次扫描，除循环引用各自减 1并且销毁引用计数器为 0 的对象，依然存活，就被归入下一代对象。

那么，按什么标准划分对象呢?是否随机将一个对象划分到某个代即可呢?答案是否定的。实际上，对象分代里头也是有不少学问的，好的划分标准可显著提升垃圾回收的效率。

Python 内部根据对象存活时间，将对象分为 3 代，每个代都由一个 gc_generation 结构体来维护（定义于 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，可收集对象链表头部，代中的对象通过该链表维护
• threshold，仅当 count 超过本阀值时，Python 垃圾回收操作才会扫描本代对象
• count，计数器，不同代统计项目不一样

Python 虚拟机运行时状态由 Include/internal/pystate.h 中的 pyruntimestate 结构体表示，它内部有一个 _gc_runtime_state(Include/internal/mem.h) 结构体，保存 GC 状态信息，包括 3 个对象代。这 3 个代，在 GC 模块(Modules/gcmodule.c)_PyGC_Initialize 函数中初始化：

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

特别注意：0 代和 1、2 代的 threshold 和 count 表示的意义不同。

• 0代，count表示0代链表中对象的数量，threshold表示0代链表对象个数阈值，超过则执行一次0代扫描检查。
• 1代，count表示0代链表扫描的次数，threshold表示0代链表扫描的次数阈值，超过则执行一次1代扫描检查。
• 2代，count表示1代链表扫描的次数，threshold表示1代链表扫描的次数阈值，超过则执行一2代扫描检查。

为方便讨论，我们将这 3 个代分别称为：初生代、中生代 以及 老生代。当这 3 个代初始化完毕后，对应的 gc_generation 数组大概是这样的：

每个 gc_generation 结构体链表头节点都指向自己，换句话说每个可收集对象链表一开始都是空的，计数器字段 count 都被初始化为 0，而阀值字段 threshold 则有各自的策略。这些策略如何理解呢?

• Python 调用 _PyObject_GC_Alloc 为需要跟踪的对象分配内存时，该函数将初生代 count 计数器加1，随后对象将接入初生代对象链表，当 Python 调用 PyObject_GC_Del 释放垃圾对象内存时，该函数将初生代 count 计数器,1，_PyObject_GC_Alloc 自增 count 后如果超过阀值(700)，将调用 collect_generations 执行一次垃圾回收( GC )。

• collect_generations 函数从老生代开始，逐个遍历每个生代，找出需要执行回收操作(count>threshold)的最老生代。随后调用 collect_with_callback 函数开始回收该生代，而该函数最终调用 collect 函数。

• collect 函数处理某个生代时，先将比它年轻的生代计数器 count 重置为 0，然后将它们的对象链表移除，与自己的拼接在一起后执行 GC 算法，最后将下一个生代计数器加1。

于是：

• 系统每新增 701 个需要 GC 的对象，Python 就执行一次 GC 操作

• 每次 GC 操作需要处理的生代可能是不同的，由 count 和 threshold 共同决定

• 某个生代需要执行 GC(count>hreshold)，在它前面的所有年轻生代也同时执行 GC

• 对多个代执行 GC，Python 将它们的对象链表拼接在一起，一次性处理

• GC 执行完毕后，count 清零，而后一个生代 count 加 1

下面是一个简单的例子：

1. 初生代触发 GC 操作，Python 执行 collect_generations 函数。它找出了达到阀值的最老生代是中生代，因此调用 collection_with_callback(1)，1 是中生代在数组中的下标。
   

2. collection_with_callback(1) 最终执调用 collect(1) ，它先将后一个生代计数器加一;然后将本生代以及前面所有年轻生代计数器重置为零;最后调用 gc_list_merge 将这几个可回收对象链表合并在一起：
   

3. 最后，collect 函数执行标记清除算法，对合并后的链表进行垃圾回收。
   

这就是分代回收机制的全部秘密，它看似复杂，但只需略加总结就可以得到几条直白的策略：

• 每新增 701 个需要 GC 的对象，触发一次新生代 GC
• 每执行 11 次新生代 GC ，触发一次中生代 GC
• 每执行 11 次中生代 GC ，触发一次老生代 GC (老生代 GC 还受其他策略影响，频率更低)
• 执行某个生代 GC 前，年轻生代对象链表也移入该代，一起 GC
• 一个对象创建后，随着时间推移将被逐步移入老生代，回收频率逐渐降低

情景模拟

根据 C 语言底层并结合图来讲解内存管理和垃圾回收的详细过程。

第一步：当创建对象 age=19 时，会将对象添加到 refchain 链表中。

第二步：当创建对象 num_list = [11,22] 时，会将列表对象添加到 refchain 和 generations 0 代中。

第三步：新创建对象使 generations 0 代链表上的对象数量大于阈值 700 时，要对链表上的对象进行扫描检查。

当 0 代大于阈值后，底层不是直接扫描 0 代，而是先判断 2、1 是否也超过了阈值。

• 如果 2、1 代未达到阈值，则扫描 0 代，并让 1 代的 count+1 。
• 如果 2 代已达到阈值，则将 2、1、0 三个链表拼接起来进行全扫描，并将 2、1、0 代的 count 重置为0.
• 如果 1 代已达到阈值，则将 1、0 两个链表拼接起来进行扫描，并将所有 1、0 代的count重置为0，并让 2 代的 count+1

对拼接起来的链表在进行扫描时，主要就是剔除循环引用和销毁垃圾，详细过程为：

• 扫描链表，把每个对象的引用计数器拷贝一份并保存到 gc_refs 中，保护原引用计数器。
• 再次扫描链表中的每个对象，并检查是否存在循环引用，如果存在则让各自的 gc_refs 减 1。
• 再次扫描链表，将 gc_refs 为 0 的对象移动到 unreachable 链表中；不为0的对象直接升级到下一代链表中。
• 处理 unreachable 链表中的对象的 析构函数 和 弱引用，不能被销毁的对象升级到下一代链表，能销毁的保留在此链表。
  • 析构函数，指的就是那些定义了 __del__ 方法的对象，需要执行之后再进行销毁处理。
  • 弱引用，
• 最后将 unreachable 中的每个对象销毁并在 refchain 链表中移除（不考虑缓存机制）。

至此，垃圾回收的过程结束。

缓存机制

从上文大家可以了解到当对象的引用计数器为0时，就会被销毁并释放内存。而实际上他不是这么的简单粗暴，因为反复的创建和销毁会使程序的执行效率变低。Python中引入了“缓存机制”机制。

例如：引用计数器为0时，不会真正销毁对象，而是将他放到一个名为 free_list 的链表中，之后会再创建对象时不会在重新开辟内存，而是在 free_list 中将之前的对象来并重置内部的值来使用。

• float类型，维护的 free_list 链表最多可缓存100个float对象。

  v1 = 3.14       # 开辟内存来存储float对象，并将对象添加到refchain链表。
  print(id(v1))   # 内存地址：2023194562768
  del v1          # 引用计数器-1，如果为0则在rechain链表中移除，不销毁对象，而是将对象添加到float的free_list.
  v2 = 3.14       # 优先去free_list中获取对象
  print(id(v2))   # 内存地址：2023194562768
   
  # 注意：引用计数器为0时，会先判断free_list中缓存个数是否满了，未满则将对象缓存，已满则直接将对象销毁。

• int类型，不是基于 free_list，而是维护一个 small_ints 链表保存常见数据（小数据池），小数据池范围：-5 <= value < 257。即：重复使用这个范围的整数时，不会重新开辟内存。

  v1 = 38         # 去小数据池 small_ints 中获取38整数对象，将对象添加到 refchain 并让引用计数器+1。
  print( id(v1))  # 内存地址：4514343712
  v2 = 38         # 去小数据池small_ints中获取38整数对象，将refchain中的对象的引用计数器+1。
  print( id(v2) ) # 内存地址：4514343712
   
  # 注意：在解释器启动时候-5~256就已经被加入到small_ints链表中且引用计数器初始化为1，代码中使用的值时直接去small_ints中拿来用并将引用计数器+1即可。另外，small_ints中的数据引用计数器永远不会为0（初始化时就设置为1了），所以也不会被销毁。

• str类型，维护 unicode_latin1[256] 链表，内部将所有的 ascii字符 缓存起来，以后使用时就不再反复创建。

  v1 = "A"
  print( id(v1) ) # 输出：4517720496
  del v1
  v2 = "A"
  print( id(v1) ) # 输出：4517720496
   
  # 除此之外，Python 内部还对字符串做了驻留机制，针对那么只含有字母、数字、下划线的字符串（见源码Objects/codeobject.c），如果内存中已存在则不会重新在创建而是使用原来的地址里（不会像free_list那样一直在内存存活，只有内存中有才能被重复利用）。
  v1 = "abcd"
  v2 = "abcd"
  print(id(v1) == id(v2)) # 输出：True

• list类型，维护的 free_list 数组最多可缓存80个list对象。

  v1 = [11,22,33]
  print(id(v1)) # 输出：4517628816
  del v1
  v2 = ["sdf","sdfs"]
  print(id(v2)) # 输出：4517628816

• tuple类型，维护一个 free_list 数组且数组容量20，数组中元素可以是链表且每个链表最多可以容纳2000个元组对象。元组的 free_list 数组在存储数据时，是按照元组可以容纳的个数为索引找到 free_list 数组中对应的链表，并添加到链表中。

  v1 = (1,2)
  print(id(v1))
  del v1      # 因元组的数量为2，所以会把这个对象缓存到free_list[2]的链表中。
  v2 = ("鹏","Jone") # 不会重新开辟内存，而是去free_list[2]对应的链表中拿到一个对象来使用。
  print(id(v2))

Python 中的 gc 模块

官网:gc—垃圾回收器接口

gc 模块是我们在 Python 中进行内存管理的接口，一般情况 Python 程序员都不用关心自己程序的内存管理问题，但是有的时候，比如发现自己程序存在内存泄露，就可能需要用到 gc 模块的接口来排查问题。

有的 Python 系统会关闭自动垃圾回收，程序自己判断回收的时机，据说 instagram 的系统就是这样做的，整体运行效率提高了 10%。

常用函数：

• set_debug(flags)：设置 gc 的 debug 日志，一般设置为 gc.DEBUG_LEAK 可以看到内存泄漏的对象。
• collect([generation])：执行垃圾回收。会将那些有循环引用的对象给回收了。这个函数可以传递参数，0代表只回收第0代的的垃圾对象、1代表回收第0代和第1代的对象，2代表回收第0、1、2代的对象。如果不传参数，那么会使用2作为默认参数。
• get_threshold()：获取 gc 模块执行垃圾回收的阈值。返回的是个元组，第 0 个是零代的阈值，第1个是1代的阈值，第2个是2代的阈值。
• set_threshold(threshold0[, threshold1[, threshold2])：设置执行垃圾回收的阈值。
• get_count()：获取当前自动执行垃圾回收的计数器。返回一个元组。第0个是零代的垃圾对象的数量，第1个是零代链表遍历的次数，第2个是1代链表遍历的次数。

Reference

• pythonav资源分享
• Pythonn内存管理以及垃圾回收机制 - 武沛齐 - 博客园
• 讲透了！Python 垃圾回收机制与原理解析
• 垃圾回收机制后章