garbage-collection - 为什么垃圾收集器在释放之前要等待？

Question

我有一个“为什么它会这样工作？” 关于垃圾收集的问题（任何/所有实现：Java、Python、CLR 等）。当对象不再在任何范围内时，垃圾收集器会释放它；指向它的引用数为零。在我看来，一旦引用数量达到零，框架就可以解除分配，但我遇到的所有实现都会等待一段时间，然后一次解除许多对象的分配。我的问题是，为什么？

我假设框架为每个对象保留一个整数（我认为 Python 会这样做，因为您必须在用 C 语言为它编写扩展模块时调用它；大概这些函数在某处修改了一个真实的计数器）PyINCREF。PyDECREF如果是这样，那么当它超出范围时，它不应该花费更多的 CPU 时间来消除对象。如果现在每个对象需要 x 纳秒，那么以后每个对象需要 x 纳秒，对吧？

如果我的假设是错误的并且没有与每个对象相关联的整数，那么我就会理解为什么垃圾收集会等待：它必须遍历引用图以确定每个对象的状态，并且计算需要时间。这种方法会比显式引用计数方法消耗更少的内存，但我很惊讶它更快或者由于其他原因是首选方法。听起来工作量很大。

从编程的角度来看，如果对象在超出范围后立即解除分配，那就太好了。我们不仅可以依赖在我们想要的时候执行析构函数（Python 的陷阱之一是它__del__不会在可预测的时间被调用），而且对程序进行内存分析会变得更加容易。 这是一个例子，说明这会导致多少混乱。在我看来，在立即解除分配框架中编程的好处是如此之大，以至于我听说的所有实现都必须在解除分配之前等待。那有什么好处？

注意：如果只需要遍历引用图来识别循环引用（纯引用计数不能），那么为什么不采用混合方法呢？一旦对象的引用计数达到零，就释放对象，然后定期扫描以查找循环引用。在这样的框架中工作的程序员将有一个性能/确定性的理由尽可能地坚持非循环引用。这通常是可行的（例如，所有数据都是 JSON 对象的形式，没有指向父对象的指针）。这是任何流行的垃圾收集器的工作方式吗？

Answer 1

首先，一个术语：“垃圾收集”对不同的人意味着不同的东西，并且一些 GC 方案比其他方案更复杂。有些人认为引用计数是 GC 的一种形式，但我个人认为“真正的 GC”不同于引用计数。

使用 refcounts，有一个整数跟踪引用的数量，当 refcount 达到零时，您可以立即触发解除分配。这就是 CPython 实现的工作原理，以及大多数 C++ 智能指针的工作原理。CPython 实现添加了一个标记/清除 GC 作为备份，因此它非常类似于您描述的混合设计。

但是引用计数实际上是一个非常糟糕的解决方案，因为每次传递引用时都会产生（相对）昂贵的内存写入（加上内存屏障和/或锁，以确保线程安全），这种情况经常发生。在像 C++ 这样的命令式语言中，可以（只是很难）通过宏和编码约定来管理内存所有权，但在像 Lisp 这样的函数式语言中，这几乎是不可能的，因为内存分配通常是由于闭包中的局部变量捕获而隐式发生的。

因此，为 Lisp 发明了迈向现代 GC 的第一步也就不足为奇了。它被称为“双空间分配器”或“双空间收集器”，它的工作方式与听起来完全一样：它将可分配内存（“堆”）分成两个空间。每个新对象都从第一个空间分配，直到它太满，此时分配将停止，运行时将遍历引用图并仅将活动（仍被引用）对象复制到第二个空间。在活动对象被复制后，第一个空间将被标记为空，并且分配将继续，从第二个空间分配新对象，直到它太满，此时活动对象将被复制回第一个空间和过程将重新开始。

双空间收集器的优点是，它不会O(N)工作，其中N是垃圾对象的总数，它只会O(M)工作，其中M是非垃圾对象的数量 。由于在实践中，大多数对象在短时间内被分配然后释放，这可以带来显着的性能改进。

