c++ - `std::shared_ptr`自动循环断路器的可行性

Question

C++11 引入了引用计数智能指针，std::shared_ptr。由于引用计数，这些指针无法自动回收循环数据结构。然而，引用循环的自动收集被证明是可能的，例如通过 Python 和 PHP 。为了将此技术与垃圾收集区分开来，问题的其余部分将其称为循环中断。

鉴于似乎没有向 C++ 添加等效功能的提议，是否存在一个根本原因，为什么与其他语言中已经部署的循环断路器类似的循环断路器不适用于 std::shared_ptr ？

请注意，这个问题并没有归结为“为什么没有 C++ GC”，即 has been asked before 。 C++ GC 通常是指自动管理所有动态分配对象的系统，通常使用某种形式的 Boehm 保守收集器来实现。 pointed out 认为这样的收集器与 RAII 不匹配。由于垃圾收集器主要管理内存，在内存不足之前甚至可能不会被调用，而 C++ 析构函数管理其他资源，依赖 GC 运行析构函数最多会引入不确定性，最坏的情况是资源匮乏。 bee 还指出，在存在更明确和可预测的智能指针的情况下，完全不需要 GC。

然而，基于库的智能指针循环中断器(类似于引用计数解释器使用的循环中断器)与通用 GC 有重要区别:

只关心通过 shared_ptr 管理的对象。此类对象已经参与共享所有权，因此必须处理延迟的析构函数调用，其确切时间取决于所有权结构。

由于范围有限，循环中断器不关心破坏或减慢 Boehm GC 的模式，例如指针屏蔽或包含偶尔指针的巨大不透明堆块。

可以选择加入，例如 std::enable_shared_from_this 。不使用它的对象不必为控制块中的额外空间付费来保存循环断路器元数据。

循环断路器不需要“根”对象的完整列表，这在 C++ 中很难获得。与查找所有事件对象并丢弃其余对象的标记-清除 GC 不同，循环断路器仅遍历可以形成循环的对象。在现有实现中，该类型需要以函数的形式提供帮助，该函数枚举对可以参与循环的其他对象的引用(直接或间接)。

它依靠常规的“当引用计数下降到零时销毁”语义来销毁循环垃圾。一旦确定了一个循环，就会要求参与它的对象清除它们的强引用，例如通过调用 reset() 。这足以打破循环并自动销毁对象。要求对象提供并清除其强引用(根据请求)可确保循环中断器不会破坏封装。

缺乏自动循环中断的建议表明该想法因实际或哲学原因而被拒绝。我很好奇原因是什么。为完整起见，以下是一些可能的反对意见:

“它会引入对循环 shared_ptr 对象的非确定性破坏。”如果程序员控制循环中断器的调用，它就不会是不确定的。此外，一旦被调用，循环破坏器的行为将是可预测的——它会破坏所有当前已知的循环。这类似于 shared_ptr 析构函数在其引用计数降至零后销毁底层对象的方式，尽管这可能导致“非确定性”级联进一步破坏。

“循环断路器，就像任何其他形式的垃圾收集一样，会在程序执行中引入暂停。”使用实现此功能的运行时的经验表明，暂停是最小的，因为 GC 仅处理循环垃圾，并且所有其他对象都通过引用计数回收。如果循环检测器从未被自动调用，循环中断器的“暂停”可能是运行它的可预测结果，类似于销毁大型 std::vector 可能会运行大量析构函数。 (在 Python 中，循环 gc 是自动运行的，但是在不需要它的代码部分中临时有 API 到 disable it。稍后重新启用 GC 将拾取在此期间创建的所有循环垃圾。)

“循环断路器是不必要的，因为循环不是那么频繁，使用 std::weak_ptr 可以轻松避免。”事实上，循环在许多简单的数据结构中很容易出现——例如一棵树， child 有一个指向父的反向指针，或一个双向链表。在某些情况下，复杂系统中异构对象之间的循环只是偶尔以特定模式的数据形成，并且难以预测和避免。在某些情况下，用弱变体替换哪个指针并不明显。

Answer 1

