reference-counting - 循环引用有哪些解决方案？

Question

使用引用计数时，有哪些可能的解决方案/技术来处理循环引用？

最著名的解决方案是使用弱引用，但是许多关于该主题的文章暗示还有其他方法，但不断重复弱引用示例。这让我想知道，这些其他方法是什么？

我不是在问引用计数的替代方法是什么，而是在使用引用计数时循环引用的解决方案是什么。
这个问题不是关于任何特定问题/实现/语言，而是一个一般性问题。

score 11 · Accepted Answer

多年来，我以十几种不同的方式研究了这个问题，而我发现每次都有效的唯一解决方案是重新设计我的解决方案以不使用循环引用。

编辑：

可以扩展吗？例如，当孩子需要了解/访问父母时，您将如何处理父子关系？–产科产科

正如我所说，唯一好的解决方案是避免此类构造，除非您使用可以安全处理它们的运行时。

也就是说，如果你必须有一个树/父子数据结构，孩子知道父母，你将不得不实现你自己的，手动调用的拆解序列（即外部你可能实现的任何析构函数）开始在根部（或您要修剪的分支处）并对树进行深度优先搜索以从叶子中删除引用。

它变得复杂和繁琐，因此 IMO 唯一的解决方案是完全避免它。

score 5 · Accepted Answer

这是我见过的解决方案：

为每个对象添加一个方法，告诉它释放对其他对象的引用，比如调用它 Teardown()。

然后，您必须知道谁“拥有”每个对象，并且对象的所有者在使用完对象后必须对其调用 Teardown()。

如果有一个循环引用，比如 A <-> B，并且 C 拥有 A，那么当 C 的 Teardown() 被调用时，它会调用 A 的 Teardown，它在 B 上调用 Teardown，B 然后释放它对 A 的引用，A 然后释放它对 B 的引用（破坏 B），然后 C 释放它对 A 的引用（破坏 A）。

score 2 · Accepted Answer

将事物放入层次结构

弱引用是一种解决方案。我知道的唯一其他解决方案是避免一起循环拥有引用。如果您有指向对象的共享指针，那么这在语义上意味着您以共享方式拥有该对象。如果仅以这种方式使用共享指针，则几乎无法获得循环引用。对象以循环方式彼此拥有的情况并不经常发生，相反，对象通常通过分层树状结构连接。这就是我接下来要描述的情况。

处理树木

如果您有一棵树，其对象具有父子关系，则子对象不需要对其父对象的拥有引用，因为无论如何父对象都会比子对象寿命长。因此，一个非拥有的原始反向指针就可以了。这也适用于指向它们所在容器的元素。如果可能，容器应该尽可能使用唯一指针或值而不是共享指针。

模拟垃圾收集

如果您有一堆可以相互指向对方的对象，并且您想在某些对象无法访问时立即清理，那么您可能需要为它们构建一个容器和一个根引用数组以进行垃圾处理手动收集。

使用唯一指针、原始指针和值

在现实世界中，我发现共享指针的实际用例非常有限，应该避免使用唯一指针、原始指针，或者——甚至更好——只是值类型。当您有多个指向共享变量的引用时，通常使用共享指针。共享会引起摩擦和争吵，如果可能的话，应该首先避免。唯一指针和非拥有的原始指针和/或值更容易推理。但是，有时需要共享指针。共享指针也用于延长对象的生命周期。这通常不会导致循环引用。

底线

谨慎使用共享指针。更喜欢唯一指针和非拥有的原始指针或纯值。共享指针表示共享所有权。以这种方式使用它们。在层次结构中排序您的对象。层次结构中同一级别的子对象或对象不应使用对彼此或其父对象的拥有共享引用，而应使用非拥有原始指针。

score 2 · Accepted Answer

我猜垃圾收集器使用的另一种方法是“标记和清除”：

在每个对象实例中设置一个标志
遍历每个可访问实例的图形，清除该标志
每个仍然设置了标志的剩余实例都是不可访问的，即使其中一些实例相互之间具有循环引用。

score 2 · Accepted Answer

我想建议一种我想到的稍微不同的方法，我不知道它是否有任何正式名称：

对象本身没有引用计数器。相反，一个或多个对象的组对整个组有一个引用计数器，它定义了组中所有对象的生命周期。

以类似的方式，引用与对象共享组，或属于空组。

仅当对象的（引用）在组外部时，对对象的引用才会影响（对象的）组的引用计数。

如果两个对象形成一个循环引用，它们应该成为同一个组的一部分。如果两个组创建循环引用，则应将它们合并为一个组。

更大的组允许更多的参考自由，但组中的对象在不需要时更有可能保持活力。

score 1 · Accepted Answer

没有人提到有一整类收集循环的算法，不是通过标记和扫描来寻找不可收集的数据，而只是通过扫描一小部分可能的循环数据，检测其中的循环并在没有全扫。

为了增加更多细节，制作一组可能的节点进行扫描的一个想法是那些引用计数减少但在减少时没有变为零的节点。只有发生这种情况的节点才能成为从根集中切断循环的点。

