python内存管理与垃圾回收

0
0
0

python中内存管理由一个私有堆完成。在这个私有堆中包含了所有python的对象与数据结构（在python中一切皆对象）。Python中的内存管理器管理这个堆。这个内存管理器有着不同的组件来处理不同的动态存储管理事务，如共享、分段、预分配和缓存等。docs.python.Memory Management

Memory management in Python involves a private heap containing all Python objects and data structures. The management of this private heap is ensured internally by the Python memory manager. The Python memory manager has different components which deal with various dynamic storage management aspects, like sharing, segmentation, preallocation or caching.

API层次结构

在python中内存管理被抽象为一个层次似的结构，如下表所示。

在最底层（第零层）是操作系统的提供的内存管理接口，如C语言运行所提供的malloc和free接口。这一层是由操作系统实现并管理的，python不能干涉这一层的行为。从这层往上都是由python维护；

第一层是由python在第零层操作系统提供的内存管理上就行简单地包装，屏蔽操作系统带来的内存管理差异。这一层的接口以PyMem_开头；

第二层是由python在第一层上做的进一步封装，主要提供了创建python对象的接口，以及提供内存的垃圾回收等机制。在这层，是一组以PyObj_开头的函数族；

第三层是由python在第二层上做的进一步封装，主要为python中的常用对象，如整数、字符串等构建更高层次的内存管理策略。

层数 功能
第三层 [int] [dict] [list] … [string]
特定对象的内存管理
第二层 PyObj_API（又称pymalloc机制）
对象存储（包含垃圾回收机制）
第一层 PyMem_API
在PyMem管理器控制下的内存（malloc等的简单包装）
第零层 操作系统提供的内存分配接口（C语言库中的malloc等）

从最底层来看，python管理的内存是由C语言中的malloc/realloc分配，而malloc分配的内存就是在堆区，因此说整个python的内存管理由一个私有堆完成。

内存组织结构

PyObj_API,又称pymalloc(Python’s memory allocator)是由Vladimir Marangozov编写，pymalloc为了防止小对象的频繁地创建与销毁导致malloc与free被频繁调用，其将内存组织为名为arena的内存块，一个arena的大小为256KB，每个arena由64个4KB的pool组成，而每个pool又由固定大小的Blocks组成。如下图所示

Figure 1: Memory layout of arenas, pools and blocks.
Figure 1: Memory layout of arenas, pools and blocks.

每个pool中的blocks大小相同，不同pool之间blocks大小可能不同，blocks的大小可为8, 16, 32, …, 256 字节。

内存分配

当要分配一个新的对象时， 内存分配器首先会判断是否有pool中含有所需要尺寸的block，如图2所示。 python的usedpools中维持有所有正在使用的pools的信息，这些pools都包含有各自大小的blocks。若有含有所需大小的block的pool，我们将相应block从blocks列表中取出。如果取出的block是这个pool中的最后一个block，这说明pool已经被完全分配，于是我们将其从usedpools中移除。最户，我们将取出的block返回给相应的应用。

Figure 2: The usedpools array for storing partially allocated pools
Figure 2: The usedpools array for storing partially allocated pools

如果没有相应大小block的pool，我们需要从freepools链式列表中取出一个可用的pool。freepools的结构如图3所示。如果有可用的pool存在于freepools中，我们取出一个pool。否则，我们需要创建一个新的pool。如果在我们最近分配的arena中有多余的空间创建pool，我们直接创建。若没有，我们使用malloc创建一个新的arena，并在其上创建一个还有所需大小的blocks的pool，同时，把这个pool加入usedpools链式列表。最后将所需的一个block返回给应用。

Figure 3: The freepools list and allocating new pools.
Figure 3: The freepools list and allocating new pools.

释放内存

当python中一个应用释放了block后。python首先确定这个block属于哪个pool，然后block被置于这个pool的空闲blocks列表中。如果这个pool原来被完全的分配了，则在加入空闲block之后，将其置于usedpools链式列表中。如果这个pool在加入这个空闲block之后，其所有block都处于空闲状态，则将这个pool加入到freepools链式列表中。

在python 2.5以后，arena的状态也被分为“可用”与“未使用”两种状态，在pool加入freepools之后，若arena中所有的pool都为空闲，则python加arena中的内存释放给系统。内存池全景如图4所示。

