c - 如何有效地引用count cons cells(检测周期)？

Question

我需要做一些 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_set_cdr 它会增加引用计数，如果 void * 参数是一个托管的 cons 单元？

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

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

由于这是一个比图形中的一般循环(一个节点上最多两个顶点)更受控制的上下文，我是否有机会在线性时间内完成此操作并避免垃圾收集(这将是我的计划 B)？

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

谢谢。

---

在另一种方法上，为了简化问题:如何在基于引用计数的语言(例如 Objective-C + ARC 或 Vala)上实现 cons cell？

Answer 1

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

首先，我建议您考虑是否改用某种 tracing garbage collection ，例如大多数现代 Lisp 实现所使用的。它与引用计数垃圾回收之间的基本区别是与内存的正相关与负相关:使用引用计数，分配的元素被假定为事件的，直到证明不是这样(通常通过图形遍历算法)。通过跟踪，分配的元素被假定为垃圾，直到证明不是这样(通过从根对象集(例如 REPL 接口(interface))的可达性)。

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

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

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

如果采用混合策略，则可以在 O(n) 时间内处理 map 中的列表处理、缩减和递归函数等高频操作，其中 n 是要进行垃圾回收的元素数。