Python 有一个收集器可以做到这一点，PHP 也是如此。

我仍在尝试了解该算法，因为有些高级版本声称能够在不停止程序的情况下并行执行此操作...

无论如何，这并不简单，它需要多次扫描，一组额外的引用计数器，并在“试验”中减少元素（在额外的计数器中），以查看自引用数据是否最终可收集。

一些论文：“Down for the Count？Getting Reference Counting Back in the Ring”Rifat Shahriyar、Stephen M. Blackburn 和 Daniel Frampton http://users.cecs.anu.edu.au/~steveb/downloads/pdf/rc- ismm-2012.pdf David F. Bacon、Perry Cheng 和 VT Rajan 的“垃圾收集统一理论” http://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf

引用计数还有更多主题，例如减少或摆脱引用计数中的互锁指令的奇异方法。我能想到3种方法，其中2种已经写出来了。

score 0 · Accepted Answer

i too am looking for a good solution to the circularly reference counted problem.

i was ~~stealing~~ borrowing an API from World of Warcraft dealing with achievements. i was implicitely translating it into interfaces when i realized i had circular references.

Note: You can replace the word achievements with orders if you don't like achievements. But who doesn't like achievements?

There's the achievement itself:

IAchievement = interface(IUnknown)
   function GetName: string;
   function GetDescription: string;
   function GetPoints: Integer;
   function GetCompleted: Boolean;

   function GetCriteriaCount: Integer;
   function GetCriteria(Index: Integer): IAchievementCriteria;
end;

And then there's the list of criteria of the achievement:

IAchievementCriteria = interface(IUnknown)
   function GetDescription: string;
   function GetCompleted: Boolean;
   function GetQuantity: Integer;
   function GetRequiredQuantity: Integer;
end;

All achievements register themselves with a central IAchievementController:

IAchievementController = interface
{
   procedure RegisterAchievement(Achievement: IAchievement);
   procedure UnregisterAchievement(Achievement: IAchievement);
}

And the controller can then be used to get a list of all the achievements:

IAchievementController = interface
{
   procedure RegisterAchievement(Achievement: IAchievement);
   procedure UnregisterAchievement(Achievement: IAchievement);

   function GetAchievementCount(): Integer;
   function GetAchievement(Index: Integer): IAchievement;
}

The idea was going to be that as something interesting happened, the system would call the IAchievementController and notify them that something interesting happend:

IAchievementController = interface
{
   ...
   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
}

And when an event happens, the controller will iterate through each child and notify them of the event through their own Notify method:

IAchievement = interface(IUnknown)
   function GetName: string;
   ...

   function GetCriteriaCount: Integer;
   function GetCriteria(Index: Integer): IAchievementCriteria;

   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
end;

If the Achievement object decides the event is something it would be interested in it will notify its child criteria:

IAchievementCriteria = interface(IUnknown)
   function GetDescription: string;
   ...
   procedure Notify(eventType: Integer; gParam: TGUID; nParam: Integer);
end;

Up until now the dependancy graph has always been top-down:

 IAchievementController --> IAchievement --> IAchievementCriteria

But what happens when the achievement's criteria have been met? The Criteria object was going to have to notify its parent `Achievement:

 IAchievementController --> IAchievement --> IAchievementCriteria
                                    ^                      |
                                    |                      |
                                    +----------------------+

Meaning that the Criteria will need a reference to its parent; the who are now referencing each other - memory leak.

And when an achievement is finally completed, it is going to have to notify its parent controller, so it can update views:

 IAchievementController --> IAchievement --> IAchievementCriteria
      ^                      |    ^                      |
      |                      |    |                      |                                        
      +----------------------+    +----------------------+

Now the Controller and its child Achievements circularly reference each other - more memory leaks.

i thought that perhaps the Criteria object could instead notify the Controller, removing the reference to its parent. But we still have a circular reference, it just takes longer:

 IAchievementController --> IAchievement --> IAchievementCriteria
      ^                      |                          |
      |                      |                          |                                        
      +<---------------------+                          |
      |                                                 |
      +-------------------------------------------------+

The World of Warcraft solution

Now the World of Warcraft api is not object-oriented friendly. But it does solve any circular references:

Do not pass references to the Controller. Have a single, global, singleton, Controller class. That way an achievement doesn't have to reference the controller, just use it.

Cons: Makes testing, and mocking, impossible - because you have to have a known global variable.
An achievement doesn't know its list of criteria. If you want the Criteria for an Achievement you ask the Controller for them:
```
 IAchievementController = interface(IUnknown)
     function GetAchievementCriteriaCount(AchievementGUID: TGUID): Integer;
     function GetAchievementCriteria(Index: Integer): IAchievementCriteria;
 end;
```
Cons: An Achievement can no longer decide to pass notifications to it's Criteria, because it doesn't have any criteria. You now have to register Criteria with the Controller

