pointers - 标记和清除垃圾收集中的指针反转会给您带来什么？

Question

我觉得我错过了一些非常简单的东西，但我试图根据 Andrew Appel 的《ML 中的现代编译器实现》一书来理解标记和清除垃圾收集，并且标记和清除部分中有一个小段落，标题为“指针反转”(270)。

现在我想我明白它是如何工作的了。简而言之，当您遍历图表时，您会翻转所有指针，以便您的前任位于您的字段集内。然后，当您完成给定元素时，将指针翻转回来，以便它们再次指向正确的位置。

如果这是正确的，它到底能给你带来什么？阿佩尔试图解释这一点，但我并没有完全理解他的措辞。

Answer 1

在标记过程中，对象分为三类:

1. 未标记的对象
2. 已标记的对象，但可以指向未标记的对象
3. 已标记的对象，仅指向已标记的对象

随着标记的进行，对象的状态从类别 1 更改为类别 2，从类别 2 更改为类别 3。垃圾收集器必须跟踪类别 2 中的所有对象，以便它可以找到所有未标记的对象。但它在哪里存储这些信息呢？垃圾收集可能在内存完全满时运行，因此它无法动态分配数据结构。它应该使用已分配的内存构建一个保存类别 2 中的对象的数据结构。指针反转是一种在不分配内存的情况下构建这些对象的链表的算法。