这里有很多问题需要讨论，所以我重写了我的帖子以更好地浓缩这些信息。

自动循环检测

你的想法是有一个 circle_ptr 智能指针(我知道你想把它添加到 shared_ptr ，但谈论一种新类型来比较两者更容易)。这个想法是，如果智能指针绑定(bind)的类型来自某个 cycle_detector_mixin ，这将激活自动循环检测。

这个 mixin 还要求类型实现一个接口(interface)。它必须能够枚举该实例直接拥有的所有 circle_ptr 实例。并且它必须提供使其中之一无效的方法。

我认为这是一个非常不切实际的解决方案。它非常脆弱，需要用户进行大量的手动工作。因此，它不适合包含在标准库中。以下是一些原因。

确定性和成本

"It would introduce non-deterministic destruction of cyclic shared_ptr objects." Cycle detection only happens when a shared_ptr's reference count drops to zero, so the programmer is in control of when it happens. It would therefore not be non-deterministic. Its behavior would be predictable - it would destroy all currently known cycles from that pointer. This is akin to how shared_ptr destructor destroys the underlying object once its reference count drops to zero, despite the possibility of this causing a "non-deterministic" cascade of further destructions.

这是真的，但不是以一种有用的方式。

常规 shared_ptr 破坏的确定性与您建议的确定性之间存在重大差异。即: shared_ptr 便宜。
shared_ptr 的析构函数执行原子递减，然后进行条件测试以查看值是否递减为零。如果是，则调用析构函数并释放内存。而已。

你的建议使这变得更加复杂。最坏的情况是，每次 circle_ptr 被销毁时，代码都必须遍历数据结构以确定是否存在循环。大多数时候，周期不会存在。但它仍然必须寻找它们，只是为了确定。并且每次销毁 circle_ptr 时都必须这样做。

python 等。阿尔。解决这个问题，因为它们是内置在语言中的。他们能够看到正在发生的一切。因此，他们可以在进行这些分配时检测何时分配了指针。通过这种方式，这样的系统不断地做少量的工作来建立循环链。一旦引用消失，它可以查看其数据结构并在创建循环链时采取行动。

但是您建议的是库功能，而不是语言功能。而库类型并不能真正做到这一点。或者更确切地说，他们可以，但只能在帮助下。

请记住: circle_ptr 的实例无法知道它所属的子对象。它不能自动将指向自身的指针转换为指向其所属类的指针。如果没有这种能力，如果重新分配它，它就无法更新拥有它的 cycle_detector_mixin 中的数据结构。

现在，它可以手动执行此操作，但只能在其拥有的实例的帮助下进行。这意味着 circle_ptr 需要一组构造函数，这些构造函数被赋予一个指向其拥有实例的指针，该指针派生自 cycle_detector_mixin 。然后，它的 operator= 将能够通知其所有者它已更新。显然，复制/移动分配不会复制/移动拥有实例指针。

当然，这需要拥有实例向它创建的每个 circle_ptr 提供一个指向自身的指针。在创建 circle_ptr 实例的每个构造函数和函数中。在它本身和它拥有的任何类中，这些类也不由 cycle_detection_mixin 管理。万无一失。这会在系统中造成一定程度的脆弱性；必须为类型拥有的每个 circle_ptr 实例花费人工。

这还要求 circle_ptr 包含 3 种指针类型:指向从 operator* 获取的对象的指针、指向实际托管存储的指针以及指向该实例所有者的指针。实例必须包含指向其所有者的指针的原因是它是每个实例的数据，而不是与块本身相关联的信息。是 circle_ptr的实例需要能够在反弹时告诉其所有者，因此该实例需要该数据。

这必须是静态开销。您无法知道 circle_ptr 实例何时在另一种类型中，何时不在。所以每个 circle_ptr ，即使是那些不使用循环检测功能的，也必须承担这 3 个指针成本。

因此，这不仅需要很大程度的脆弱性，而且价格昂贵，使字体的大小膨胀了 50%。用这种类型替换 shared_ptr(或者更重要的是，用这个功能增加 shared_ptr)是不可行的。

