c++ - 垃圾收集器 : data structure of the object graph

Question

我阅读了很多关于垃圾收集的资源，他们在其中解释了不同的算法。但是，我没有找到任何解释图形对象表示的内容。

我的想法很简单:一个有向图，其中顶点代表分配的内存块(在堆上)，边代表所有者关系。示例:考虑 2 个内存块 m1 和 m2，如果 m1 包含对 m2 内部 block 的引用，则添加一条边 (m1, m2)。这些边用 m1 包含的对 m2 的引用数加权(此处仅为 1)。最后我得到了一个代表堆栈的“虚拟”内存顶点，称之为 M0。从 M0 可达的每个 Mi 都不能被垃圾收集。

好的，现在考虑要向图中添加一个内存块。如果我们将顶点保存在一个集合中，那么添加一个内存块的复杂度应该是 O(log(n))。第一个问题:我们可以做得更好吗？

同上删除。

现在，我被要求将此算法与 C++ 中的引用计数机制 (shared_ptr) 结合使用。首先，引用计数器是否与顶点的入度无关？

其次，关键思想是使用最好的引用计数器(O(1) 删除/添加)和最好的垃圾收集器算法(清理引用循环)，但是添加/删除每个节点的开销在对象图中是不是有点低效？

在已知的垃圾收集器(java/C#/...)中添加/删除的复杂性是什么？

谢谢!

Answer 1

好吧……你的前提不对。已知的垃圾收集器实际上并没有维护太多状态，每个对象和某些结构最多维护几个位，但仅此而已。相反，他们在每个收集 channel 建立一些状态，并让它在 channel 结束时消亡。这样，他们几乎不需要(甚至不需要)所有权关系的工具。