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

Question

fixnum问题让我想到了另一个问题问题我好久都想知道了。

许多关于垃圾收集的在线资料并未说明如何实现运行时类型信息。因此，我对各种各样的垃圾收集器了解很多，但实际上我并不知道如何实现它们。

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

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

Answer 1

基本上为了获得准确的标记，您需要元数据来指示哪些单词用作指针而哪些单词不用。

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

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

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

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

例如，混合方法可以对物体进行准确的标记，但不会对物体特别毛茸茸的堆叠区域进行准确标记。例如，如果您编写的JIT可以创建代码，其中引用的对象地址仅出现在寄存器中，而不是通常的堆栈槽中，那么您可能需要非准确地跟踪操作系统存储寄存器的堆栈区域。计划了有问题的线程来运行垃圾收集器。这可能非常繁琐，因此合理的方法（可能导致代码更慢）将要求JIT始终保留其在准确标记的堆栈上使用的所有指针值的副本。

Answer 2

在Squeak（也就是Scheme和其他许多动态语言）中你有 SmallInteger ，有符号的31位整数类，以及任意大整数的类，例如： <代码> LargePositiveInteger 。很可能还有其他表示，64位的整数或者作为完整对象，或者有几个位作为“我不是指针”。标志。

但是算术方法被编码为处理过流/欠流，这样如果你向 SmallInteger maxVal 添加一个，你得到2 ^ 30 + 1作为 LargePositiveInteger的一个实例，如果你从中减去一个，你将得到2 ^ 30作为 SmallInteger 。