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

Question

我觉得我错过了一些非常简单的东西，但我试图根据 Andrew Appel 的 Modern Compiler Implementation in ML book 理解标记和清除垃圾收集，并且在标记和清除部分中有一小段标题为指针反转（270）。

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

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

Answer 1

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

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

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