数据结构中的垃圾回收

垃圾回收 (GC) 是一种动态的内存管理和堆分配技术，它会检查并识别无用的内存块，然后重新分配存储空间以供重用。垃圾回收的主要目标是减少内存泄漏。垃圾回收使程序员无需手动解除分配对象并将它们返回给内存系统。垃圾回收可能占程序总处理时间的很大一部分，因此可能对性能产生重大影响。堆栈分配、区域推断、内存所有权以及各种技术的组合是相关技术的示例。

垃圾回收的基本原理是查找程序中未来无法访问的数据对象，并回收这些对象所使用的资源。

垃圾回收通常不处理内存以外的资源，例如网络套接字、数据库句柄、用户交互窗口、文件和设备描述符。管理这些资源的 方法，尤其是析构函数，可能足以在不需要 GC 的情况下管理内存。在某些 GC 系统中，其他资源可以与内存区域关联，当这些内存区域被收集时，会导致回收这些资源的任务。

许多编程语言，如 RPL、Java、C#、Go 和大多数脚本语言，都需要垃圾回收，无论是作为语言规范的一部分，还是为了实际实现（例如，像 lambda 演算这样的形式语言）；这些被称为垃圾回收语言。其他语言，如 C 和 C++，最初是为手动内存管理设计的，但包含了垃圾回收的实现。一些语言，如 Ada、Modula-3 和 C++/CLI，通过使用独立的堆来收集和手动管理的内存，允许在同一个应用程序中进行垃圾回收和手动内存管理；另一些语言，如 D，是垃圾回收的，但允许用户手动删除对象并在需要速度时完全禁用垃圾回收。

垃圾回收通过自动堆分配的动态方法解决了常见且代价高昂的故障，如果这些故障未被发现，可能会导致实际的程序员问题。

分配错误代价高昂，因为它们难以检测和纠正。因此，许多程序员认为垃圾回收是一项必不可少的功能，它通过减少手动堆分配管理来简化程序员的工作。

现在让我们看看一些最著名和最常用的垃圾回收技术。

• 标记和清除
• 引用计数

标记和清除

Mark Sweep 算法正如其名一样简单。它包含两个阶段：标记阶段和清除阶段。在标记阶段，收集器会遍历所有根（全局变量、局部变量、堆栈帧、虚拟和硬件寄存器等），并通过在对象周围设置一个位来标记遇到的每个对象。在清除阶段，它还会遍历堆，回收所有未标记对象占用的内存。

下面的 Python 伪代码概述了基本算法。在此示例中，假设收集器是单线程的，尽管可能存在多个变异体。当收集器运行时，所有变异体线程都会被暂停。这种“停止世界”技术可能看起来效率低下，但它极大地简化了收集器的实现，因为变异体无法影响其下方的状态。

代码

从伪代码中可以明显看出，Mark-Sweep 并不会立即识别垃圾。相反，它首先识别所有不是垃圾的对象，例如活动的（活的）对象，然后才将其他所有对象视为垃圾。标记过程是循环的。在检测到活动引用后，我们递归到其子字段，依此类推。由于时间成本和堆栈溢出的风险，递归过程调用并不是标记的合适方法。这就是我们使用显式定义的堆栈的原因。此技术使标记阶段的空间和时间开销都变得显而易见。必须通过对象图追踪的最长路径的长度决定了候选堆栈的最大深度。

理论上，最坏情况等于堆上节点的数量。然而，大多数实际应用程序产生的堆栈相当浅。尽管如此，一个安全的 GC 系统必须处理异常情况。在我们的实现中，我们在将新对象添加到候选对象后立即使用 **mark()**，以控制堆栈大小。标记的问题在于，GC 正是因为内存不足而需要的，但辅助堆栈却需要更多空间。大型应用程序可能会导致垃圾收集器耗尽内存。

有多种方法可以检测溢出。使用显式堆栈的一个优点是，可以立即检测到溢出并启动恢复过程。使用内联检查每次推送是一种简单的方法（）。使用保护页并在捕获保护冲突异常后触发恢复可能是稍微更有效的方法。这两种技术的权衡都必须在底层操作系统和硬件的上下文中进行考虑。对于第一种技术，is-full 测试可能只花费几条指令（测试后跟一个分支），但每次检查对象时都会执行。第二种技术需要捕获访问冲突异常，这通常代价高昂但很少发生。

**Sweep()** 是一个具有简单实现的简单函数。它线性遍历堆，释放所有未标记的对象。由于这个原因，我们的堆布局确实会面临解析限制。next object(address) 实现必须能够返回堆中的下一个对象。在大多数情况下，堆只需要能够以一种方式解析。在大多数启用了 GC 的语言运行时中，对象的内存通常会带有对象头。该头提供了有关对象的信息，例如类型、大小、哈希码、标记位、同步块等。

对象头通常放置在对象数据之前。因此，对象的引用指向的是分配的堆单元的中间，紧随对象头之后，而不是第一个字节。这使得从上到下解析堆变得更加容易。在大多数情况下，free(address) 会用堆解析算法识别的预定填充模式填充释放的单元。

Mark and Sweep 算法的优点

