对于实时编程，引用计数在确定性方面比垃圾收集有优势吗？
如果您正在设计一种具有自动内存管理功能的编程语言，那么使用引用计数是否可以实现垃圾收集器无法实现的确定性保证？
对于函数式语言和命令式语言来说，这个问题会有不同的答案吗？
If you were designing a programming language that features automatic memory management, would using reference counting allow for determinism guarantees that are not possible with a garbage collector?
Would there be a different answer to this question for functional vs. imperative languages?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
保证这个词是一个强有力的词。以下是您可以通过引用计数提供的保证：
在分配时调整引用计数的恒定时间开销。
释放引用计数为零的对象的恒定时间。 （关键是您不能立即递减该对象的子对象；相反，当该对象用于满足未来的分配请求时，您必须延迟执行此操作。）
分配新对象的恒定时间对象当相关空闲列表不为空时。这种保证是有条件的，没有多大价值。
以下是引用计数无法保证的一些事情：
分配新对象的时间恒定。 组织新内存的延迟可能会相当大。或者更糟糕的是，您可能会填满堆并且无法分配。）
所有无法访问的对象都是回收和重复使用，同时保持其他操作的恒定时间。 （标准引用计数器无法收集循环垃圾。有多种巧妙的解决方法，但通常它们会使简单操作的恒定时间保证失效。）
现在有一些实时垃圾收集器提供了有关暂停时间的非常有趣的保证，在过去 5 年中，引用计数和垃圾收集方面都取得了非常有趣的发展。作为一个知情的局外人，我认为没有明显的赢家。
最近有关引用计数的一些最佳著作是 IBM 的 David Bacon 和 Technion 的 Erez Petrank 完成的。如果您想了解复杂的现代引用计数系统可以做什么，请查阅他们的论文。除此之外，他们以令人惊奇的方式使用多个处理器。
有关内存管理和实时保证的更一般信息，请查看 内存管理国际研讨会。
因为您询问了保证，没有。但对于一般的内存管理来说，对于命令式语言（大量突变但分配率低）、不纯函数式语言（几乎没有任何突变但分配率高）和纯粹的惰性函数式语言（大量突变）的性能权衡是完全不同的。突变（所有这些都认为正在更新）和高分配率）。
The word guarantee is a strong one. Here are the guarantees you can provide with reference counting:
Constant time overhead at an assignment to adjust reference counts.
Constant time to free an object whose reference count goes to zero. (The key is that you must not decrement that object's children right away; instead you must do it lazily when the object is used to satisfy a future allocation request.)
Constant time to allocate a new object when the relevant free list is not empty. This guarantee is conditional and isn't worth much.
Here are some things you can't guarantee with reference counting:
Constant time to allocate a new object. (In the worst case, the heap may be growing, and depending on the system the delay to organize new memory may be considerable. Or even worse, you may fill the heap and be unable to allocate.)
All unreachable objects are reclaimed and reused while maintaining constant time for other operations. (A standard reference counter can't collect cyclic garbage. There are a variety of ingenious workarounds, but generally they invalidate constant-time guarantees for simple operations.)
There are now some real-time garbage collectors that provide pretty interesting guarantees about pause times, and in the last 5 years there have been pretty interesting developments in both reference counting and garbage collection. From where I sit as an informed outsider, there's no obvious winner.
Some of the best recent work on reference counting is by David Bacon of IBM and by Erez Petrank of Technion. If you want to learn what a sophisticated, modern reference-counting system can do, look up their papers. Among other things, they are using multiple processors in amazing ways.
For information about memory management and real-time guarantees more generally, check out the International Symposium on Memory Management.
Because you asked about guarantees, no. But for memory management in general, the performance tradeoffs are quite different for an imperative language (lots of mutation but low allocation rates), an impure functional language (hardly any mutation but high allocation rates), and a pure, lazy functional language (lots of mutation—all those thinks being updated—and high allocation rates).
我不明白怎么办。 降低对象引用计数的过程没有时间限制，因为该对象可能是任意大型对象图的单个根。
解决实时系统 GC 问题的唯一方法是使用并发收集器或增量收集器 - 无论系统是否使用引用计数；在我看来，无论如何，引用计数和“集合”之间的区别并不精确，例如，利用引用计数的系统可能仍然偶尔执行一些内存扫描（例如，处理周期）。
您可能对 IBM 的 Metronome 感兴趣，并且我还知道微软在良好的实时内存管理方向上做了一些研究。
I don't see how. The process of lowering the reference count of an object is not time-bounded, as that object may be the single root for an arbitrary large object graph.
The only way to approach the problem of GC for real-time systems is by using either a concurrent collector or an incremental one - and no matter if the system uses reference counting or not; in my opinion your distinction between reference counting and "collection" is not precise anyway, e.g. systems which utilize reference counting might still occasionally perform some memory sweep (for example, to handle cycles).
You might be interested in IBM's Metronome, and I also know Microsoft has done some research in direction of good, real-time memory management.
如果您查看 RTSJ 规范 (JSR-1)，您会发现他们通过提供无堆实时线程来解决该问题。通过设置一个单独的线程类别，不允许接触任何可能需要停止线程进行垃圾回收的对象，JSR-1 回避了这个问题。目前还没有很多 RTSJ 实现，但实时垃圾收集领域是该社区的热门话题。
If you look at the RTSJ spec (JSR-1), you'll see they did an end-run around the problem by providing for no-heap realtime threads. By having a separate category of thread that isn't allowed to touch any object that might require the thread to be stopped for garbage collection, JSR-1 side stepped the issue. There aren't many RTSJ implementations right now, but the area of realtime garbage collection is a hot topic in that community.
是的。引用计数的主要优点是简单。
像 Baker's Treadmill 这样的 GC 应该获得与引用计数提供的确定性相同级别的保证。
是的。单独的引用计数不能处理循环。某些函数式语言无法通过设计来创建循环（例如 Erlang 和 Mathematica），因此它们通常允许单独使用引用计数作为 GC 的精确方法。
Yes. The main advantage of reference counting is simplicity.
A GC like Baker's Treadmill should attain the same level of guarantees regarding determinism that reference counting offers.
Yes. Reference counting alone does not handle cycles. Some functional languages make it impossible to create cycles by design (e.g. Erlang and Mathematica) so they trivially permit reference counting alone as an exact approach to GC.
在实时编程中，垃圾收集可能是有害的，因为您不知道垃圾收集器何时收集......所以，是的，引用计数在这种情况下肯定更好。
顺便说一句，通常在实时系统中只有某些部分需要实时处理，因此您可以避免仅在敏感组件中进行垃圾收集。一个真实的示例是在 Windows CE 目标上运行的 C# 程序。
In real time programming garbage collection could be harmful, because you don't know when the garbage collector will collect... so yes, reference counting is definitely better in this context.
As a side note, usually in real time system only some parts needs real time processing, so you could avoid garbage collection just in sensitive components. A real world example is a C# program running on a Windows CE target.
从参与将大量代码从 C++（具有各种智能指针类，包括引用计数）迁移到垃圾收集 Java/C# 的各种项目中，我发现最大的痛点似乎都与非空类相关析构函数（特别是用于 RAII 时）。这是一个相当大的标志，表明需要进行确定性清理。
对于任何带有对象的语言来说，这个问题肯定都是一样的。我不认为像 Scala 或 Ocaml 这样的混合面向对象函数式语言在这个领域有任何特殊的优势。对于更“纯”的函数式语言，情况可能有所不同。
From some involvement in various projects migrating significant chunks of code from C++ (with various smart pointer classes, including reference counted) to garbage collected Java/C#, I observe that the biggest pain-points all seem to be related to classes with non-empty destructors (particularly when used for RAII). This is a pretty big flag that deterministic cleanup is expected.
The issue is surely much the same for any language with objects; I don't think hybrid OO-functional languages like Scala or Ocaml enjoy any particular advantages in this area. Situation might be different for more "pure" functional languages.