JS `Mark-Sweep-Compact` GC 算法在 V8 中的实现细节

各位观众老爷，大家好！今天咱们来聊聊 V8 引擎里那个神秘又强大的家伙——Mark-Sweep-Compact 垃圾回收算法。这玩意儿听起来高大上，但其实没那么可怕，咱们慢慢把它扒个精光！

首先，咱们得明白垃圾回收是干啥的。简单来说，就是程序运行的时候会产生很多没用的对象，占用着内存。如果这些没用的对象一直堆在那里，内存迟早会被耗光，程序就崩溃了。所以，我们需要一种机制来自动清理这些垃圾，释放内存，这就是垃圾回收。

V8 引擎是 Google Chrome 和 Node.js 的幕后功臣，它的垃圾回收机制非常复杂，其中 Mark-Sweep-Compact 算法是主力军之一。它主要负责 Old Generation 的垃圾回收，也就是那些活得比较久的对象。

为什么需要 Mark-Sweep-Compact？

在了解算法细节之前，我们先搞清楚为什么需要这么一种算法。V8 的内存空间被分为几个不同的区域，比如 New Generation 和 Old Generation。New Generation 主要存放存活时间较短的对象，用 Scavenge 算法（也叫 Copying GC）来回收效率很高。但是，对于存活时间较长的对象，如果也频繁地进行复制操作，那开销就太大了。

这就好比整理房间，New Generation 就像你每天整理的桌面，东西不多，随便扫扫就干净了。而 Old Generation 就像你的书架，东西很多，而且很多都是你暂时用不到但以后可能还会用到的东西，你不能随便扔，也不能频繁搬动，不然太累了。

因此，我们需要一种更适合 Old Generation 的垃圾回收算法，Mark-Sweep-Compact 就应运而生了。

Mark-Sweep-Compact 算法三部曲

Mark-Sweep-Compact 算法，顾名思义，分为三个阶段：

Mark (标记): 从根对象（比如全局对象、调用栈等）开始，遍历所有可达的对象，并给它们打上标记。这个过程就像警察抓小偷，先确定哪些是“好人”（可达对象），给他们贴上标签，免得误伤。
Sweep (清除): 遍历整个堆，找到所有没有被标记的对象，这些就是垃圾，然后把它们清除掉，释放内存。就像警察把没标签的“坏人”（不可达对象）抓走。
Compact (整理/压缩): 把存活的对象都移动到堆的一端，整理内存空间，消除碎片。就像警察把“好人”都集中到安全区域，把空出来的地盘整理干净。

代码示例 (伪代码)

为了更好地理解，咱们用伪代码来模拟一下这三个阶段：

// 假设 Heap 是整个堆空间，Object 是堆中的对象

// Mark 阶段
function mark(heap) {
  let rootObjects = getRootObjects(); // 获取根对象
  let markedObjects = new Set(); // 用于存储已标记的对象

  function markObject(object) {
    if (markedObjects.has(object)) {
      return; // 已经标记过，直接返回
    }

    markedObjects.add(object);
    object.isMarked = true; // 给对象打上标记

    // 遍历对象的引用，递归标记
    for (let reference of object.references) {
      markObject(reference);
    }
  }

  // 从根对象开始标记
  for (let rootObject of rootObjects) {
    markObject(rootObject);
  }
}

// Sweep 阶段
function sweep(heap) {
  for (let object of heap) {
    if (!object.isMarked) {
      // 对象没有被标记，是垃圾，释放内存
      freeMemory(object);
      object.isAlive = false; // 标记对象为死亡状态
    }
  }
}

// Compact 阶段
function compact(heap) {
  let liveObjects = []; // 用于存储存活的对象
  let freeIndex = 0; // 下一个存活对象存放的位置

  // 收集存活的对象
  for (let object of heap) {
    if (object.isAlive) {
      liveObjects.push(object);
    }
  }

  // 移动存活对象到堆的起始位置
  for (let object of liveObjects) {
    // 将对象移动到新的位置
    moveObject(object, freeIndex);
    object.newAddress = freeIndex; // 更新对象的地址
    freeIndex += object.size; // 更新下一个对象的位置
  }

  // 更新所有引用
  updateReferences(heap);
}