从好的方面来说，您不再需要从 cycle_detector_mixin 派生的用户来实现获取 circle_ptr 实例列表的方法。相反，您将类注册到 circle_ptr 实例。这允许可以循环的 circle_ptr 实例直接与其拥有的 cycle_detector_mixin 对话。

所以有一些东西。

封装和不变量

需要能够告诉一个类使其 circle_ptr 对象中的一个无效，从根本上改变了类与其任何 circle_ptr 成员交互的方式。

不变量是一段代码假定为真的某种状态，因为它在逻辑上不可能为假。如果您检查 const int 变量是否 > 0，那么您已经为后面的代码建立了一个不变量，该值是正的。

封装的存在是为了让您能够在类中构建不变量。单独的构造函数无法做到这一点，因为外部代码可以修改类存储的任何值。封装允许您防止外部代码进行此类修改。因此，您可以为类存储的各种数据开发不变量。

这就是封装的用途。

使用 shared_ptr ，可以围绕此类指针的存在构建不变量。您可以设计您的类，以便指针永远不会为空。因此，没有人必须检查它是否为空。
circle_ptr 不是这种情况。如果您实现了 cycle_detector_mixin ，那么您的代码必须能够处理任何 circle_ptr 实例变为空的情况。因此，您的析构函数不能假设它们是有效的，您的析构函数调用的任何代码也不能做出这种假设。

因此，您的类无法与 circle_ptr 指向的对象建立不变量。至少，如果它是 cycle_detector_mixin 及其相关注册等的一部分，则不会。

您可以争辩说您的设计在技术上没有破坏封装，因为 circle_ptr 实例仍然可以是私有(private)的。但是类(class)愿意放弃对循环检测系统的封装。因此，该类不能再确保某些类型的不变量。

对我来说，这听起来像是打破了封装。

线程安全

为了访问 weak_ptr ，用户必须 lock 它。这将返回 shared_ptr ，以确保对象将保持事件状态(如果它仍然存在)。锁定是一个原子操作，就像引用递增/递减一样。所以这都是线程安全的。
circle_ptr s 可能不是非常线程安全。如果另一个线程释放了对它的最后一个非循环引用，则 circle_ptr 可能会从另一个线程变为无效。

我不完全确定这一点。可能只有在您已经对对象的销毁进行数据竞争，或者正在使用非拥有引用时，才会出现这种情况。但我不确定您的设计是否可以是线程安全的。

毒力因子

这个想法非常流行。可能发生循环引用的所有其他类型都必须实现此接口(interface)。这不是你可以放在一种类型上的东西。为了获得好处，每个可以参与循环引用的类型都必须使用它。始终如一且正确。

如果你试图让 circle_ptr 要求它管理的对象实现 cycle_detector_mixin ，那么你就不可能将这样的指针用于任何其他类型。它不会替代(或扩充) shared_ptr 。因此，编译器无法帮助检测意外误用。

当然，编译器无法检测到 0x25181231343141 的意外误用。然而，这不是病毒构建体。因此，对于需要此功能的人来说，这只是一个问题。相比之下，从 make_shared_from_this 中获益的唯一方法是尽可能全面地使用它。

同样重要的是，因为这个想法非常流行，你会经常使用它。因此，您比 cycle_detector_mixin 的用户更有可能遇到多重继承问题。这不是一个小问题。特别是因为 make_shared_from_this 可能会使用 cycle_detector_mixin 来访问派生类，因此您将无法使用虚拟继承。

求和

因此，为了检测循环，您必须执行以下操作，而不会失败，编译器不会验证循环:

参与循环的每个类都必须从 static_cast 派生。

