可视化垃圾收集器算法[2014]

大多数开发人员授予自动垃圾收集。这只是我们的语言运行时间提供的另一个惊人的功能，使我们的工作更轻松。

但如果你试图在现代垃圾收集器里偷看，那么很难看出他们实际工作的工作。除非您已经对尝试做的事情有所了解以及如何奇妙地了解，否则有成千上万的实施细节会困惑。

我建造了一个有五个不同的垃圾收集算法的玩具。从运行时行为创建小动画。您可以在Github.com/kenfox/gc-viz找到更大的动画和代码以在github.com/kenfox/gc-viz中创建它们。这让我惊讶了一个简单的动画揭示了这些重要的算法。

清理垃圾的最简单可能的方式是等到任务完成并立即处理所有事情。这是一个令人惊讶的有用技术，特别是如果您有办法将任务分解成碎片。例如，Apache Web服务器每个请求创建一小部分内存池，并在请求完成时将整个池抛出。

右侧的小动画代表了一个正在运行的程序。整个图像代表程序的内存。记忆开始彩色黑色，这意味着它不使用。闪光亮绿色或黄色的区域是内存读取或写入。随着时间的推移，颜色衰减，因此您可以看到如何使用内存，但也看到了当前活动。如果您仔细观察，您可以看到模式出现的模式开始忽略一些内存。这些地区已成为垃圾 - 它们未被使用而无法通过该计划访问。其他不是垃圾的东西是“生活”。

该程序容易符合内存，而无需担心程序运行时清理垃圾。我将在剩下的例子中坚持这个简单的程序。

另一个简单的解决方案是保留您使用资源（在内存中的对象，在这种情况下的对象）的计数，并且当计数下降到零时将其处置。这是开发人员在将垃圾收集添加到现有系统时使用的最常用技术 - 这是唯一与其他资源管理器和现有代码基础集成的唯一垃圾收集器。苹果在释放Mark-Sweep收集器以获得目标-C后，Apple学到了本课程。它引起了许多问题，它们缩回了该功能并用自动参考计数收集器替换它，与现有代码更好地工作。

动画显示相同的程序，如上所述，但这一次它将通过在内存中的每个对象上保持引用计数来尝试处理垃圾。红色闪烁表示参考计数活动。一个非常有用的参考计数属性是尽快检测到垃圾 - 您有时可以看到一闪红的红色，然后立即关闭区域。

不幸的是，参考算有很多问题。最糟糕的是，它无法处理循环结构。这些非常常见 - 具有父级或反向引用的任何内容都会创建一个泄漏内存的循环。参考计数也具有很高的开销 - 您可以在动画中看到，即使内存使用不断增加，也可以在动画中不断发生。算法在现代CPU上快速，但内存缓慢，并且次数正在加载并经常保存到内存中。所有这些计数器更新也使得难以具有只读或线程安全数据。

参考计数是摊销算法（开销在程序的运行时间上传播），但它是一种意外摊销的算法，不能保证响应时间。例如，假设一个程序正在使用非常大的树结构。使用树的最后一块程序将触发整个树的处理，当用户最不希望延迟时，墨菲将保证。这里的其他算法都没有摊销，因此，因此意外摊销可能是根据您的数据的特征。 （所有这些算法确实都有并发或部分并发变体，但这些算法超出了我玩具程序的能力来证明。）

标记扫描消除了一些参考数数问题。它可以轻松处理循环结构，并且它具有较低的开销，因为它不需要维持计数。

它放弃了能够立即检测垃圾。您可以在动画中看到有一段时间没有任何红色闪烁的活动，那么突然一堆红色闪光指示它标记实时对象的位置。标记完成后，它会扫过所有内存并处置垃圾。您可以在动画中看到它太多 - 几个区域一次转动黑色，而不是在参考计数方法中随时间播放。

标记扫描需要更多的实现一致性而不是参考计数，并且更难以改装到现有系统中。标记阶段需要遍历所有实时数据，甚至封装在对象中的数据。如果对象没有提供遍历，则尝试将标记扫描到代码中可能过于危险。标记扫描的其他弱点是事实，扫描阶段必须扫过所有内存以找到垃圾。对于不产生大量垃圾的系统，这不是一个问题，但现代功能规划风格产生了大量的垃圾。

在上一动画中可能注意到的一件事是对象永远不会移动。一旦对象被分配在内存中，即使记忆变成黑色围绕着黑色的岛屿的分散的海洋，它也处于同一个位置。接下来的两个算法改变了，但具有完全不同的方法。

标记紧凑的内存处理，而不是通过自由标记，而是通过将物体移动到自由空间中。对象始终保持在相同的内存顺序 - 在另一个对象之前分配的对象将始终在内存中较低 - 但是由设置的对象导致的差距将被移动向下关闭。

移动对象的疯狂思想意味着始终可以在旧的内存结束时创建新对象。这被称为“凹凸”分配器，并且与堆栈分配一样便宜，但没有堆栈大小的局限性。一些使用Bump分配器的系统甚至没有使用呼叫堆栈进行数据存储，它们只需在堆中分配呼叫帧并像任何其他对象一样对待它们。

另一个好处，有时比实践更多的理论，就是当物体被压缩时，程序具有更好的内存访问模式，友好到现代硬件存储器缓存。尽管如此，它远远甚至可以看到这种好处 - 参考计数和标记扫描中使用的内存分配器是复杂的，但也很好地调试和非常高效。

Mark-Compact是一种复杂的算法，需要多次通过所有分配的对象。在动画中，您可以看到Live对象标记的红色闪烁，然后读取许多读写，因为计算目的地，因此移动对象，最后引用是指向对象移动的位置。所有这些复杂性的主要好处是在极低的内存开销下运行。 Oracle的热点JVM使用几种不同的垃圾收集算法。终身物体空间使用标记紧凑。

我动画的最后一次算法是大多数高性能垃圾收集系统的基础。这是一个动作的收集器，如标记紧凑，但它非常简单。它使用两个内存空间，并在它们之间来回复制活对象。在实践中，有两个以上的空间，并且空间用于不同几代物体。新对象是在一个空格中创建的，如果他们生存，将复制到另一个空间，并且如果它们非常长期以来，最终会复制到职业空间。如果您听到垃圾收集器被描述为世代或短暂的，它通常是多空间复制收集器。

除了简单和灵活性之外，该算法的主要优点是它仅在实时对象上花费时间。没有单独的标记阶段必须稍后扫除或压缩。在实时对象遍历期间立即复制对象，并且通过遵循常用的对象，通过遵循常见的心脏引用来修补对象引用。

在动画中，您可以看到有几个集合，几乎所有数据都将从一个空间复制到另一个空间。这是这种算法的可怕情况，并显示了人们谈论调整垃圾收集器的原因之一。如果您可以进行尺寸，并调整您的分配，以便在收集开始时大多数物体都死了，那么您可以获得安全功能性编程风格和高性能的奇妙组合。