本文转载自微信公众号《小菜学编程》，作者fasionchan。转载本文请联系小彩雪编程公众号。Python内部使用引用计数的方法维护每个对象的引用次数，回收不再需要的垃圾对象。由于引用计数方式的重大缺陷，在存在循环引用时存在内存泄漏的风险，因此Python也采用mark-and-clear方式回收循环引用的垃圾对象。另外，为了提高垃圾回收（GC）的效率，Python还引入了分代回收机制。对象跟踪跟踪程序内部的对象，是垃圾回收的第一步。那么，是否需要跟踪程序创建的所有对象？一个对象是否需要被跟踪取决于它是否会形成循环引用。Python对象根据引用特点可分为两类：内向型对象，如int、float、str等，不引用其他对象，因此不能形成循环引用，不需要被追踪；面向外部的对象，如元组、列表、字典等容器对象，以及函数、类实例等复杂对象。此类对象一般会引用其他对象，存在形成循环引用的风险。因此，它们是垃圾回收算法的重点；这是一个典型的例子，橙红色外向型对象有循环引用的可能，需要跟踪；而绿色的向内类型对象在引用关系图中只能作为叶子节点存在，不能形成任何环，所以无需跟踪：Python为外部类型对象分配内存时，调用位于_PyObject_GC_AllocModules/gcmodule.c源文件的功能。该函数在对象头之前保留了一些内存空间，以便垃圾收集器可以使用链表跟踪它们。保留的内存空间是一个_gc_head结构体，定义在Include/objimpl.h头文件中：mallocreturnsmemoryblockalignedforanybuilt-intypesand//longdoubleisthelargeststandardCtype.//Onamd64linux,longdoublerequires16bytealignment.//Seebpo-27987fororediscussion.}PyGC_Head;gc_next，链表的后向指针，指向下一个被跟踪对象；gc_prev，指向链表对象的前向跟踪；gc_refs，对象引用计数副本，用于标记清除算法；dummy，用于内存对齐，以64位系统为例，保证_gc_head结构体的大小为16字节的整数倍，且结构体地址在16字节处对齐；以list对象为例，_PyObject_GC_Alloc函数在PyListObject结构体中加入_gc_head结构体申请内存，但只返回PyListObject的地址作为对象地址，而不是整块内存的首地址：就是这样，借助gc_next和gc_prev指针，Python将需要跟踪的对象一一组织成一个双向链表：这个链表也称为可收集（collectable）对象链表，Python会收集并回收垃圾来自这个链表的对象。分代回收机制一个Python程序启动后，内部可能会创建大量的对象。如果每次执行mark-and-sweep方法都需要遍历所有对象，很可能会影响程序性能。为此，Python引入了分代回收机制——将对象分成若干“世代”（generations），每次只处理某一代中的对象，因此GC停顿时间更短。那么，对象的划分标准是什么？将一个对象随机分成某一代就足够了吗？答案是不。其实对象生成有很多学问，一个好的划分标准可以显着提高垃圾回收的效率。考察一个对象的生命周期，我们可以发现一个显着的特点：一个对象存活的时间越长，它在下一时刻被释放的概率就越低。我们应该也有这样的切身体会：程序中经常会创建一些临时对象，用完就立即释放；定义为全局变量的对象很少被释放。因此，按照对象的生命周期来划分对象是一个不错的选择。对象存活时间越长，被释放的概率越低，可适当降低回收频率；反之，对象存活时间越短，被释放的概率越高，可以适当提高回收频率。对象存活时间释放概率回收频率longlowlowshorthighhighPython内部根据对象存活时间将对象分为3代（见Include/internal/mem.h）：#defineNUM_GENERATIONS3每一代由一个gc_generation结构维护，也就是在Include/internal/mem.h头文件中定义：structgc_generation{PyGC_Headhead;intthreshold;/*collectionthreshold*/intcount;/*countofallocationsorcollectionsofyoungergenerations*/};链表维护；阈值，只有当计数超过这个阈值时，Python垃圾回收操作才会扫描这一代的对象；count，计数器，不同代的统计项不同；Python虚拟机的运行时状态由Include/internal/pystate.h中的pyruntimestate结构体显示，其内部有一个_gc_runtime_state(Include/internal/mem.h)结构体，存储GC状态信息，包括3个对象世代.这3代在GC模块(Modules/gcmodule.c)_PyGC_Initialize函数中初始化：structgc_generationgenerations[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},};为了讨论方便，我们将这三代分别称为：第一代、中代和老一代。这三个世代初始化时，对应的gc_generation数组大致是这样的：每个gc_generation结构链表的头节点都指向自己，换句话说，每个可收集对象链表的开头都是空的；计数器字段count被初始化为0；threshold字段threshold有自己的策略。如何理解这些策略？当Python调用_PyObject_GC_Alloc为需要跟踪的对象分配内存时，该函数会将初级生成的计数计数器加1，然后将对象连接到初级生成对象列表；当Python调用PyObject_GC_Del释放垃圾对象的内存时，该函数将初级代的计数计数器减1；如果_PyObject_GC_Alloc增加计数并超过阈值(700)，它将调用collect_generations来执行垃圾收集(GC)。collect_generations函数从老年代开始，逐代遍历每一代，找出最老的需要回收的代（count>threshold）。然后调用collect_with_callback函数开始回收生成，这个函数最后调用collect函数。当collect函数处理一个代时，首先将比它年轻的代计数器计数重置为0；然后取出它们的对象链表，将它们与自身拼接在一起，执行GC算法（本文后半部分介绍）；最后，将下一代计数器加一。系统每新增701个需要GC的对象，Python都会进行一次GC操作；每次GC操作需要处理的代可能不同，由count和threshold决定；某一代需要执行GC（count>threshold），它前面的所有年轻代也同时执行G??C；多代执行GC，Python将它们的对象链表拼接在一起进行一次性处理；GC执行完后，count清零，下一代count加一；举个简单的例子：第一代触发GC操作，Python执行collect_generations函数。发现最老的达到阈值的代是中生代，于是调用collection_with_callback(1)，其中1是数组中中生代的下标。collection_with_callback(1)最后调用的是collect(1)，先对下一代计数器加1；然后将当前代和所有之前的年轻代计数器重置为零；最后调用gc_list_merge将这些可回收??对象的链表合并在一起：最后collect函数执行标记清除算法对合并后的链表进行垃圾回收。详情在本文后半部分介绍。这就是分代回收机制的全部秘密。看似复杂，但稍微总结一下就可以得出一些直截了当的策略：每次添加701个需要GC的新对象，就触发一次新生代GC；每11次二代GC触发一次中生代GC；MesozoicGC每执行11次就会触发一次老年代GC（老年代GC还受其他策略影响，频率较低）；在执行某次新生代GC之前，新生代对象列表也一起移入本代和GC；对象创建后，会随着时间的推移逐渐移入老年代，回收频率逐渐降低；限于篇幅，部分分代回收代码无法逐行解释，请参考图示阅读相关重点功能，应该不难理解。现在，我们有了一个Python垃圾回收机制的框架，但是对于检测垃圾对象的方法知之甚少。垃圾对象识别是垃圾回收的重中之重。Python是如何解决这个关键问题的？
