use*_*611 4 garbage-collection racket
当实现一个停止和复制垃圾收集器作为一对时,我需要两个存储库(旧的和新的一个).一个存储库由汽车和磁带组成.所以基本上当我创建一个新的地址时,它是指向汽车和-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循环,并使用一个显式容器来保存接下来要访问的容器,直到我们耗尽容器.如果你恰到好处地斜视,新半空间中的中间值看起来非常像那个容器.
一旦你发现如何在常量控制堆栈空间中遍历实时集,你就会发现你需要这两个遍来完成copy-and-rewrite-internal-references的完整复制.担心这些细节很麻烦,但是看看垃圾收集者的实际工作方式非常重要.一个真正的收集器需要做这样的事情,关注控件堆栈的使用,以确保它在收集过程中使用有界内存.
总结:双遍算法是一种能够以一段时间为代价帮助我们获取内存的解决方案.但是我们在性能方面付出的代价并不高:虽然我们两次通过实时集,但这个过程在实时集的大小上仍然是线性的.
历史:看到切尼的算法,并注意开创性的论文强调的标题:" 一个非递归列表压实算法 ".单个突出显示的单词"Nonrecursive"是激发双程方法的关键:它试图避免消耗控制堆栈.切尼的论文是Fenichel和Yochelson撰写的" 用于虚拟内存计算机系统的LISP垃圾收集器 "的论文的扩展,其中作者首先提出了基本上使用递归,堆栈的方法.为了改善这种情况,Fenichel和Yochelson随后建议使用非递归(但复杂!)的Schorr-Waite DFS算法来进行遍历.切尼的方法是一种改进,因为遍历更简单.