python GC

pptg大约 4 分钟

1. 垃圾回收机制

python的垃圾回收机制主要分为三大块:

引用计数法: 最基本的回收方法
标记清除法: 用于回收循环引用的部分
分代回收法: 用于解决频繁扫描“标记清除列表”的性能问题

1.1 引用计数法

python通过引用计数器来进行垃圾回收。每个对象的基础结构里都维护了引用计数字段，如果他的引用数量是0，则会触发回收机制。

// 这是Python对象在C层面的基础结构
typedef struct _object {
    Py_ssize_t ob_refcnt;  // 引用计数
    PyTypeObject *ob_type; // 类型指针
    // ... 其他字段根据类型不同而变化
} PyObject;

当有对象引用/去除引用的时候，分别会调用两个引用计数的操作原语

// C层面的宏定义
#define Py_INCREF(op) (                         \
    _Py_INC_REFTOTAL  _Py_REF_DEBUG_COMMA       \
    ((PyObject *)(op))->ob_refcnt++)

// 实际应用场景：
// - 赋值操作: a = b
// - 函数参数传递
// - 放入容器: list.append(obj)

#define Py_DECREF(op)                   \
    do {                                \
        PyObject *_py_decref_tmp = (PyObject *)(op); \
        if (_Py_DEC_REFTOTAL  _Py_REF_DEBUG_COMMA \
        --(_py_decref_tmp)->ob_refcnt != 0)        \
            _Py_CHECK_REFCNT(_py_decref_tmp)       \
        else                            \
            _Py_Dealloc(_py_decref_tmp); \
    } while (0)

当Py_DECREF检查到引用计数归零时，会调用_Py_Dealloc最终调用到python里的__del__方法，从refchain中移除，最后通过内存管理器将内存还给分配器或操作系统

1.2 refchain

Python中，refchain类似于“注册列表”，在创建对象时，会加入到refchain中。在销毁时再从refchain移除。

refchain为了高效的删除、插入节点，其底层实现是一个双向列表，实现如下：

#define PyObject_HEAD PyObject ob_base;
#define Pyobject_VAR_HEAD Pyvarobject ob_base;

// 宏定义 上、下节点
#define _PyobJect_HEAD_EXTRA    \
    struct| _object *_ob_next;  \
    struct _object '_ob_prev;

typedef struct _object {
    _Pyobject_HEAD_EXTRA // 用于构造双向链表
    Py_ssize_t ob_refcnt; // 引用计数器
    struct _typeobject *ob_type; // 数据类型 
｝ Pyobject;

typedef struct ｛
    Pyobject ob_base: // Pyobject对象
    Py_sssze_t ob_size: /* Number of items in variable part,即:元素个数*/ 
｝ PyVarObject;

不同类型的对象有不同的refchain结构体，但也都是基于上述结构进行的封装，比如：

int

typedef struct _longobject｛
    PyObject_VAR_HEAD 
    digit ob_digit［1］;
｝PyLongobject;

list

typedef struct{
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
}PyListObject

dict

typedef struct{
    PyObject_VAR_HEAD
    Py_ssize_t allocated;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values
}PyDictObject

1.3 标记清除法

在引用计数法中，对于循环引用的情况下，无法对这两个对象进行清除（A、B互相引用，但没有其他对象引用他们）。为此Python引入了标记清除法。

在触发时，执行下面的流程：

确定根对象（当前栈帧的变量、全局变量、模块级变量、内部状态等）
标记可达对象：从根对象出发，使用DFS算法（当深度不高的时候，相比BFS更节省内存）遍历所有可达的对象，并标记为存活
清除不可达对象: 与GC跟踪对象对比，清除那些没被标记的对象

哪些对象会被GC跟踪?

list、dict、set
自定义类的实例
包含可变对象的tuple

不可变对象除了被驻留外，不会被GC追踪（如int、str、tuple）

1.4 分代回收法

分代回收法和标记清除法相互配合，标记清除法决定了具体的执行过程。分代回收法则负责处理触发时机和GC对象的跟踪。

分代回收维护了0/1/2三个双向链表，分别存储了跟踪的GC对象。

0代：当列表长度为700时，触发标记清除算法，并对存活对象晋升到1代
1代：当0代执行10次后触发，触发标记清除算法，并对存活对象晋升到2代
2代：当1代执行10次后触发，触发标记清除算法

// 分代的C源码
#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代
};

2. 缓存机制

在GC中，当引用为0时，有时也不会真的触发回收。因为有些对象需要反复创建和销毁，所以python引入了缓存机制。将需要销毁的对象放入到free_list单向链表中，之后再创建对象时，首先检查free_list是否有可用的内存块，具有以下优势:

性能提升：减少内存分配的系统调用
减少内存碎片：重用相同大小的内存块
降低开销：避免频繁的内存分配和释放

对于不同的类型，分别有不同的free_list

int：使用小数据池优化[-5 到 256]
list：最大80个
dict：最大80个
float：最大100个
元组：最大20组，每组2000个