自从java把垃圾回收的概念发扬光大,现在介绍垃圾回收算法的文章已经很多了,这篇文章的目的是想结合python源码分析python实现的GC算法.

简单得说,垃圾回收就是两个步骤:找出垃圾,回收垃圾.回收比较简单,直接free掉就可以.关键在于怎么找到垃圾.

找垃圾的算法有两种,一个是引用计数法,这是python使用的,引用计数法比较好理解,接触过com的人肯定记得他,用一个整数保存当前对内存块引用的数目,找垃圾就只需要找那些引用计数为0的就可以,唯一的缺陷就是著名的引用循环问题,当然python2.0以后解决了这个问题;另一种就是tracing算法了,.net和java使用的都是这个,该算法要求维护固定数目的几个"根","根"保存着对其他内存块的引用,当然普通内存块也可以保存其他内存块的引用,比如容器.这样内存块和之间的引用就构成了一棵树,所有分配的内存块都在这棵树中,删除一个内存块删除对他的引都是有用的,用就可以.找垃圾的时候不是很方便,每次从"根"开始遍历这棵树,能遍历到的剩下的都是垃圾,这个时候如何清除垃圾又有两种选择,详细情况见... 另外generation算法和adaptive算法都是通用的,详细情况也不一一赘述了.

上面说了.net和java都选择tracing算法,为什么python却选择引用计数法呢.我觉得是这样的: tracing算法需要维护一棵或几棵固定的内存树,这样就使得内存必须统一进行分配,而python是个很开放的东西,为了允许用户编写自己的内存分配方式