用C语言实现的解释器中垃圾回收问题

4
我正在开发一个玩具过程化语言的编译器/解释器,已经实现了我计划探索的大部分功能,除了一个好的垃圾回收算法(类似于这个人)。我已经阅读了很多有关算法的资料,并且对如何实现它们有一个大致的想法。我的语言运行时的早期版本使用了引用计数,但我放弃了它以学习更高级的东西,因此我现在考虑使用标记和复制压缩算法。
开始时我遇到的第一个问题是防止算法在本地扩展函数(即用C编写的函数)中收集“对象”。根集包括解释器堆栈上的“对象”和符号表中的“对象”,这些我不应该有太多麻烦,然而,如果在C函数中创建一个容器“对象”,然后填充子“对象”,由于它实际上不在解释器堆栈上或绑定到符号,我该如何防止GC收集它们?
使GC实现变得更容易的事情:
  • 我语言中的所有“对象”都是内置类型(例如,不是面向对象的)
  • 解释器堆栈只是指向结构体的指针堆栈
  • 符号表只是指向结构体的指针数组
用户代码:
f = open('words.txt', 'r');
lines = readlines(f);
close(f);

解释器(在解析、编译为字节码之后):

  1. push 文件名, 打开模式
  2. 调用builtin_fopen函数,它返回一个封装了FILE*的结构体
  3. 将结果存储在符号f
  4. push 符号f
  5. 调用builtin_flines函数创建一个列表类型l,然后使用C语言的fread函数将文件的每一行作为字符串类型读取并附加到列表l
  6. 将结果存储在符号lines中,等等......

现在,如果在分配包含文件中一行的字符串时GC运行,则根集还没有任何对l的引用,因此l可能被回收。有什么更好的处理方式吗?


“标记和复制”--您可能是指标记和清除。您的解释器分配的所有对象都应该在它们自己的堆中,与扩展函数使用的堆分开。如果您想要GC扩展函数内存,您需要考虑类似于Boehm保守GC的东西。 - Jim Balter
我真的是指实现标记-压缩算法,它会复制可到达对象。这个想法是,扩展函数分配对象,这些对象旨在放置在解释器堆栈上和/或绑定到符号,并且因此应该在以后进行垃圾回收处理。 - joe
你可能会对我的问题感兴趣,链接在这里:https://dev59.com/41jUa4cB1Zd3GeqPP0vv。 - luser droog
我认为我的解决方案是结合了Chris Dodd、n.m.和Derek Pressnall的答案。n.m.保持特殊分配位于堆顶指针上方的方法很有用,但不能解决在本地函数执行过程中进行垃圾回收的问题。Chris Dodd为本地函数创建运行时接口以获取对象句柄的方法很棒,但Derek Pressnall实际上解释了如何做到这一点,通过将对象指针的引用传递给变异器。这个解释让我获得了50分。 - joe
4个回答

3
  1. 为解释器堆分配一个独立的连续内存块。不要在该内存块之外进行任何垃圾回收操作。
  2. 始终保留该内存块的当前顶部(假设其增长方向为从低地址到高地址)。顶部以上的所有空间都不可回收,但被视为根集合。如果内置函数需要分配多个链接对象,则将它们分配到顶部以上,然后将顶部上移,以便所有分配的对象一次性进入可回收的堆中。如果在函数执行过程中进行垃圾回收操作,则顶部以上的对象会一次性移动到新堆中。

这听起来像是一个好方法,但是如果在本地函数执行过程中发生集合,我不确定如何处理更新引用指针。 - joe

1
你需要为本地函数提供一个接口,通过该接口它们可以告诉垃圾回收器它们引用了哪些对象,然后让它们使用该接口。
最简单的方法可能是根本不让本地代码直接指向解释器/垃圾收集数据。相反,你给本地代码一个对象的句柄,并让它回调运行时从对象中获取值。在你的例子中,builtin_flines将调用运行时来分配一个列表并返回其句柄。然后它将读取行,并调用运行时将每个行附加到列表中,最后返回完整的列表。运行时将管理给定本机调用的所有句柄,在本机调用返回后释放它们。