此外，双空间收集器还可以简化分配器端。大多数malloc()实现都维护所谓的“空闲列表”：哪些块仍然可以分配的列表。要分配新对象，malloc()必须扫描空闲列表以寻找足够大的空白空间。但是双空间分配器并没有为此烦恼：它只是像堆栈一样在每个空间中分配对象，只需将指针向上推所需的字节数即可。

所以 twospace 收集器比 . 快得多malloc()，这很棒，因为 Lisp 程序会比 C 程序做更多的分配。或者，换句话说，Lisp 程序需要一种像堆栈一样分配内存的方法，但它的生命周期不限于执行堆栈——换句话说，一个堆栈可以无限增长而不会耗尽程序的内存. 而且，事实上，Raymond Chen 认为这正是人们应该如何看待 GC。我强烈推荐他的系列博客文章，以“每个人都以错误的方式思考垃圾收集”开头。

但是 twospace 收集器有一个重大缺陷，那就是没有程序可以使用超过一半的可用 RAM：另一半总是被浪费掉。所以 GC 技术的历史就是尝试改进双空间收集器的历史，通常是通过使用程序行为的启发式方法。然而，GC 算法不可避免地涉及权衡，通常更喜欢分批释放对象而不是单独释放对象，这不可避免地会导致对象没有立即释放的延迟。

编辑：为了回答您的后续问题，现代 GC 通常包含分代垃圾回收的概念，其中对象根据生命周期被分组为不同的“代”，并且一个代中的对象一旦存在就会被“提升”到另一代够长了。有时，对象生存期的微小差异（例如，在请求驱动的服务器中，将对象存储的时间超过一个请求）可能会导致对象被释放之前所需的时间量有很大差异，因为它会导致它变为更“终身”。

malloc()您正确地观察到真正的 GC 必须在and的级别“之下”运行free()。（作为旁注，值得学习如何实现malloc()和free()实现——它们也不是魔法！）此外，对于有效的 GC，您要么需要保守（如 Boehm GC）并且永远不要移动对象，并检查可能是指针的东西，或者您需要某种“不透明指针”类型——Java 和 C# 称之为“引用”。不透明指针实际上非常适合分配系统，因为这意味着您始终可以通过更新指向对象的指针来移动对象。在像 C 这样直接与原始内存地址交互的语言中，移动对象从来都不是真正安全的。

GC 算法有多种选择。标准的 Java 运行时包含不少于五个收集器（Young、Serial、old CMS、new CMS 和 G1，尽管我想我忘记了一个）并且每个都有一组可配置的选项。

但是，GC 并不神奇。大多数 GC 只是利用批处理工作的时间-空间权衡，这意味着速度的提高通常是通过增加内存使用来支付的（与手动内存管理或重新计数相比）。但是，提高程序性能和提高程序员性能的结合，与如今 RAM 的低成本相比，通常值得权衡。

希望这有助于使事情更清楚！

Answer 2

要了解垃圾收集，请前往保龄球馆并观察置瓶机在第一个球滚完后如何清除掉下的瓶。置瓶机机制不是识别和移除单个倒下的瓶，而是捡起所有仍然站立的瓶，将它们提升到安全位置，然后在车道上运行一个清扫杆，而不考虑有多少瓶躺在那里或它们的位置. 完成后，将站立的旗杆放回球道上。许多垃圾收集系统的工作原理大致相同：它们必须为每个活动对象做大量工作以确保它不会被破坏，但死对象会被大量销毁，甚至没有被查看或注意到。

附录

一个垃圾收集器总是必须对每个活动项目采取行动以确保其保存在有很多活动项目时很容易变慢；这就是为什么垃圾收集器在历史上名声不好的原因。Commodore 64 上的 BASIC 解释器（顺便说一句，它是微软在MS-DOS之前的日子里编写的）在一个包含几百个字符串的数组的程序中执行垃圾收集需要几秒钟的时间。如果可以忽略在第一次垃圾收集中幸存的项目，直到许多项目在第一次垃圾收集中幸存下来，并且那些参与了并且在两次垃圾收集中幸存下来（请注意，在许多其他对象在第一次垃圾收集中幸存下来之前，它们不必参与第二次收集）可以被忽略，直到许多其他对象也参与并在第二次垃圾收集中幸存下来。这个概念可以很容易地部分实现（即使在 Commodore 64 上，也可以强制在给定时刻存在的所有字符串免于将来的垃圾收集，如果在启动时程序创建了永远不会的大型字符串数组，这可能很有用更改），但通过一些额外的硬件支持变得更强大。

