垃圾收集和运行时间类型信息

Question

The fixnum question让我想起了另一个我很久以来想知道的问题。

许多关于垃圾收集的在线资料并没有说明如何实现运行时类型信息。因此，我知道很多关于垃圾收集器的事情，但并不是真的关于如何实施它们。

fixnum解决方案其实很不错，很清楚哪个值是指针，哪个不是。还有哪些常用的存储类型信息的解决方案？

另外，我想知道fixnum -thing。这并不意味着你被限制在每个数组索引上的fixnums吗？或者有什么解决方法可以获得完整的64位整数？

Answer 1

基本上，要实现准确的标记，您需要元数据指示哪些字用作指针，哪些不是。

这个元数据可以像emacs一样存储在每个引用中。如果您的语言/实现不关心内存使用，甚至可以使引用大于单词（可能是单词的两倍），以便每个引用都可以携带类型信息以及单字数据。这样，你可以有一个32位指针的全部大小的fixnum，代价是引用都是64位。

或者，元数据可以与其他类型信息一起存储。因此，例如，一个类可以像通常的函数指针表一样包含数据布局的每个字的一位，指示该单词是否包含垃圾收集器应该遵循的引用。如果你的语言具有虚拟调用，那么你必须已经有了一种方法来从一个对象中得出使用哪个函数地址，所以相同的机制将允许你计算出使用什么标记数据 - 通常你在其中添加一个额外的秘密指针每个对象的开始，指向构成其运行时类型的类。显然，对于某些动态语言，指向的类型数据需要进行写入时拷贝，因为它是可修改的。

堆栈可以做类似的操作 - 将准确的标记信息存储在代码本身的数据段中，并让垃圾回收器检查存储的程序计数器和/或堆栈上的链接指针和/或其他信息由代码堆栈为目的，确定每个堆栈的哪些代码与哪个代码相关，因此哪些是指针。轻量级异常机制倾向于做类似的事情来存储有关代码中try/catch发生位置的信息，当然调试器也需要能够解释堆栈，所以这很可能与其他一些东西叠加在一起你已经在努力实现任何语言，包括内置垃圾回收的语言。

请注意，垃圾收集不一定需要准确的标记。你可以把每一个单词当作一个指针，不管它是否真的存在，都可以在你的垃圾收集器的“所有东西的大列表”中查找它，以决定它是否可以引用尚未标记的对象，以及如果所以请将其视为对该对象的引用。这很简单，但是成本当然是在“非常慢”和“非常慢”之间，取决于你的gc用于查找的数据结构。此外，有时一个整数恰好与未引用对象的地址具有相同的值，并导致您保留应该收集的大量对象。所以这样一个垃圾收集器不能提供有关未被收集的未引用对象的强有力的保证。对于玩具实施或第一个工作版本，这可能没问题，但不太可能受到用户的欢迎。

混合的方法可能会对物体进行精确的标记，而不是堆栈中特别多毛的区域。例如，如果您编写的JIT可以创建代码，其中引用的对象地址只出现在寄存器中，而不是出现在通常的堆栈槽中，那么您可能需要非正确地遵循操作系统存储寄存器时堆栈的区域取消预定有问题的线程来运行垃圾回收器。这可能非常复杂，所以合理的方法（可能导致代码较慢）将要求JIT始终保留它在精确标记的堆栈上使用的所有指针值的副本。

Answer 2

在吱吱声中（还有Scheme和许多其他动态语言，我猜）你有SmallInteger，有符号的31位整数的类，以及任意大整数的类。 LargePositiveInteger。很可能有其他的表示方式，64位的整数或者作为完整的对象或者一些位，如“我不是指针”标志。

但算术方法被编码来处理溢出/不足流量，例如，如果您向SmallInteger maxVal添加一个，则会得到2^30 + 1作为LargePositiveInteger的一个实例，并且如果您从中减去一个，则会得到返回2^30作为SmallInteger。