当前位置：首页 > news >正文

python虚拟机集锦（1）-垃圾收集算法（1）

news 来源：原创 2024/11/30 18:35:34

引用计数

CPython使用的主要垃圾收集算法是引用计数。基本思想是CPython计算有多少不同的地方引用了一个对象。
这样的位置可以是另一个对象，或者全局（或静态）C变量，或者某个C函数中的局部变量。
当对象的引用计数变为零时，该对象将被释放。
如果它包含对其他对象的引用，则其引用计数将递减。
如果该减量使其他对象的引用计数变为零，则可以依次取消分配这些对象，依此类推。
可以使用sys.getrefcount函数检查引用计数字段（请注意，此函数返回的值总是多于1，因为该函数在调用时也有对该对象的引用）：

x = object()
sys.getrefcount(x)
2
y = x
sys.getrefcount(x)
3
del y
sys.getrefcount(x)
2

参考计数方案的主要问题是它不处理参考周期。例如，考虑以下代码：

container = []
container.append(container)
sys.getrefcount(container)
3
del container

在本例中，容器保存对其自身的引用，因此即使我们删除对它的引用（变量“container”），引用计数也不会下降到0，因为它仍然有自己的内部引用。
因此，它永远不会仅仅通过简单的引用计数来清理。
由于这个原因，一旦对象变得不可访问，就需要一些额外的装置来清理对象之间的这些参考循环。
这是循环垃圾收集器，通常称为垃圾收集器（GC），尽管引用计数也是垃圾收集的一种形式。

内存布局和对象结构

通常，支持常规Python对象的C结构如下所示：

object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
              |                    ob_refcnt                  | |
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
              |                    *ob_type                   | |
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
              |                      ...                      |

为了支持垃圾收集器，更改对象的内存布局以在正常布局之前容纳额外信息：

              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
              |                    *_gc_next                  | |
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
              |                    *_gc_prev                  | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
              |                    ob_refcnt                  | \
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
              |                    *ob_type                   | |
              +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
              |                      ...                      |

通过这种方式，对象可以被视为一个普通的python对象，当需要与GC相关的额外信息时，可以通过原始对象的简单类型转换来访问前面的字段：（（PyGC_Head*）（the_object）-1）。

正如后面在优化：重用字段以节省内存所解释的，这两个额外的字段通常用于保存垃圾收集器跟踪的所有对象的双链接列表（这些列表是GC生成），但是当不需要完整的双链接列表结构作为内存优化时，它们也被重用以实现其他目的。

重用字段以节省内存
为了节省内存，每个具有GC支持的对象中的两个链接列表指针可用于多种用途。这是一种常见的优化，称为“胖指针”或“标记指针”：携带额外数据的指针，“折叠”到指针中，意味着内联存储在表示地址的数据中，利用内存寻址的某些属性。这是可能的，因为大多数架构将某些类型的数据与数据的大小对齐，通常是一个字或多个字。这种差异使得指针的一些最低有效位未被使用，这些位可以用于标记或保存其他信息——最常见的是作为位字段（每个位都是一个单独的标记）——只要使用指针的代码在访问内存之前屏蔽掉这些位。E、
例如，在32位体系结构（对于地址和字大小）上，一个字是32位=4字节，所以字对齐的地址总是4的倍数，因此以00结尾，剩下最后2位可用；而在64位体系结构中，一个字是64位＝8字节，所以字对齐的地址以000结尾，剩下最后3位可用。

之所以使用双重链接列表，是因为它们有效地支持最经常需要的操作。通常，GC跟踪的所有对象的集合都被划分为不相交的集合，每个集合都在其自己的双链接列表中。在集合之间，对象被划分为“几代”，反映了它们在集合尝试中存活的频率。在收集过程中，被收集的一代（一代）被进一步划分为，例如，可访问和不可访问对象的集合。双链接列表支持将一个对象从一个分区移动到另一个分区，添加一个新对象，完全删除一个对象（GC跟踪的对象通常在GC根本不运行时由引用计数系统回收！），以及合并分区，所有这些都需要少量的指针更新。小心地，它们还支持在向分区添加对象和从分区中删除对象时对分区进行迭代，这是GC运行时经常需要的。

提供了特定的API来分配、解除分配、初始化、跟踪和取消跟踪具有GC支持的对象。这些API可以在垃圾收集器C API文档中找到。

除了此对象结构之外，支持垃圾收集的对象的类型对象必须在其tp_flags槽中包含Py_TPFLAGS_HAVE_GC，并提供tp_traverse处理程序的实现。除非能够证明对象不能仅与其类型的对象形成引用循环，或者除非该类型是不可变的，否则还必须提供tp_clear实现。

识别参考循环

CPython用于检测这些参考周期的算法在gc模块中实现。垃圾收集器只专注于清理容器对象（即可以包含对一个或多个对象的引用的对象）。这些可以是数组、字典、列表、自定义类实例、扩展模块中的类等。人们可能会认为循环是不常见的，但事实是，解释器所需的许多内部引用到处都会创建循环。一些值得注意的例子：

异常包含包含包含异常本身的帧列表的回溯对象。
模块级函数引用模块的dict（解析全局所需），后者又包含模块级函数的条目。
实例具有对其类的引用，该类本身引用其模块，并且模块包含对内部所有内容（可能还有其他模块）的引用，这可以返回到原始实例。
当表示像图这样的数据结构时，它们与自己有内部链接是非常典型的。
要在这些对象无法访问时正确处理它们，需要首先识别它们。在标识周期的函数中，维护了两个双重链接的列表：一个列表包含所有要扫描的对象，另一个列表将包含所有“暂时”无法访问的对象。

为了理解算法的工作原理，让我们以一个循环链接列表为例，它有一个由变量a引用的链接和一个完全不可访问的自引用对象：

import gc

class Link:
   def __init__(self, next_link=None):
       self.next_link = next_link

link_3 = Link()
link_2 = Link(link_3)
link_1 = Link(link_2)
link_3.next_link = link_1
A = link_1
del link_1, link_2, link_3

link_4 = Link()
link_4.next_link = link_4
del link_4

# Collect the unreachable Link object (and its .__dict__ dict).
gc.collect()
2