任何时候 cycle_detector_mixin 派生类在其自身内部构造一个 cycle_detector_mixin 实例(直接或间接，但不在本身派生自 0x2518122313 到 18 的类中，该类本身派生自 0x2518122313 到 1314 1314 到 1314 到 1314 到 1314 的 18

不要假设一个类的任何 circle_ptr 子对象都是有效的。由于线程问题，甚至可能在成员函数中变得无效。

这是成本:

cycle_detector_mixin 内的循环检测数据结构。

每 cycle_ptr 必须大 50%，即使是那些不用于循环检测的。

对所有权的误解

最终，我认为整个想法归结为对 cycle_ptr 实际上是什么的误解。

"A cycle detector is unnecessary because cycles are not that frequent and they can be easily avoided using std::weak_ptr." Cycles in fact turn up easily in many simple data structures - e.g. a tree where children have a back-pointer to the parent, or a doubly-linked list. In some cases, cycles between heterogenous objects in complex systems are formed only occasionally with certain patterns of data and are hard to predict and avoid. In some cases it is far from obvious which pointer to replace with the weak variant.

这是通用 GC 的一个非常常见的论点。这个论点的问题在于，它通常假设使用了无效的智能指针。

使用 cycle_detector_mixin 意味着什么。如果类存储 cycle_ptr ，则表示该类拥有该对象的所有权。

那么解释一下:为什么链表中的节点需要同时拥有下一个和前一个节点？为什么树中的子节点需要拥有其父节点？哦，他们需要能够引用其他节点。但是他们不需要控制他们的生命周期。

例如，我将一个树节点作为 shared_ptr 的数组实现给他们的 child ，并有一个指向 parent 的指针。常规指针，而不是智能指针。毕竟，如果树构造正确，则父项将拥有其子项。所以如果一个子节点存在，它的父节点必须存在；如果没有有效的 parent ， child 就不能存在。

对于双链表，我的左指针可能是 shared_ptr ，右指针是常规指针。或相反亦然;一种方式并不比另一种方式好。

您的心态似乎是我们应该始终使用 shared_ptr来处理问题，让自动系统解决如何处理问题。无论是循环引用还是其他什么，只要让系统解决即可。

这不是 unique_ptr 的用途。智能指针的目标不是让您不再考虑所有权；就是你可以直接在代码中表达所有权关系。

全面的

与使用 unique_ptr 中断循环相比，这些改进有何改进？你现在没有意识到循环何时可能发生并做额外的工作，而是到处做一堆额外的工作。极其脆弱的工作；如果你做错了，你不会比错过一个你应该使用 shared_ptr 的地方更好。只是更糟，因为您可能认为您的代码是安全的。

安全的错觉比没有安全更糟糕。至少后者让你小心翼翼。

你能实现这样的东西吗？可能。它是标准库的合适类型吗？不，它太脆弱了。您必须在任何时候、以各种方式、在任何可能出现循环的地方正确实现它……否则您将一无所获。

权威引用

对于标准化的 never proposed, suggested, or even imagined 没有权威引用。 Boost 没有这样的类型，这样的构造是 never even considered 为 shared_ptr 。甚至 very first smart pointer paper (PDF) 也从未考虑过这种可能性。扩展 weak_ptr 以通过一些手动工作自动能够处理循环的主题有 never been discussed even on the standard proposal forums 其中 远 已经考虑了更愚蠢的想法。

我可以提供的最接近引用的是 this paper from 1994 about a reference-counted smart pointer 。本文主要谈论使语言的 weak_ptr和 boost::shared_ptr部分的等效(这是在创业初期，他们甚至不认为这是可以写一个 shared_ptr，允许类型转换 shared_ptr到 weak_ptr时 shared_ptr是基础 shared_ptr<T> )。但即便如此，它也明确表示不会收集周期。它没有花太多时间在为什么不上，但它确实说明了这一点:

However, cycles of collected objects with clean-up functions are problematic. If A and B are reachable from each other, then destroying either one first will violate the ordering guarantee, leaving a dangling pointer. If the collector breaks the cycle arbitrarily, programmers would have no real ordering guarantee, and subtle, time-dependent bugs could result. To date, no one has devised a safe, general solution to this problem [Hayes 92].

这本质上是我指出的封装/不变性问题:使类型无效的指针成员破坏了不变性。

所以基本上，很少有人考虑过这种可能性，而那些考虑过这种可能性的人很快就认为它不切实际。如果你真的相信他们是错的，那么证明它的最好方法就是自己实现它。然后建议标准化。