• 硬件缓存的使用效率通常是大多数应用程序性能的决定因素。L1-L3 缓存现在可以在 2 到 10 个 CPU 周期内访问，而 RAM 可能需要高达 100 个周期。缓存有助于具有良好时间局部性和空间局部性的应用程序运行得更好。当程序访问最近访问过的内存位置时，它被称为时间局部性。如果程序以扫描模式访问附近的内存区域，则具有很高的空间局部性。不幸的是，Mark-Sweep 算法中的标记阶段在时间局部性和地理局部性方面表现不佳（标记阶段在标记时就完成了，后面就不再访问了，所以无法利用预取）。假设大多数对象是流行的，并且只被单个指针引用，则在 mark() 中，对象的头通常只读写一次。我们读取标记位，如果对象尚未被标记，它将不再被访问。硬件预取（无论是推测的还是通过显式预取指令）对于这种不规则的指针跟踪并非理想。一种改进缓存速度的常用策略是将标记位放在单独的位图中，而不是将它们作为对象头的一部分。位图的格式、位置和大小由各种参数确定，包括堆大小、对象对齐要求、硬件缓存大小等。Mark-Sweep 算法从这些标记位图中受益，从而提高了性能。例如，标记不需要修改对象；可以使用单个指令（针对位图单词进行位运算）标记多个对象。由于它修改的字数更少，因此生成的脏缓存行更少，从而导致更少的缓存刷新。清除不需要读取任何活动对象，并且可以完全依赖位图进行堆扫描。
• 标记阶段的复杂度为 O(L)，其中 L 是可从所有根访问的活动对象的大小。清除阶段的时间复杂度为 O(H)，其中 H 是堆单元的数量。考虑到 H > L，很容易认为 O(H) 占主导地位 O(L)，但实际上，由于高空间局部性，清除阶段具有出色的缓存性能，但由于所有缓存不友好的指针跟踪，整个收集速度由 O(L) 主导。
• 由于标记是一个耗时的过程，因此它仅在有限的范围内进行（仅在需要时）。与引用计数技术相比，Mark-Sweep 方法占用的空间更少，并且可以干净地处理循环结构，而无需进行复杂的指针操作。它像其他跟踪算法一样，需要一定的堆空间才能正常工作。此外，由于 Mark-Sweep 不会压缩堆，因此系统可能会出现内部碎片增加，导致堆利用率降低（尤其是对于较大的分配）。
• 与变异体的读写操作相比，Mark-Sweep 几乎不增加任何协调开销。对象分配函数是与变异体交互的唯一方式，即使在这种情况下，开销也很小。
• 总的来说，Mark-Sweep 系统需要复杂的分配器来理解和支持堆解析和位图操作。堆管理器可能需要设计非平凡的实现解决方案来处理内部碎片。另一方面，Mark Sweep 由于不移动对象，因此非常适合在非协作上下文中使用，其中语言运行时不与垃圾收集器协调（如果 GC 是作为事后添加的，则可能发生）。不移动的另一个好处是对象地址不会改变。因此，在清除阶段之后不需要进行任何修补。

引用计数

引用计数方法非常简单。它基于计算每个分配的对象有多少指针引用。它是一种简单、本质上是增量的解决方案，因为程序内存管理的开销是分布式的。除了内存管理之外，引用计数还广泛用于操作系统中，作为一种资源管理工具，用于管理文件、套接字等系统资源。

在引用计数技术中，每个分配的对象都有一个引用计数字段。内存管理器负责确保每个对象的引用计数始终等于指向该对象的直接指针引用的数量。下面是该算法的简化版本。

代码

无法回收循环存储是引用计数最主要的缺点。像双向链表和非基本图这样的循环数据结构无法使用简单的引用计数技术成功回收，并且会泄漏内存。

引用计数的优点

• 与跟踪收集器相比，内存管理成本分布在整个应用程序中，从而使系统更加平滑和响应迅速。值得注意的是，处理成本与最终指针引用的子图大小成正比，并且并不总是微不足道的。
• 引用计数系统的空间局部性通常不比实际客户端程序差，而且通常比必须遍历所有活动对象的跟踪 GC 更好。
• 与跟踪收集器不同，跟踪收集器会在收集器执行（通常在堆耗尽时）之前将无法访问的内存保留为未分配状态，而引用计数技术允许立即重用已浪费的内存。由于立即重用，缓存具有更好的时间局部性，从而减少了页面错误。它还可以简化资源清理，因为析构函数可以立即调用，从而加快系统资源释放。空间的即时重用还允许进行改进，例如原地数据结构修改。
• 从技术细节上看，基于引用计数的集合是最简单的垃圾收集方法。如果语言运行时不支持指针操作和/或程序员无法确定/操作对象根，则实现非常简单。
• 程序员可以使用引用计数技术完全控制对象的分配和去分配。在程序员认为安全的地方，可能可以优化掉引用计数成本。这在准确性方面带来了困难，因此需要更高的代码纪律。即使没有智能优化，客户端应用程序的接口和引用计数方法也是紧密耦合的。客户端必须适当地调用增加和减少引用计数的运算。
• 每个项目都带有引用计数字段之上的空间。对于非常小的项目，理论上这可能等于 50% 的开销。必须将此成本与内存单元可以立即重用以及引用计数在收集期间不使用堆空间的事实进行权衡。引用计数系统可以通过使用单个字节来节省空间，而不是为 ref-count 使用完整的字。此类系统使用回退跟踪机制（如 Mark-Sweep）来收集引用计数达到最大值和引用计数（以及循环引用）的对象。
• 与跟踪技术不同，指针更改是免费的，但引用计数成本很高，因为每次指针更新都需要更新两个引用计数才能使程序保持有效。
• 如前所述，引用计数的主要缺点是无法回收循环存储。像双向链表和非基本图这样的循环数据结构无法使用简单的引用计数技术成功回收，并且会泄漏内存。

结论

因此，在本文中，我们了解了数据结构中的垃圾回收以及垃圾回收对于使各种数据结构更高效的重要性。我们还了解了两种主要的垃圾回收算法，即 Mark and Sweep 和 Reference Counting，以及这两种算法的工作原理，以及上述这些垃圾回收算法的显著优点。