当成对实现停止和复制垃圾收集器时，我需要两个内存库（旧的和一个免费的新的）。一个内存库由-cars 和-cdrs 组成。所以基本上当我创建一个新地址时，它是一个指向 the-cars 和 the-cdrs 的指针。
当分配新内存时，我发现我没有足够的空间，我启动了一个 GC。这个做的是：
现在的问题是：为什么我需要先扫描然后再移动。为什么我不能两者一起做？
听起来您正在经历非常棒的垃圾收集任务，您可以在其中实现自己的收集器（标记和清除、停止和复制、分代）。
对您的问题的一般回答：通过以时间换空间，两次算法通常比一次算法使用更少的内存。
更具体的答案：在停止和复制收集器中，您分两遍执行此操作：（1）首先将实时数据复制到新的半空间，以及（2）调整实时数据中的内部引用以引用新的半空间，将旧内存映射到新内存。
您必须意识到，进行映射所需的信息并非神奇地可用：您需要内存来跟踪如何重定向移动的内存。请记住：您的收集器本身就是一个程序，它必须使用有限的少量内存！例如，在您的收集器中保留一个哈希表来进行簿记将是禁止的：它不符合规则。因此，您需要跟踪的一件事是确保收集器正在使用有限的内存。这就解释了为什么停止复制收集器将重用旧的半空间并将那些重定向记录写在那里。
考虑到这个限制：重要的是要意识到我们需要小心我们如何遍历现场。我们选择哪种方法可能需要也可能不需要额外的内存，以一些非常微妙和令人惊讶的方式。特别是，一般情况下的递归不是免费的！从技术上讲，在第一遍中，我们不仅应该使用新的半空间作为我们复制的目标，而且作为我们用来实现遍历实时数据的递归过程的控制堆栈的时髦表示。
具体来说，如果我们使用这样的一次性方法来复制实时集：
;; copy-live-set: number -> void
;; copies the live set starting from memory-location.
Pseudocode:
to copy-live-set starting at memory-location:
copy the block at memory-location over to the new semispace, and
record a redirection record in the old semispace
for each internal-reference in the block:
recursively call copy-live-set at the internal-reference if
it hasn't been copied already
remap the internal-reference to that new memory location
那么你可能会惊讶地发现我们搞砸了记忆。以上将破坏收集器对运行时环境做出的承诺，因为这里的递归不是迭代的！它将消耗控制堆栈空间。在实时集遍历期间，它将消耗与我们正在遍历的结构的深度成比例的控制堆栈空间。哎呀。
如果您尝试另一种方法来遍历活动集，您最终应该会看到有一种很好的方法可以遍历整个活动集，同时仍然保证有限的、小的控制堆栈使用。提示：考虑如何将图遍历算法编写为一个简单的 while 循环，并使用一个显式容器来保存接下来要访问的内容，直到我们耗尽容器。如果你眯着眼睛看，新半空间中的中间值看起来非常像那个容器。
一旦您发现如何在恒定控制堆栈空间中遍历活动集，您就会发现您需要这两个通道来完成完整的复制和重写内部引用的事情。担心这些细节很麻烦，但了解垃圾收集器的实际工作方式很重要。一个真正的收集器需要做这样的事情，关注控制堆栈的使用，以确保它在收集期间使用有限的内存。
总结：两遍算法是一种以一些时间为代价帮助我们处理内存的解决方案。但是我们在性能方面付出的并不多：虽然我们两次通过 live set，但这个过程在 live set 的大小上仍然是线性的。
历史：参见Cheney's Algorithm，并注意开创性论文重点的标题：“ A Nonrecursive List Compacting Algorithm ”。那个突出显示的单词“非递归”是激发两遍方法的关键：它试图避免消耗控制堆栈。Cheney 的论文是 Fenichel 和 Yochelson 的论文“ A LISP Garbage-Collector for Virtual-Memory Computer Systems ”的扩展，其中作者首先提出了递归、堆栈使用的方法。为了改善这种情况，Fenichel 和 Yochelson 随后提出使用非递归（但复杂！）Schorr-Waite DFS 算法进行遍历。Cheney 的方法是一种改进，因为遍历更简单。