垃圾回收器(GC)

在现代语言的设计中，垃圾回收器被广泛使用，高效的垃圾回收机制可以防止内存泄漏和指针悬空等问题，能够更好的使用计算机的内存。在计算机语言发展的过程中，也出现了很多类型的垃圾回收算法。
Python里也一样采用了垃圾收集机制，Python采用的是引用计数机制为主，标记-清除和分代收集两种机制为辅的策略.

引用计数(Reference Counting Collector)

Python里面所有的value都是对象，它们的核心就是一个结构体：PyObject

1
2
3
4
typedef struct_object {
    int ob_refcnt;
    struct_typeobject *ob_type;
} PyObject;

引用计数算法最早George E. Collins在1960的时候首次提出，50年后的今天，该算法依然被很多编程语言使用。每个PyObject维护一个ob_refcnt字段，用来记录该对象当前被引用的次数，每当新的引用指向该对象时，它的引用计数ob_refcnt加1，每当该对象的引用失效时计数ob_refcnt减1，一旦对象的引用计数为0，该对象立即被回收，对象占用的内存空间将被释放。

虽然引用计数必须在每次分配和释放内存的时候加入管理引用计数的动作，然而与其他主流的垃圾收集技术相比，引用计数有一个最大的有点，即“实时性”，任何内存，一旦没有指向它的引用，就会立即被回收。而其他的垃圾收集计数必须在某种特殊条件下（比如内存分配失败）才能进行无效内存的回收。

引用计数机制执行效率问题：引用计数机制所带来的维护引用计数的额外操作与Python运行中所进行的内存分配和释放，引用赋值的次数是成正比的。而这点相比其他主流的垃圾回收机制，比如“标记-清除”，“停止-复制”，是一个弱点，因为这些技术所带来的额外操作基本上只是与待回收的内存数量有关。（引用技术和内存操作次数有关，其余机制主要和内存使用数量相关）

引用计数机制的致命缺点是它不能解决对象的“循环引用”。

循环引用可以使一组对象的引用计数不为0，然而这些对象实际上并没有被任何外部对象所引用，它们之间只是相互引用。这意味着不会再有人使用这组对象，应该回收这组对象所占用的内存空间，然后由于相互引用的存在，每一个对象的引用计数都不为0，因此这些对象所占用的内存永远不会被释放。比如：

1
2
3
4
5
6
list1 = []
list2 = []
list1.append(list2)
list2.append(list1)
list1  //[[[...]]]
list2  //[[[...]]]

这一点是致命的，这与手动进行内存管理所产生的内存泄露毫无区别。

要解决这个问题，Python引入了其他的垃圾收集机制来弥补引用计数的缺陷：“标记-清除”，“分代回收”两种收集技术。

标记-清除(Mark-Sweep Collector)

标记清除回收算法解决了一些在引用计数算法中存在的问题。它解决了循环引用问题，因为不需要维护计数器所以性能开销要小得多。在申请内存时，所有容器对象的头部加上了PyGC_Head来实现“标记-清除”机制。

1
2
3
4
5
6
7
8
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;

我们必须承认一个事实，如果两个对象的引用计数都为1，但是仅仅存在他们之间的循环引用，那么这两个对象都是需要被回收的，也就是说，它们的引用计数虽然表现为非0，但实际上有效的引用计数为0。我们必须先将循环引用摘掉，那么这两个对象的有效计数就现身了。假设两个对象为A、B，我们从A出发，因为它有一个对B的引用，则将B的引用计数减1；然后顺着引用达到B，因为B有一个对A的引用，同样将A的引用减1，这样，就完成了循环引用对象间环摘除。

但是这样就有一个问题，假设对象A有一个对象引用C，而C没有引用A，如果将C计数引用减1，而最后A并没有被回收，显然，我们错误的将C的引用计数减1，这将导致在未来的某个时刻出现一个对C的悬空引用。这就要求我们必须在A没有被删除的情况下复原C的引用计数，如果采用这样的方案，那么维护引用计数的复杂度将成倍增加。

原理：“标记-清除”采用了更好的做法，我们并不改动真实的引用计数，而是将集合中对象的引用计数复制一份副本，改动该对象引用的副本。对于副本做任何的改动，都不会影响到对象生命走起的维护。

这个计数副本的唯一作用是寻找root object集合（该集合中的对象是不能被回收的）。当成功寻找到root object集合之后，首先将现在的内存链表一分为二，一条链表中维护root object集合，成为root链表，而另外一条链表中维护剩下的对象，成为unreachable链表。之所以要剖成两个链表，是基于这样的一种考虑：现在的unreachable可能存在被root链表中的对象，直接或间接引用的对象，这些对象是不能被回收的，一旦在标记的过程中，发现这样的对象，就将其从unreachable链表中移到root链表中；当完成标记后，unreachable链表中剩下的所有对象就是名副其实的垃圾对象了，接下来的垃圾回收只需限制在unreachable链表中即可。

分代收集(Generation Collector)

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

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

1
2
3
4
5
6
struct gc_generation {
    PyGC_Head head;
    int threshold; /* collection threshold */
    int count; /* count of allocations or collections of younger
              generations */
};

从前面“标记-清除”这样的垃圾收集机制来看，这种垃圾收集机制所带来的额外操作实际上与系统中总的内存块的数量是相关的，当需要回收的内存块越多时，垃圾检测带来的额外操作就越多，而垃圾回收带来的额外操作就越少；反之，当需回收的内存块越少时，垃圾检测就将比垃圾回收带来更少的额外操作。为了提高垃圾收集的效率，采用“空间换时间的策略”。

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