1

我需要做一些liblisp（在 C11 中），它需要处理基本功能，就像libobjc对 Objective-C 语言所做的一样。

编辑

我将问题改写为不那么通用的问题。

我有一个这样的实现：

typedef struct cons {
  void *car, *cdr;
} *cons_t;

cons_t cons_init(void *, void *);
void *cons_get_car(cons_t);
void *cons_get_cdr(cons_t);
void cons_set_car(cons_t, void *);
void cons_set_cdr(cons_t, void *);
void cons_free(cons_t);
bool cons_is_managed(cons_t);

所以我可以制作一个 cons 单元（它使用一个带有引用计数对象的内存池）。我还可以cons_is_managed用来检查 cons 单元是否在内存池内（因此您可以使用外部定义的单元，而不是使用创建的单元cons_init（如静态数据）。

我怎样才能在这里有效地实现自动引用计数，如果有人调用cons_set_car，或者如果参数是托管的 cons 单元格cons_set_cdr，它将增加引用计数？void *

后宫和乌龟问题在这里没有用处，因为每个单元格都有两种可能的路径（如果 car 和 cdr 都是 conses，它可能无处可去），它们可以是列表、树或图形。

cons_set_car我可能应该注册在 on /中使用的外部（非托管）conses cons_set_cdr，以便找到涉及它们的循环，但我仍然不确定如何有效地做到这一点。

由于这是一个更受控制的上下文，然后是图中的一般循环（节点上最多两个顶点），我有没有机会在线性时间内做到这一点并避免垃圾收集（这将是我的计划 B）？

主要问题是这是任何函数式语言的核心，所以这些函数会被调用很多次（比如obj_msgSend），它们是瓶颈。

谢谢。

在另一种方法上，为了简化问题：如何在基于引用计数的语言（如 Objective-C + ARC 或 Vala）上实现 cons 单元？

4

1 回答 1

1

我假设您要实现的引用计数的主要目标是有效的垃圾收集（即使您说“避免垃圾收集”，很明显您的目标是实现自动内存管理）。

首先，我建议您考虑是否改用某种跟踪垃圾收集，例如大多数现代 Lisp 实现使用的。这与引用计数垃圾收集之间的基本区别是与内存的正负关系：使用引用计数，假设分配的元素是活动的，直到另有证明（通常通过图遍历算法）。通过跟踪，分配的元素被假定为垃圾，除非另有证明（通过来自对象根集的可访问性，例如 REPL 接口）。

是的，在运行标记和扫描算法时，您偶尔会受到显着的性能影响，但取决于您的库的目标用途，这可能是值得的。同样，如果您仔细管理线程，您可以让一个核心处理垃圾收集，而另一个继续执行。最有效的是混合策略，例如执行无法处理循环的“廉价”引用计数来处理高频简单情况，然后使用跟踪方法在循环垃圾累积时收集它。

至于如何有效地做到这一点......如果你想做引用计数，你需要每个缺点存储一个数字。为什么不将其存储在结构中？

typedef struct cons {
   void *car, *cdr;
   size_t reference_count;
} *cons_t;

如果采用混合策略，则可以在 O(n) 时间内处理地图中的列表处理、归约和递归函数等高频操作，其中 n 是要被垃圾收集的元素的数量。

于 2014-10-09T19:16:13.853 回答