概述

Python 的垃圾回收以引用计数机制（Reference Counting）为主，并配合使用标记 - 清除（Mark and Sweep）和分代回收（Generational Collection）等 GC 策略。

一、引用计数 Reference Counting

Python 中主要依赖引用计数来完成垃圾回收

原理

Python 的每个对象内部都会维护一个引用计数器，程序运行过程中会实时更新引用计数器的值，以此来反映引用当前对象的数量。当有新引用指向该对象时，引用计数器加1；当指向对象的引用失效时，引用计数器减1。当引用计数器数值为0时，该对象的内存就会被释放掉。可以通过 sys 包的 getrefcount() 来获取一个名称所引用的对象当前的引用计数（ps：这里 getrefcount() 本身会使得引用计数加一）。

1
sys.getrefcount(a)

  • 引用计数加1的情况：

    • 对象被创建，e.g. a=1
    • 对象被引用，e.g. b=a
    • 对象作为参数，被传入函数
    • 对象作为一个元素，被放入容器中

  • 引用计数减1的情况：

    • 对象别名被显示销毁 del
    • 对象别名被赋予新的对象
    • 一个对象离开他的作用域
    • 对象所在的容器被销毁或者是从容器中删除对象

优点

  • 逻辑简单、高效执行、实时性高，一旦某个对象的引用计数归零，内存就会被释放，无需像其他 GC 方法需要等到某个时机执行
  • GC 时间被打平，对运行中的程序影响较小

缺点

  • 逻辑简单但有一定的实现成本，每个对象都需要独立的空间维护引用计数器，加大了对空间的负担
  • 尽管 GC 时间被打平，但在一些场景下也会比较慢。在释放一个大对象时，如字典，需要对引用的所有对象循环嵌套调用，时间花销较大
  • 引用计数无法避免循环引用的问题，必须通过其他 GC 策略来辅助解决，这也导致一些高级语言如 Java 的 GC 没有采用引用计数机制

循环引用

当两个对象互相引用、且不存在任何外部引用时，两个对象的引用计数会始终为1，永远不会被垃圾回收。举个例子：

1
2
3
4
5
6
7
8
9
# list1和list2引用的对象引用计数加1
list1 = []
list2 = []
# list1和list2的对象互相引用，对象引用计数分别加1，即为2
list1.append(list2)
list2.append(list1)
# list1和list2引用的对象引用计数减1，但对象的引用计数仍然为1，且永远无法归0
del list1
del list2

为了解决循环引用问题，Python 又引入了以下两种 GC 策略。

二、标记 - 清除 Mark and Sweep

Python 采用标记 - 清除算法来解决容器对象可能产生的循环引用问题。（ps：只有容器对象才有可能产生循环引用，如列表、字典、自定义的类、元组等等。像整型、字符串等基础数据类型并不会出现循环引用。）

基本原理

标记 - 清除是一种基于 Tracing 的垃圾回收算法，主要分为两个阶段：第一阶段是标记，把所有存活对象打上标记；第二阶段是清除，对没有标记的失活对象进行回收。

  • 标记阶段：遍历所有对象，如果是可达的，说明还有对象引用它，则该对象被标记（ps：GC root 一般是一些全局变量、调用栈、寄存器等不可被删除的对象）
  • 清除阶段：再次遍历对象，如果发现某个对象没有被标记为可达，则将其回收

详细说明

参考：CPython 垃圾收集器设计

在标记 - 清除算法中，为了追踪容器对象，需要每个容器对象维护两个额外的指针，用来将容器对象组成一个双向链表（double-linked lists），指针分别指向前后两个容器对象，方便插入和删除操作。Python 解释器（CPython）维护了两个这样的双向链表，一个链表存放着需要被扫描的容器对象（Object to Scan），另一个链表存放着临时不可达对象（Unreachable）。下面举例说明标记-清除的详细过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