如果有人认为垃圾收集器将尝试打包将尽可能靠近内存末端的对象，那么世代支持只需要跟踪使用的（连续）内存范围按每一代的对象。必须扫描每一代的所有对象，以确保所有较新的活动对象都已定位和保存，但不必移动较旧的对象，因为它们占用的内存没有被大规模淘汰的危险。这种方法实现起来非常简单，并且与非分代 GC 相比可以提供一些显着的性能改进，但如果有很多活动对象，即使 GC 的扫描阶段也会很昂贵。

加速“新一代”垃圾收集的关键是观察如果对象“Fred”自上次参与的垃圾收集后没有被写入，则它不可能包含对任何已被回收的对象的引用。从那时起创建。因此，在 Fred 本身有资格被淘汰之前，它所引用的任何对象都不会有被淘汰的危险。当然，如果自上次低级 GC 以来对新对象的引用已存储在 Fred 中，则确实需要扫描这些引用。为了实现这一点，高级垃圾收集器设置了硬件陷阱，在写入老一代堆的部分内容时触发。当这样的陷阱触发时，它将该区域中的对象添加到需要扫描的老一代对象列表中，然后禁用与该区域关联的陷阱。在老一代对象经常引用存储在其中的新对象的情况下，这种额外的簿记可能会损害性能，但在大多数情况下，它最终会成为主要的性能优势。

Answer 3

您的想法通常非常有见地且经过深思熟虑。您只是缺少一些基本信息。

当对象不再在任何范围内时，垃圾收集器会释放对象

一般来说，这是完全不正确的。垃圾收集器在运行时处理范围概念早已被删除的表示。例如，活性分析的内联和应用会破坏范围。

跟踪垃圾收集器在最后一个引用消失后的某个时间点回收空间。即使变量仍在范围内，活跃度分析也可以使堆栈帧中的引用被其他引用覆盖，因为活跃度分析确定该变量永远不会再次使用，因此不再需要。

在我看来，一旦引用数量达到零，框架就可以解除分配，但我遇到的所有实现都会等待一段时间，然后一次解除许多对象的分配。我的问题是，为什么？

表现。您可以在堆栈条目和寄存器级别引用计数，但性能绝对糟糕。所有实用的引用计数垃圾收集器都将计数器递减延迟到作用域的末尾，以实现合理（但仍然很差）的性能。最先进的引用计数垃圾收集器延迟递减以将它们批量化，据称可以获得具有竞争力的性能。

我假设框架为每个对象保留一个整数

不必要。例如，OCaml 使用单个位。

从编程的角度来看，如果对象在超出范围后立即解除分配，那就太好了。

从编程的角度来看，如果代码能毫不费力地快 10 倍，那就太好了。

请注意，析构函数抑制尾调用消除，这在函数式编程中是无价的。

我很惊讶它更快或出于其他原因是首选方法。听起来工作量很大。

考虑一个通过处理棋盘坐标列表来解决 n 皇后问题的程序。输入是一个整数。输出是一个包含一些棋盘坐标的列表。中间数据是一个巨大的链表节点意大利面条堆栈。如果您通过预先分配足够大的链表节点堆栈来编写它，操纵它们以获得答案，复制出（小）答案然后free在整个堆栈上调用一次，那么您将做的几乎完全相同世代垃圾收集器所做的事情。特别是，您只需要复制约 6% 的数据，而只需调用free.

对于坚持“大多数对象年轻而老对象很少引用新对象”这一假设的世代垃圾收集器来说，这是一个完美的快乐日子场景。分代垃圾收集器挣扎的一个病态反例是用新分配的对象填充哈希表。哈希表的主干是一个大数组，可以存活，所以它会在老年代。每个插入其中的新对象都是从老一代到新一代的反向指针。每个新对象都存在。因此，分代垃圾收集器快速分配，然后标记所有内容，复制所有内容并更新指向所有内容的指针，因此，运行速度比简单的 C 或 C++ 解决方案慢约 3 倍。