// 更新所有对象的引用，指向新的地址
function updateReferences(heap) {
  for (let object of heap) {
    if (object.isAlive) {
      for (let i = 0; i < object.references.length; i++) {
        let oldReference = object.references[i];
        if (oldReference && oldReference.newAddress !== undefined) {
          object.references[i] = oldReference.newAddress; // 更新引用
        }
      }
    }
  }
}

// 辅助函数（实际实现会更复杂）
function getRootObjects() { /* ... */ }
function freeMemory(object) { /* ... */ }
function moveObject(object, newAddress) { /* ... */ }

V8 中的实现细节

V8 的 Mark-Sweep-Compact 算法实现比上面的伪代码复杂得多，它有很多优化策略，包括：

增量标记 (Incremental Marking): V8 不会一次性完成所有的标记工作，而是将标记过程分成多个小步，穿插在 JavaScript 代码的执行过程中。这样可以避免垃圾回收长时间阻塞主线程，提高用户体验。
写屏障 (Write Barrier): 在增量标记过程中，如果一个已经被标记的对象被修改，指向了另一个未被标记的对象，那么就需要重新标记这个新对象。写屏障就是用来检测这种修改，并触发重新标记的机制。
Remembered Set: 为了加速增量标记，V8 使用 Remembered Set 记录 Old Generation 对象对 New Generation 对象的引用。这样在 New Generation GC 时，只需要扫描 Remembered Set 中的对象，就可以找到所有 Old Generation 对 New Generation 的引用，避免全堆扫描。
并行标记 (Parallel Marking): V8 允许多个线程同时进行标记工作，进一步缩短标记时间。
并发整理 (Concurrent Compacting): 在某些情况下，V8 可以在 JavaScript 代码运行的同时进行整理操作，但这需要更复杂的同步机制来保证数据一致性。

表格总结 V8 的优化策略：

优化策略	描述	目的
增量标记	将标记过程分成多个小步，穿插在 JavaScript 代码的执行过程中。	避免垃圾回收长时间阻塞主线程，提高用户体验。
写屏障	检测对象修改，并触发重新标记机制，保证增量标记的正确性。	保证增量标记过程中，所有可达对象都能被正确标记。
Remembered Set	记录 Old Generation 对象对 New Generation 对象的引用。	加速 New Generation GC，避免全堆扫描。
并行标记	允许多个线程同时进行标记工作。	进一步缩短标记时间。
并发整理	在 JavaScript 代码运行的同时进行整理操作。	减少整理过程对主线程的阻塞。

增量标记和写屏障的代码示例 (简化版)：

// 假设 object 是堆中的一个对象

// 写屏障函数
function writeBarrier(object, field, newValue) {
  // 如果对象已经被标记，并且新值指向一个未被标记的对象
  if (object.isMarked && !newValue.isMarked) {
    markObject(newValue); // 重新标记新对象
  }

  object[field] = newValue; // 执行赋值操作
}

// 示例：使用写屏障
let obj1 = { value: null, isMarked: false };
let obj2 = { value: 10, isMarked: false };

mark(heap); // 初始标记

// 模拟修改对象
writeBarrier(obj1, "value", obj2); // 使用写屏障进行赋值

总结

Mark-Sweep-Compact 算法是 V8 引擎中 Old Generation 垃圾回收的核心算法。它通过标记、清除和整理三个阶段，有效地回收垃圾，释放内存，并减少内存碎片。为了提高性能，V8 采用了多种优化策略，包括增量标记、写屏障、Remembered Set、并行标记和并发整理。

当然，V8 的垃圾回收机制远不止这些，还有很多其他的细节和优化策略。但是，掌握了 Mark-Sweep-Compact 算法的基本原理，就相当于掌握了 V8 垃圾回收的一把钥匙，可以帮助我们更好地理解 V8 的工作原理，并编写更高效的 JavaScript 代码。

希望今天的讲座能让大家对 V8 的 Mark-Sweep-Compact 算法有更深入的了解。记住，垃圾回收虽然复杂，但只要用心学习，总能把它搞明白的！

发表回复 取消回复

发表回复取消回复