# Collect the unreachable Link object (and its .__dict__ dict).
gc.collect()
# Output: 2

该例子中，link1、link2、link3 形成引用环，同时 link1 还被名称 A 引用。link4 自引用，也构成一个引用环。在垃圾收集器中，每一个节点除了有一个记录当前引用计数的变量 ref_count 还有一个 gc_ref 变量，这个 gc_ref 是 ref_count 的一个副本，所以初始值为 ref_count 的大小。

  1. GC 启动时，遍历 Object to Scan 链表中的容器对象，并且将当前对象所引用的所有对象的 gc_ref 减 1。这一步相当于解除了循环引用的影响，因为只有真正被外部引用的对象才满足 gc_ref > 1。

  1. GC 再次扫描所有的容器对象，如果对象的 gc_ref 为0，则该对象被标记为 GC_TENTATIVELY_UNREACHABLE ，并且被移至 Unreachable 链表中（link3、link4）。（下图为处理了 link3 和 link4 的时刻，link1 和 link2 还没被处理）

  1. 紧接着2，如果对象的 gc_ref 不为0，那么这个对象就会被标记为 GC_REACHABLE（link1）。同时当 GC 发现一个节点是可达的，则会从该节点出发可以到达的所有节点标记为 GC_REACHABLE。如果被标记为 GC_REACHABLE 的节点在 Unreachable 链表中，则需要将其移回 Object to Scan 链表中（link3）。

  1. 第二次遍历结束后，存在于 Unreachable 链表中的对象就是真正需要被释放的对象，GC 随即释放。（link4）

Notice

标记 - 清除 执行时会 STW （stop the world），整个应用程序会被暂停直到标记 - 清除结束后才会恢复。

三、分代回收 Generational Collection

由于 标记 - 清除 会 STW，为了限制垃圾回收的时间，Python 通过引入分代回收来优化自身的垃圾回收机制，以空间换时间的方式来提高垃圾回收效率。

先验知识

  • 分代回收思想基于一个统计事实：对于程序，存在一定比例的内存块的生存周期比较短；而剩下的内存块，生存周期会比较长，甚至会从程序开始一直持续到程序结束。生存期较短对象的比例通常在 80%～90% 之间。
  • 简而言之，对象存在时间越长，越可能不是垃圾，应该越少去收集。这样在执行 标记-清除 算法时可以有效减小遍历的对象数，从而提高垃圾回收的速度。

原理

  • Python GC 给对象定义了三种世代(0,1,2)，每一个新生对象在 generation 0 中；如果它在一轮 GC 扫描中活了下来，那么它将被移至 generation 2，在那里他将较少的被扫描；如果它又活过了一轮 GC，它又将被移至 generation 2，在那里它被扫描的次数将会更少。
  • GC = 垃圾检查 + 垃圾回收。垃圾检查触发时机：世代中的对象达到一定的数目。
  • 每个世代都有自己的阈值，且越老年代的阈值会越小（阈值越小表示垃圾检查的频率越小）。
    • 阈值解释（以 (700, 10, 10) 为例）：
      • 第一个参数 700 表示距离上一次 generation 0 垃圾检查，Python 分配内存数目减去释放内存的数目，如果超过 700 就会触发 generation 0 的垃圾检查
      • 第二个参数 10 表示距离上一次 generation 1 垃圾检查，generation 0 垃圾检查的次数
      • 第三个参数 10 表示距离上一次 generation 2 垃圾检查，generation 1 垃圾检查的次数
    • 通过以下两个函数可以查询和调整阈值：
1
2
gc.get_threshold() # (threshold0, threshold1, threshold2). default (700, 10, 10)
gc.set_threshold(threshold0[, threshold1[, threshold2]])

垃圾回收触发时机

  1. 调用 gc.collect(),需要先导入 gc 模块。
  2. 自动垃圾回收：当 gc 模块的计数器达到阀值的时候（上述情况）。
  3. 程序退出的时候。