Mark-Sweep 与变种算法篇章02-原理篇阅读时间约 40 分钟前置知识了解 GC 基本概念一、引言垃圾回收Garbage Collection简称 GC的核心使命可以归结为一个问题如何自动识别并回收不再被程序使用的内存在数十年的 GC 发展史中最基础也最经典的算法家族就是Mark-Sweep标记-清扫及其变种。Mark-Sweep 由 John McCarthy 在 1960 年为 Lisp 语言首次提出它是所有追踪式 GCTracing GC的鼻祖。在此之后为了解决 Mark-Sweep 的内存碎片化问题衍生出了Mark-Compact标记-压缩算法为了解决压缩开销大的问题又诞生了Copying复制算法。这三种算法构成了现代 GC 的基石几乎所有工业级 GC 实现包括 .NET 的 GC、Java HotSpot 的 G1/ZGC、V8 的 Orinoco都是在这三种算法的基础上组合演变而来。本章将从原理层面深入剖析这三种算法的工作机制并通过对比矩阵帮助读者建立清晰的选型直觉。二、Mark-Sweep 算法Mark-Sweep 算法分为两个阶段标记阶段Mark Phase和清扫阶段Sweep Phase。顾名思义先标记出所有存活对象再清扫掉未被标记的垃圾对象。2.1 标记阶段标记阶段从GC Roots出发遍历整个对象图Object Graph将所有可达对象标记为存活。这个过程本质上是一次图遍历BFS 或 DFS。标记阶段伪代码 function Mark(rootSet): worklist new Queue() for root in rootSet: if root ! null !root.marked: root.marked true worklist.enqueue(root) while !worklist.isEmpty(): obj worklist.dequeue() for ref in obj.references: if ref ! null !ref.marked: ref.marked true worklist.enqueue(ref)关键细节标记位存储每个对象头部需要一个 bit 来记录是否被标记。在 .NET 中这个标记位存储在对象头的SyncBlock中不会额外占用对象体空间。遍历方式.NET 的 GC 使用 BFS广度优先搜索配合一个灰色队列mark queue而非递归 DFS以避免栈溢出。STWStop-The-World在非并发 GC 中标记阶段需要暂停所有应用线程否则对象引用关系可能在遍历过程中变化导致漏标。在 C# 中你可以通过以下代码观察标记阶段的行为using System; using System.Runtime; class MarkPhaseDemo { static void Main() { // 创建对象图root - A - B - C // root - D独立分支 var a new Node(A); var b new Node(B); var c new Node(C); var d new Node(D); a.Next b; b.Next c; // 此时 A、B、C、D 均可达 GC.Collect(); Console.WriteLine($After GC (all reachable): Gen0{GC.CollectionCount(0)}); // 断开 A 的引用链 a null; GC.Collect(); // A、B、C 变为不可达被回收D 仍可达 d null; GC.Collect(); // D 也被回收 } } class Node { public string Name { get; } public Node Next { get; set; } public Node(string name) Name name; ~Node() Console.WriteLine(${Name} finalized); }2.2 清扫阶段清扫阶段遍历整个堆检查每个对象的标记位已标记→ 清除标记位保留对象下一轮 GC 重新标记未标记→ 该对象是垃圾将其空间加入空闲链表Free List清扫阶段伪代码 function Sweep(heap): for each block in heap: if block.marked: block.marked false // 重置标记为下次GC准备 else: freeList.add(block) // 加入空闲链表空闲链表Free List的结构在 Mark-Sweep 中被回收的内存块不会立即被归还给操作系统而是被组织成一个空闲链表。后续分配时GC 从空闲链表中寻找合适大小的块First-Fit找到第一个足够大的块就分配速度快但可能浪费Best-Fit找到最接近请求大小的块减少浪费但搜索慢Next-Fit从上次搜索位置继续找折中方案.NET 的 SOHSmall Object Heap使用的是类似 Next-Fit 的策略以减少搜索开销。2.3 优缺点分析优点优点说明实现简单两阶段流程清晰不需要移动对象对象地址稳定对象不会被移动不需要更新引用适合大对象不需要复制大对象避免复制开销缺点缺点说明内存碎片化回收后产生不连续的空闲块无法分配大对象分配速度慢需要遍历空闲链表寻找合适块STW 时间长标记和清扫都需要遍历整个堆空间利用率低碎片化导致有效可用空间减少碎片化问题图示堆内存布局Mark-Sweep 后 [存活A] [空闲] [存活B] [空闲] [空闲] [存活C] [空闲] [存活D] 16B 8B 32B 16B 8B 24B 16B 16B 总空闲 48B但最大连续空闲块仅 16B → 无法分配 32B 的新对象这就是 Mark-Sweep 最大的痛点——明明有足够的总空闲空间却因为碎片化而无法分配。三、Mark-Compact 算法为了解决 Mark-Sweep 的碎片化问题Mark-Compact 在标记阶段之后增加了一个压缩Compact阶段将所有存活对象移动到堆的一端形成连续的内存空间。3.1 压缩阶段压缩阶段分为三步步骤 1计算新地址遍历堆为每个存活对象计算压缩后的新地址。使用一个空闲指针free pointer从堆起始位置开始依次为存活对象分配新地址计算新地址伪代码 function ComputeNewAddresses(heap): free heap.start for each block in heap: if block.marked: block.newAddress free free block.size return free // 压缩后的空闲指针位置步骤 2更新引用遍历所有存活对象将其内部引用更新为指向对象的新地址更新引用伪代码 function UpdateReferences(heap): for each block in heap: if block.marked: for ref in block.references: if ref ! null: ref.target ref.target.newAddress步骤 3移动对象将每个存活对象从旧地址复制到新地址移动对象伪代码 function MoveObjects(heap): for each block in heap: if block.marked: memcpy(block.newAddress, block, block.size) block.marked false // 重置标记压缩效果图示压缩前 [存活A] [空闲] [存活B] [空闲] [空闲] [存活C] [空闲] [存活D] 16B 8B 32B 16B 8B 24B 16B 16B 压缩后 [存活A] [存活B] [存活C] [存活D] [ 连续空闲 ] 16B 32B 24B 16B 48B可分配任意大小 ≤ 48B在 .NET 中GC 在执行压缩时会使用一个Brick Table砖块表来记录对象移动的映射关系以高效地更新引用。Brick Table 将堆划分为固定大小的砖块每个砖块记录该区域内第一个对象的新地址通过砖块表可以快速定位任意对象的新位置。3.2 优缺点分析优点优点说明消除碎片化压缩后内存连续分配效率高分配速度快空闲空间连续只需移动空闲指针Bump Allocation空间利用率高不存在碎片浪费缺点缺点说明移动开销大需要复制对象数据大对象移动代价极高引用更新复杂需要更新所有指向移动对象的引用STW 时间更长三步操作都需要暂停应用线程不适合大对象移动大对象如数组的内存复制成本很高C# 代码示例——观察压缩行为using System; using System.Runtime.InteropServices; class CompactDemo { static void Main() { // 分配大量小对象制造碎片 var objects new WeakReference[100]; for (int i 0; i 100; i) { objects[i] new WeakReference(new byte[100]); } // 释放一半对象制造碎片 for (int i 0; i 100; i 2) { objects[i] null; } // 触发GC并压缩 GC.Collect(); GC.WaitForPendingFinalizers(); GC.Collect(); // 检查压缩后的内存布局 // 注意实际开发中不应依赖对象地址 var settings new GCMemorySettings(); Console.WriteLine($GC 内存信息:); Console.WriteLine($ 堆大小: {GC.GetTotalMemory(false)} bytes); Console.WriteLine($ Gen0 回收次数: {GC.CollectionCount(0)}); Console.WriteLine($ Gen1 回收次数: {GC.CollectionCount(1)}); Console.WriteLine($ Gen2 回收次数: {GC.CollectionCount(2)}); } }四、Copying 算法Copying 算法由 C.J. Cheney 在 1970 年提出它用一种更优雅的方式同时解决了碎片化和压缩问题——将堆分成两个半区每次只使用一个半区GC 时将存活对象复制到另一个半区。4.1 半区复制工作原理堆布局 ┌──────────────── From 区 ────────┬──────── To 区 ────────┐ │ [A] [B] [垃圾] [C] [垃圾] [D] │ │ └──────────────────────────────────┴───────────────────────┘ GC 后 ┌──────────────────────────────────┬──── To 区 ───────────┐ │ │ [A] [B] [C] [D] [空闲]│ └──────────────────────────────────┴───────────────────────┘ ↑ 新的 From 区Cheney 复制算法Cheney 算法伪代码 function Copy(rootSet, fromSpace, toSpace): // scan 指针已复制但未扫描引用的对象 // free 指针下一个可分配位置 scan toSpace.start free toSpace.start // 复制根直接引用的对象 for root in rootSet: root.target copy(root.target, free) // 扫描已复制对象的引用 while scan free: obj scan for ref in obj.references: ref.target copy(ref.target, free) scan obj.size // 交换半区 swap(fromSpace, toSpace) function copy(obj, free): if obj null: return null if obj.forwarded: return obj.forward // 已复制返回转发地址 // 复制对象到新空间 newAddr free memcpy(newAddr, obj, obj.size) obj.forwarded true obj.forward newAddr free obj.size return newAddr关键特性BFS 遍历Cheney 算法天然使用 BFS 遍历对象图scan指针和free指针之间的对象就是灰色对象已复制但未扫描引用。转发指针Forward Pointer被复制的对象在旧空间留下转发指针指向新空间中的副本确保多次引用同一对象时只复制一次。无碎片化复制后新空间天然连续。无标记位不需要标记位存活对象通过是否被复制来区分。4.2 优缺点分析优点优点说明无碎片化复制后天然连续分配极快Bump Allocation只需移动指针无标记开销不需要标记位和清扫遍历访问局部性好存活对象在复制时被重新排列引用关系更紧凑缺点缺点说明空间利用率 50%始终有一半空间空闲移动开销需要复制存活对象不适合存活率高的堆存活对象越多复制开销越大不适合大对象复制大对象代价极高存活率与效率关系Copying 算法的效率与存活率的关系 存活率 10% → 复制 10% 的对象效率极高 存活率 50% → 复制 50% 的对象效率一般 存活率 90% → 复制 90% 的对象效率极低几乎全在复制 → Copying 算法最适合朝生夕灭的新生代这正是分代 GC 中新生代使用 Copying 算法的理论依据。五、三种算法的对比矩阵维度Mark-SweepMark-CompactCopying碎片化严重无无空间利用率高可用全部堆高可用全部堆低50%半区复制分配速度慢空闲链表搜索快Bump Allocation极快Bump Allocation回收速度中等遍历堆清扫慢三步压缩快只复制存活对象对象移动不移动移动移动引用更新不需要需要需要标记位需要需要不需要适合存活率任意任意低存活率最佳适合对象大小任意中小对象中小对象STW 时间中等长短存活率低时实现复杂度低中中典型应用早期 Lisp GC.NET Gen2 部分.NET Gen0/Gen1, Java Young选型决策树是否需要避免移动对象 ├── 是 → Mark-Sweep但需接受碎片化 └── 否 → 存活率是否较低 ├── 是 30%→ Copying高效复制少量存活对象 └── 否 30%→ Mark-Compact压缩但避免复制开销六、实际 GC 中的组合使用工业级 GC 几乎不会单独使用某一种算法而是根据堆的不同区域特征组合使用。6.1 .NET GC 的组合策略.NET 的堆分为三个代Gen0、Gen1、Gen2加上大对象堆LOH区域算法原因Gen0Copying新生代存活率极低复制开销小Gen1Copying同 Gen0作为 Gen0 到 Gen2 的缓冲Gen2Mark-Sweep 可选 Compact老年代存活率高复制开销大默认只 Sweep碎片严重时才 CompactLOHMark-Sweep 可选 Compact大对象移动代价极高默认不压缩// .NET GC 策略验证代码 using System; using System.Runtime; class GCStrategyDemo { static void Main() { // Gen0 对象快速分配Copying 回收 var smallObj new byte[100]; Console.WriteLine($小对象代: {GC.GetGeneration(smallObj)}); // 0 // 触发多次 GC 使对象晋升 for (int i 0; i 10; i) { GC.Collect(); GC.WaitForPendingFinalizers(); } Console.WriteLine($多次GC后小对象代: {GC.GetGeneration(smallObj)}); // 2 // LOH 对象≥ 85000 bytes直接分配在 LOH var largeObj new byte[85000]; Console.WriteLine($大对象代: {GC.GetGeneration(largeObj)}); // 2LOH 算作 Gen2 // .NET 4.5.1 可以手动请求 LOH 压缩 GCSettings.LargeObjectHeapCompactionMode GCLargeObjectHeapCompactionMode.CompactOnce; GC.Collect(); // 这次 GC 会压缩 LOH Console.WriteLine(LOH 已压缩); } }6.2 Java HotSpot 的组合策略区域算法说明Eden SurvivorCopying新生代存活率低Old GenMark-Compact老年代存活率高Metaspace不会回收元数据区类元数据6.3 Unity Mono/Boehm GC 的策略Unity 早期默认使用Boehm GCBoehm-Demers-Weiser GC它是一种Mark-Sweep 变体不移动对象纯 Mark-Sweep不压缩保守式 GC不依赖精确的类型信息将栈上看起来像指针的值都当作引用碎片化严重长时间运行的游戏容易出现碎片化问题// Unity 中检测 Boehm GC 碎片化的示例 // 注意此代码仅在 Unity Mono 后端有效 #if UNITY_EDITOR using UnityEngine; using System; public class BoehmGCDemo : MonoBehaviour { void Start() { // 分配大量不同大小的对象 var objects new System.WeakReference[1000]; for (int i 0; i 1000; i) { objects[i] new System.WeakReference(new byte[UnityEngine.Random.Range(64, 512)]); } // 随机释放一半 for (int i 0; i 1000; i 2) { objects[i] null; } // 触发 GC GC.Collect(); // Boehm GC 不会压缩碎片化会累积 Debug.Log(Boehm GC 完成回收但碎片未压缩); Debug.Log($堆大小: {GC.GetTotalMemory(false) / 1024 / 1024} MB); } } #endif6.4 Unity IL2CPP Boehm vs .NET Core 的差异特性Unity Boehm.NET Core Server GC算法Mark-Sweep保守式分代 Copying/Compact压缩不支持支持Gen2 LOH 可选分代不分代3 代 LOH并发部分支持完全并发Background GC碎片化严重可控STW长短分代 并发七、总结本章深入剖析了三种基础 GC 算法Mark-Sweep最基础的算法标记存活对象后清扫垃圾。优点是不移动对象、实现简单缺点是碎片化严重、分配速度慢。Unity 的 Boehm GC 就是这一算法的保守式变体。Mark-Compact在 Mark-Sweep 基础上增加压缩阶段消除碎片化。优点是分配快、空间利用率高缺点是移动开销大、STW 时间长。.NET 的 Gen2 回收在碎片严重时会触发压缩。Copying将堆分为两个半区GC 时复制存活对象到另一半区。优点是无碎片、分配极快缺点是空间利用率仅 50%、不适合高存活率场景。.NET 的 Gen0/Gen1 使用此算法。核心洞察没有一种算法是万能的工业级 GC 都是组合策略。算法选择的关键因素是存活率低存活率用 Copying高存活率用 Mark-Sweep/Compact。大对象不适合移动因此 LOH 通常使用 Mark-Sweep 可选压缩。.NET 的分代策略是教科书级的组合实践而 Unity 的 Boehm GC 则展示了 Mark-Sweep 的局限性。理解这三种算法是理解后续分代 GC、并发 GC、区域 GC 等高级主题的基础。在下一章中我们将探讨 .NET 如何利用分代假说将这三种算法组合成一个高效的 GC 系统。