如何有效地引用计数单元格(检测周期)？
我需要做一些liblisp (在C11中)，它需要处理基本的函数，就像libobjc对Objective语言所做的一样。
编辑
我要把这个问题改写成一个不那么普通的问题。
我得到了这样的实现：
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_is_managed来检查cons单元是否在内存池内(因此您可以使用外部定义的单元格，而不是用cons_init创建的单元格(比如静态数据)。
我如何在这里有效地实现自动引用计数，如果有人调用cons_set_car或cons_set_cdr，如果void *参数是托管cons单元格，它就会增加引用计数。
在这里，harem和tortoise问题不会有用，因为每个单元格都有两种可能的方法(如果car或cdr是干果，它可能去不了任何地方)，它们可以是列表、树或图表。
我可能应该注册在cons_set_car/cons_set_cdr上使用的外部(非托管)会话，以便找到涉及它们的周期，但我仍然不知道如何有效地完成这些任务。
由于这是一个比图中的一般循环更受控制的上下文(节点上两个顶点的最大值)，我是否有可能在线性时间内这样做，并避免垃圾收集(这将是我的计划B)？
主要的问题是，这是任何函数语言的核心，因此这些函数将被称为(许多时代的(如obj_msgSend) )，它们是的瓶颈。
谢谢。
在另一种方法上，简化问题:如何在一种基于引用计数的语言上实现一个反单元格，比如目标C+ ARC或Vala？
回答 1
Stack Overflow用户
发布于 2014-10-09 11:16:13
我假设您要实现的引用计数的主要目标是高效的垃圾收集(即使您说“避免垃圾收集”，但很明显您的目标是实现自动内存管理)。
首先，我建议您考虑是否改用某种类型的跟踪垃圾收集，例如大多数现代的Lisp实现使用。这与引用计数垃圾收集之间的基本区别是与内存的正关系和负关系:对于引用计数，分配的元素被假定为活动元素，直到证明并非如此为止(通常通过图遍历算法)。通过跟踪，分配的元素被假定为垃圾元素，直到事实证明并非如此(通过从对象的根集合(如REPL接口)获得可达性)。
是的，当标记和扫描算法运行时，您可能偶尔会受到显著的性能影响，但取决于您在库中的目标用途，这可能是值得的。类似地，如果您仔细地管理线程，则可以有一个核心处理垃圾收集，而另一个则继续执行。最有效的是混合策略，比如执行一个“廉价”的引用计数，它不能处理周期来处理高频的简单情况，然后使用跟踪方法来收集循环垃圾。
至于如何有效地.如果您想要进行引用计数，则需要存储每个密码的一个数字。为什么不直接把它储存在结构里呢？
typedef struct cons {
void *car, *cdr;
size_t reference_count;
} *cons_t;如果采用混合策略，则可以在O(n)时间内处理映射中的列表处理、约简和递归函数等高频操作，其中n是要收集的元素数。
https://stackoverflow.com/questions/19142499
复制
腾讯云开发者