When a Criteria is completed, it notifies the Controller, who notifies the Achievement:

 IAchievementController-->IAchievement      IAchievementCriteria
      ^                                              |
      |                                              |
      +----------------------------------------------+

Cons: Makes my head hurt.

i'm sure a Teardown method is much more desirable that re-architecting an entire system into a horribly messy API.

But, like you wonder, perhaps there's a better way.

score 0 · Accepted Answer

使用引用计数时，有哪些可能的解决方案/技术来处理循环引用？

三种解决方案：

使用循环检测器增强朴素引用计数：递减到非零值的计数被认为是潜在的循环源，并且在它们周围的堆拓扑中搜索循环。
使用像标记扫描这样的传统垃圾收集器来增强天真的引用计数。
限制语言，使其程序只能产生非循环（也称为单向）堆。Erlang 和 Mathematica 就是这样做的。
用字典查找替换引用，然后实现您自己的可以收集循环的垃圾收集器。

score 0 · Accepted Answer

我一直在重新设计以避免这个问题。出现这种情况的常见情况之一是孩子需要了解父母的父子关系。有2个解决方案

将父级转换为服务，然后父级不知道子级，并且当没有更多子级或主程序删除父级引用时父级死亡。
如果父级必须可以访问子级，则在父级上有一个 register 方法，该方法接受一个不被引用计数的指针，例如一个对象指针，以及一个相应的 unregister 方法。孩子需要调用 register 和 unregister 方法。当父级需要访问子级时，它会将对象指针类型转换为引用计数接口。

score 0 · Accepted Answer

如果您需要存储循环数据，将快照转换为字符串，

我将一个循环布尔值附加到任何可能是循环的对象上。

第 1 步：将数据解析为 JSON 字符串时，我将任何未使用的 object.is_cyclic 推送到数组中，并将索引保存到字符串中。（任何使用的对象都将替换为现有索引）。

第 2 步：我遍历对象数组，将任何 children.is_cyclic 设置为指定索引，或将任何新对象推送到数组。然后将数组解析为 JSON 字符串。

注意：通过将新的循环对象推到数组的末尾，将强制递归，直到所有循环引用都被删除。

第 3 步：最后我将两个 JSON 字符串解析为一个字符串；

这是一个javascript小提琴...... https://jsfiddle.net/7uondjhe/5/

function my_json(item) {

var parse_key = 'restore_reference', 
    stringify_key = 'is_cyclic';

var referenced_array = [];


var json_replacer = function(key,value) {

            if(typeof value == 'object' && value[stringify_key]) {
                var index = referenced_array.indexOf(value);

                if(index == -1) {
                    index = referenced_array.length;
                    referenced_array.push(value);
                };

                return {
                    [parse_key]: index
                }
            }
            return value;
}

var json_reviver = function(key, value) {

        if(typeof value == 'object' && value[parse_key] >= 0) {
                return referenced_array[value[parse_key]];
        }
        return value;
}
var unflatten_recursive = function(item, level) {
        if(!level) level = 1;
        for(var key in item) {
            if(!item.hasOwnProperty(key)) continue;
            var value = item[key];

            if(typeof value !== 'object') continue;

            if(level < 2 || !value.hasOwnProperty(parse_key)) {
                unflatten_recursive(value, level+1);
                continue;
            }

            var index = value[parse_key];
            item[key] = referenced_array[index];

        }
};


var flatten_recursive = function(item, level) {
        if(!level) level = 1;
        for(var key in item) {
            if(!item.hasOwnProperty(key)) continue;
            var value = item[key];

            if(typeof value !== 'object') continue;

            if(level < 2 || !value[stringify_key]) {
                flatten_recursive(value, level+1);
                continue;
            }

            var index = referenced_array.indexOf(value);

            if(index == -1) (item[key] = {})[parse_key] = referenced_array.push(value)-1; 
            else (item[key] = {})[parse_key] = index;
        }
};


return {

    clone: function(){ 
        return JSON.parse(JSON.stringify(item,json_replacer),json_reviver)
},

    parse: function() {
            var object_of_json_strings = JSON.parse(item);
            referenced_array = JSON.parse(object_of_json_strings.references);
            unflatten_recursive(referenced_array);
            return JSON.parse(object_of_json_strings.data,json_reviver);
    },

    stringify: function() {
            var data = JSON.stringify(item,json_replacer);
            flatten_recursive(referenced_array);
            return JSON.stringify({
                        data: data,
                        references: JSON.stringify(referenced_array)
                });
    }
}
}

score -4 · Accepted Answer

我知道有几种方法可以绕过这个：

第一个（也是首选）只是将公共代码提取到第三个程序集中，并使两个引用都使用那个

第二个是将引用添加为“文件引用”（dll）而不是“项目引用”

希望这可以帮助

reference-counting - 循环引用有哪些解决方案？

11 回答 11

将事物放入层次结构

处理树木

模拟垃圾收集

使用唯一指针、原始指针和值

底线

The World of Warcraft solution

Related

Reference