我希望本地函数使用与解释器相同的API来分配新对象,例如LuciObject *list = LuciList_new()。是否将堆栈类型传递给所有本地函数并要求它们立即将分配的对象推送到堆栈上是不合理的?堆栈将可被解释器/垃圾回收器访问,以便将其包含在根集中。 - joe

1

由于我是你提到的原始“this”人,所以我可以根据我在项目中设计的内容为你提供一些关于你第一个问题的见解(我保证最终会在博客中写出来)。首先,所有的内存分配都通过一个变异函数进行。输入参数是你要创建的对象类型和一个指向它的指针类型对象的引用。然后,在创建新对象时,该指针对象将被更新。如果正在为解释器运行时的C函数独占使用分配对象,则它是根对象。在这种情况下,NULL作为第二个参数传递,并将对象添加到根对象列表中。现在,如果该内部函数不再需要该对象,则必须从根对象列表中删除该对象。(它不会自己销毁对象,因为垃圾回收例程最终会处理它)。哦,而解释器堆栈本身也是解释器中的一个对象(列表类型或数组类型对象),因此指向它的指针也在根对象列表中(另一个已知于解释器的列表类型对象)。指向根对象列表的指针是垃圾回收器需要知道的唯一指针。

此外,关于何时开始执行垃圾回收--由于现代架构上的内存实际上是无限制的,我决定在分配了X个对象后启动垃圾收集器。 运行后还剩下Y个对象。 如果Y仍然大于X的Z百分比,则将X增加足够多以使其达到该值。 然后我只希望malloc()永远不会失败(如果失败,则只需输出错误并退出解释器)。 希望这有所帮助,并希望其他人能添加更多澄清,因为当涉及到语言/解释器设计时,我更像是业余爱好者。

所以本质上,Object *tmp = alloc(obj_type, &tmp)。这使得收集器可以存储tmp的地址并在任何时候更改其值。老实说,我从未像这样玩过指针,但很不错。 - joe

-1

一些复杂情况:

当您输入要解释的行时,例如 100 if X then gosub 5000

但是5000尚不存在,您正在进行意大利面式编码... 也许x还没有被分配任何值或数据类型。 如果我们现在不建立索引,难道我们要等到有人 键入“run”或直接从提示符执行一行吗?

如果我们现在建立索引以加快后续速度,我们将如何 知道最后一个“100”、“X”或“5000”实例被 删除了?

在“事物”的主索引中我们应该做什么记录? 假设这些事物可能包括基本代码行、字符串和其他变量, 我们想通过名称或行号处理。

我们希望快速找到并用于战略性地识别 垃圾收集潜力,当需要收集时。

我们在可能会改变大小的事物索引上烧掉了多少静态空间?除了标签、位置和长度之外,哪些细节足够有用以证明索引是合理的?当一个变量缩小时,我们应该尝试索引空白空间吗?还是只索引变量的最大历史大小以及当前大小?我们如何识别那些最频繁改变大小的变量,并且我们应该避免清理它们,甚至故意填充它们吗?

什么时候我们才能清理整个混乱?或者只有清理足够的自由空间才能挤入无法通过侧面进入现有孔洞的东西更好?

有目的的延迟和等待“输入”似乎是我们可以利用来主动清理一些混乱的好目标。没有保证任何基本程序都会有这样的死时间。

很抱歉这不是一个答案,但原始问题似乎邀请我们对更好的方案进行头脑风暴。我们需要一个明确的策略,需要定义整个问题。


抱歉,但SO不是一个像你所说的头脑风暴的网站。这不是一个论坛,而是一个问答网站。我知道你没有足够的声望在任何地方发表评论,但这仍然不是你应该在SO上发布的回答的好例子。因为你是SO的新手,我不会对这个答案进行负面评价。 - markasoftware

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接