Python源码剖析——垃圾回收机制

前言

在Python中，内存管理机制被抽象成一种层次似的结果。

第0层，是操作系统提供的内存管理接口，比如C运行时所提供的malloc和free接口。这一层由操作系统实现并管理。
第1层，是Python基于第0层操作系统的内存管理接口包装而成的，因为虽然操作系统都提供了ANSI C标准所定义的内存管理接口，但是对于某些特殊的情况不同的操作系统有不同的行为。
第2层，第一层所提供的内存管理接口其功能是有限的，加入要创建一个PyIntObject对象，还需要许多额外的工作，如设置对象的类型，初始化对象的引用计数值等。为了简化Python自身的开发，Python在比第一层更高的抽象层次上提供了第二层管理接口，主要提供了创建Python对象的接口。
第3层，主要是对象缓冲池机制。

在Python中，许多时候申请的内存都是小块的内存，申请后很快又会被释放，它们不是为了创建对象，没有对象一级的内存池机制。意味着会大量执行malloc和free操作，影响Python的执行效率。

为了提高执行效率，Python引入一个内存池机制，管理小块内存的申请和释放。

Python默认小块内存与大块内存的分界点定在256个字节，也就是说，当申请的内存小于256字节时PyObject_Malloc会在内存池中申请内存；当申请内存大于256字节时PyObject_Malloc的行为蜕化为malloc的行为。

在Python中，大多数对象的声明周期都是通过对象的引用计数来管理的。但循环引用这种状态不同通过引用计数来回收内存，需要配合另外两种垃圾收集技术，标记——清除和分代收集。

当一个对象的引用被创建或者复制时，对象的引用计数加1；当一个对象的引用被销毁（退出作用域、被del删除）时，对象的引用计数减1。如果对象的引用计数为0，那么释放其所占用的内存。

引用计数有一个问题，就是可能会产生循环引用，看一段代码：

>>> l1 = []
>>> l2 = []
>>> l1.append(l2)
>>> l2.append(l1)
>>> l1
[[[...]]]
>>> l2
[[[...]]]

要想回收l1的内存需要先将其引用计数置为0，其引用为l2即需要先释放l2的内存。同时，回收l2的内存需要先将其引用计数置为0，其引用为l1即需要先释放l1的内存，此时造成了循环引用的状态，这些对象所占用内存永远不会被回收。

Python 中的循环引用总是发发生在container对象之间，所谓container对象即是内部可持有对其他对象引用的对象，比如list、dict、class、instance等等。当Python垃圾回收机制运行时，只会去检查container对象。

为了解决循环引用这个问题Python引用了标记-清除和分代回收技术。

其简要工作过程如下：

寻找根对象（root object）的集合，root object即是一些全局引用和函数栈中的引用。这些引用所用的对象是不可被删除的。
从root object集合出发，沿着root object集合中的每一个引用，如果能到达某个对象A，则A称为可达的，可达的对象也不可删除。这个阶段就是垃圾检测阶段。
当垃圾检测阶段结束后，所有的对象分为了可达的和不可达的两部分，对所有不可达的对象占用的内存将被回收，这就是垃圾回收阶段。

Python中的循环引用总是发生在container对象之间，所谓container对象即是内部可持有对其他对象的引用的对象，如list、dict、class、instance等。Python的垃圾收集机制运行时，只需要去检查这些container对象。

Python中使用链表来存储可收集对象。

将系统中的所有内存块根据其存活时间划分为不同的集合，每一个集合称为一个“代”，代的存活时间越长，就越可能不是垃圾，应该越少去收集。衡量存活时间的标准就是经过了几次垃圾收集动作。每一个“代”用链表实现。

一个垃圾回收的例子：
分代清除

垃圾回收的过程中必然要涉及到频繁的插入（分代回收，如第0代放在第1代之后）、删除（标记清除，删除不可达节点）的过程，使用双向链表等结构可以使插入、删除等操作时间复杂度达到为O(1)；相比于链表，如果使用树型的数据结构，那么插入和删除的时间复杂度会达到O(logN),同时由于树的父子间的复杂关系，在删除的时候会进行大量操作。
container对象的内存分布中有三部分，一块用于垃圾回收机制，一块是PyObject_HEAD和自身数据，Python使用双向链表结构将container对象连接起来。在标记的过程中，根据链表结构一对一的对关系，一次完全遍历和一次简答的遍历就可以完成标记任务；如果使用树型结构，由于树的性质，每个节点需要保存2个至多个子代信息，需要保存额外的信息，浪费资源。