我们不仅可以依赖于在我们希望它们执行时执行析构函数（Python 的陷阱之一是del不会在可预测的时间被调用），而且对程序进行内存分析会变得更加容易

请注意，析构函数和垃圾回收是正交概念。例如，.NET 以 .NET 的形式提供析构函数IDisposable。

FWIW，在使用垃圾收集语言的约 15 年中，我使用内存分析可能 3 次。

为什么不采用混合方法？一旦对象的引用计数达到零，就释放对象，然后定期扫描以查找循环引用。在这样的框架中工作的程序员将有一个性能/确定性的理由尽可能地坚持非循环引用。这通常是可行的（例如，所有数据都是 JSON 对象的形式，没有指向父对象的指针）。这是任何流行的垃圾收集器的工作方式吗？

我相信 CPython 就是这样做的。Mathematica 和 Erlang 在设计上将堆限制为 DAG，因此它们可以单独使用引用计数。GC 研究人员提出了相关技术，例如 Trial-deletion 作为检测循环的辅助算法。

另请注意，引用计数在理论上比跟踪垃圾收集更快，因为它的性能与（活动）堆的大小无关。实际上，即使使用 100GB 堆，跟踪垃圾收集仍然要快得多。

Answer 4

我认为原因在性能。如果您在循环中创建大量对象并在循环步骤结束时销毁它们，则执行该代码将花费更多时间，然后等到程序空闲并立即释放数据。或者对原因的低记忆。

Answer 5

在我遇到 GC 系统的地方，它们会一直等到需要运行，这样仍在使用中的对象的重定位就可以完成一次，而不是多次。

考虑在内存中顺序分配的一系列对象：

Object 1
Object 2
Object 3
Object 4
Object 5

如果对象 2 可以被释放，并且 GC 立即运行，则对象 3,4 和 5 都需要移动。

现在考虑可以释放对象 4，GC 现在会将对象 5 移动到对象 3 旁边。对象 5 已经移动了两次

但是，如果 GC 等待一小会儿，Objects2 和 Objects 4 可以同时被移除，这意味着 Object 5 被移动了一次，并且移动得更远。

将对象的数量乘以 100，您可以看到这种方法节省了大量时间

Answer 6

@Jim 已经回答了很多，我会添加更多。

首先，是什么让您认为一旦计数就解除分配 [A1]0是一个不错的选择？

垃圾收集器不仅释放对象，而且负责完整的内存管理。从 开始fragmentation，垃圾收集器的最大问题之一。如果处理不当，将导致不必要的页面命中和缓存未命中。垃圾收集器从一开始就是为了处理这个问题而设计的。对于不同的世代，处理这个变得更容易。使用A[1]，线程必须定期对其进行设置和处理。

此外，事实证明清除多个对象比A[1]. （想一想，对于一个铺满沙子的房间 - 将它们全部清除而不是单独挑选它们会更快）

其次，为了多线程系统中的线程安全，必须为每个对象持有一个锁以增加/减少计数，这是性能不佳和额外的内存。此外，现代收集器有能力并行而不是停止世界（例如：Java 的 ParallelGC），我想知道A[1].

Answer 7

使用引用计数的垃圾收集非常慢，尤其是在线程环境中。

我真的推荐Brian Harry 的这篇文章。

那里提供了一个代码示例，足以说服我（C#）：

public interface IRefCounted : IDisposable
{
        void AddRef();
}

// ref counted base class.
class RefCountable : IRefCountable
{
        private m_ref;
        public RefCountable()
        {
                m_ref = 1;
        }
        public void AddRef()
        {
                Interlocked.Increment(ref m_ref);
        }
        public void Dispose()
        {
                if (Interlocked.Decrement(ref m_ref) == 0)
                        OnFinalDispose();
        }
        protected virtual void OnFinalDispose()
        {
        }
}

Interlocked.Increment(ref m_ref)是一个原子操作，需要数百个内存周期。