内存池全景
Figure 4: The overall of the memory structure

垃圾回收

Python的GC模块主要运用了“引用计数”（reference counting）来跟踪和回收垃圾。在引用计数的基础上，还可以通过“标记-清除”（mark and sweep）解决容器对象可能产生的循环引用的问题。通过“分代回收”（generation collection）以空间换取时间来进一步提高垃圾回收的效率。

"引用计数"原理：当一个对象的引用被创建或者复制时，对象的引用计数加1；当一个对象的引用被销毁时，对象的引用计数减1；当对象的引用计数减少为0时，就意味着对象已经没有被任何人使用了，可以将其所占用的内存释放了。

"标记-清除"原理：标记清除算法作为Python的辅助垃圾收集技术主要处理的是一些容器对象，比如list、dict、tuple，instance等，因为对于字符串、数值对象是不可能造成循环引用问题。Python使用一个双向链表将这些容器对象组织起来。将集合中对象的引用计数复制一份副本，遍历对象集合，将被引用对象的引用计数副本值减1，计算有效引用。最终标记出垃圾对象，进而清除。
标记-清除的逻辑如下（参考Python 源码阅读 – 垃圾回收机制）：

分配内存
-> 发现超过阈值了
-> 触发垃圾回收
-> 将所有可收集对象链表放到一起
-> 遍历, 计算有效引用计数
-> 分成 有效引用计数=0 和 有效引用计数 > 0 两个集合
-> 大于0的, 放入到更老一代
-> =0的, 执行回收
-> 回收遍历容器内的各个元素, 减掉对应元素引用计数(破掉循环引用)
-> 执行-1的逻辑, 若发现对象引用计数=0, 触发内存回收
-> python底层内存管理机制回收内存

"分代回收"原理：分代回收是一种以空间换时间的操作方式。将系统中的所有内存块根据其存活时间划分为不同的集合，每一个集合就成为一个“代”，垃圾收集的频率随着“代”的存活时间的增大而减小。也就是说，活得越长的对象，就越不可能是垃圾，就应该减少对它的垃圾收集频率。那么如何来衡量这个存活时间：通常是利用几次垃圾收集动作来衡量，如果一个对象经过的垃圾收集次数越多，可以得出：该对象存活时间就越长。

引用计数

引用计数法在对象内部维护了一个被其他对象引用数的引用计数值，当这个引用计数值为0时，说明这个对象不再被其他对象引用，就可以被回收了。

结合源码来看，所有Python对象的头部包含了这样一个结构PyObject（相当于继承自PyObject）：

// object.h
struct _object {
    Py_ssize_t ob_refcnt;
    struct PyTypeObject *ob_type;
} PyObject;

ob_refcnt就是引用计数值。

例如，下面是int型对象的定义：


// intobject.h
typedef struct {
        PyObject_HEAD
        long ob_ival;
} PyIntObject;

引用计数法有很明显的优点：

  1. 高效
  2. 运行期没有停顿
  3. 对象有确定的生命周期
  4. 易于实现

原始的引用计数法也有明显的缺点：

  1. 维护引用计数的次数和引用赋值成正比，而不像mark and sweep等基本与回收的内存数量有关。
  2. 无法解决循环引用的问题。A和B相互引用而再没有外部引用A与B中的任何一个，它们的引用计数都为1，但显然应该被回收。

为了解决这两个致命弱点，Python又引入了以下两种GC机制。

标记-清除

“标记-清除”法是为了解决循环引用问题。可以包含其他对象引用的容器对象（如list, dict, set，甚至class）都可能产生循环引用，为此，在申请内存时，所有容器对象的头部又加上了PyGC_Head来实现“标记-清除”机制。

// objimpl.h
typedef union _gc_head {
    struct {
        union _gc_head *gc_next;
        union _gc_head *gc_prev;
        Py_ssize_t gc_refs;
    } gc;
    long double dummy;  /* force worst-case alignment */
} PyGC_Head;

在为对象申请内存的时候，可以明显看到，实际申请的内存数量已经加上了PyGC_Head的大小

// gcmodule.c
PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
    PyObject *op;
    PyGC_Head *g = (PyGC_Head *)PyObject_MALLOC(
                sizeof(PyGC_Head) + basicsize);
    if (g == NULL)
        return PyErr_NoMemory();

    ......

    op = FROM_GC(g);
    return op;
}

举例来说，从list对象的创建中，有如下主要逻辑：

// listobject.c
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就将对象链接到了第0代对象集合中（后文详述分代回收）。

垃圾标记时，先将集合中对象的引用计数复制一份副本(以免在操作过程中破坏真实的引用计数值)：

// gcmodule.c
static void
update_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc = gc->gc.gc_next) {
        assert(gc->gc.gc_refs == GC_REACHABLE);
        gc->gc.gc_refs = FROM_GC(gc)->ob_refcnt;
        assert(gc->gc.gc_refs != 0);
    }
}

然后操作这个副本，遍历对象集合，将被引用对象的引用计数副本值减1：


// gcmodule.c
static void
subtract_refs(PyGC_Head *containers)
{
    traverseproc traverse;
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc=gc->gc.gc_next) {
        traverse = FROM_GC(gc)->ob_type->tp_traverse;
        (void) traverse(FROM_GC(gc),
                   (visitproc)visit_decref,
                   NULL);
    }
}

这个traverse是对象类型定义的函数，用来遍历对象，通过传入的回调函数visit_decref来操作引用计数副本。

例如dict就要在key和value上都用visit_decref操作一遍：

// dictobject.c
static int
dict_traverse(PyObject *op, visitproc visit, void *arg)
{
    Py_ssize_t i = 0;
    PyObject *pk;
    PyObject *pv;

    while (PyDict_Next(op, &i, &pk, &pv)) {
        visit(pk);
        visit(pv);
    }
    return 0;
}

然后根据引用计数副本值是否为0将集合内的对象分成两类，reachable和unreachable，其中unreachable是可以被回收的对象：

// gcmodule.c
static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
    PyGC_Head *gc = young->gc.gc_next;
    while (gc != young) {
        PyGC_Head *next;
        if (gc->gc.gc_refs) {
            PyObject *op = FROM_GC(gc);
            traverseproc traverse = op->ob_type->tp_traverse;
            assert(gc->gc.gc_refs > 0);
            gc->gc.gc_refs = GC_REACHABLE;
            (void) traverse(op,
                            (visitproc)visit_reachable,
                            (void *)young);
            next = gc->gc.gc_next;
        }
        else {
            next = gc->gc.gc_next;
            gc_list_move(gc, unreachable);
            gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
        }
        gc = next;
    }
}

在处理了weak reference和finalizer等琐碎细节后（本文不展开讲述，有兴趣的童鞋请参考python源码），就可以回收unreachable中的对象了。

分代回收

分代回收的整体思想是：将系统中的所有内存块根据其存活时间划分为不同的集合，每个集合就成为一个“代”，垃圾收集频率随着“代”的存活时间的增大而减小，存活时间通常利用经过几次垃圾回收来度量。

用来表示“代”的结构体是gc_generation， 包括了当前代链表表头、对象数量上限、当前对象数量：


// gcmodule.c
struct gc_generation {
    PyGC_Head head;
    int threshold; /* collection threshold */
    int count; /* count of allocations or collections of younger
 generations */
};

Python默认定义了三代对象集合，索引数越大，对象存活时间越长。

#define NUM_GENERATIONS 3
#define GEN_HEAD(n) (&generations[n].head)

/* 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},
    {{{GEN_HEAD(1), GEN_HEAD(1), 0}},   10,     0},
    {{{GEN_HEAD(2), GEN_HEAD(2), 0}},   10,     0},
};

新生成的对象会被加入第0代，前面_PyObject_GC_Malloc中省略的部分就是Python GC触发的时机。每新生成一个对象都会检查第0代有没有满，如果满了就开始着手进行垃圾回收：


g->gc.gc_refs = GC_UNTRACKED;
 generations[0].count++; /* number of allocated GC objects */
 if (generations[0].count > generations[0].threshold &&
     enabled &&
     generations[0].threshold &&
     !collecting &&
     !PyErr_Occurred()) {
          collecting = 1;
          collect_generations();
          collecting = 0;

参考文献

http://www.cnblogs.com/vamei/p/3232088.html
http://blogs.microsoft.co.il/terfin3/2016/01/14/python-small-memory-allocator/
http://www.wklken.me/posts/2015/08/29/python-source-memory-1.html

Was this helpful?

0 / 0

发表回复 0