vlambda博客
学习文章列表

【算法】2021年-快速了解GC算法

内存管理方式

  1. 显式内存管理方案 像c/c++那样，用free/delete来动态分配内存，设计显示内存控制方案，是为了让我们能够在写代码的时候注意内存管理，来确保程序的长期稳定和可靠。

    但是也有一些坑：

    虽然有很多编码模式来规范我们代码的写法，而且这些模式要求也成了一些第三方库的trick，但是对于内存问题(比如悬垂指针)造成的争论却从没有停止过，甚至在这种本应该让程序立即停止的错误发生时，程序仍然在运行，并试图获取一些意料之外的内存区域。这些问题在21世纪仍然存在。

    • 由释放活跃对象造成的 悬垂指针(dangling pointer)
    • 双重 free造成的 内存损坏(memory corruption)
    • 由忘记释放内存造成的 内存泄漏(memory leak)
    • API签名中所有权语义建模造成的 组件高耦合(higher coupling between components)

  2. 自动内存管理方案 自动内存管理是所有现代语言的一个重要特性。自动的内存管理方案让程序员们觉得内存是无限制使用的，这样他们就可以将关注点更集中到功能的完成，而不是纠结内存的分配和释放。他有这么些优点：

    • 没有 悬垂指针的问题。
    • 没有 双重释放的问题。
    • 简单的编码方式(无需管理内粗)。
    • 让项目可以更快地迭代

但是自动内存管理并不是一颗银弹，他不能保证你的程序不会出现内存泄漏，帮你管理内存的同时他也降低了程序的运行速度。

自动内存管理基础

  1. 动态内存分配
  2. 垃圾回收

动态内存分配

  1. 堆内存。受分配的对象池。(内存池)
  2. 可以通过 引用来获取堆内存上的对象。
  3. 可以通过 引用来获取堆内存上的句柄。(依序包含对象内存)

句柄提供了一种更新对象的更容易的方式，在对象的内存重分配的时候，就不用去更新所有对象的引用。

堆内存(作为一个allocator分配器)需要对外提供allocate和deallocate的API

垃圾回收

垃圾回收器(Garbage collector)由mutator和collector组成。

  1. mutator: 分配和回收对象，管理执行上下文，对象引用变更等。大型应用一般不只是一个 mutator。
  2. collector: 执行垃圾回收。

垃圾回收算法理想状态

和系统设计一样，垃圾回收系统的设计，也要去平衡各种参数。

  1. 正确性。安全和正确是必须要保证的。
    • 不能重新声明存活对象
    • 安全性通常会牺牲性能和效率
  2. 性能。
  3. 空间消耗。

【算法】2021年-快速了解GC算法

引用计数

引用计数方式会给每个分配的对象挂载一个引用计数属性，该属性的计数等于直接引用到该对象的个数。

像这样

X堆X -> A|1 -> B|1
X内X           ↓
X存X -> C|1 -> D|2 -> E|1
X区X
X域X -> F|1 -> G|1

其中A、C、F是最顶层的对象，他们分别引用了B、D、G，以此类推，D由于被C和B都引用了，因此计数为2。

如果我们执行delete操作，会从当前对象开始，依次减少引用对象的引用计数。比如上图我们从内存中删除A，就变成了

X堆X -> A|0 -> B|0
X内X           ↓
X存X -> C|1 -> D|1 -> E|1
X区X
X域X -> F|1 -> G|1

然后计数为0的对象就会被collector回收掉。

X堆X
X内X
X存X -> C|1 -> D|1 -> E|1
X区X
X域X -> F|1 -> G|1

你肯定看出来了，这是数据结构与算法研究里面的有向图问题，因此，垃圾回收最重要的是处理回环问题，如果回环被放任，就会造成内存泄漏(memory leak)。如下

X堆X -> A|1 -> B|2
X内X               ↖
X存X            ↓    E|1
X区X               ↗
X域X -> C|1 -> D|2

在这个示例中，我们去解除对A和C的引用，会因为D->E->B->D的循环引用而造成内存泄漏。

X堆X        B|1
X内X            ↖
X存X         ↓    E|1   # memory leak
X区X            ↗
X域X        D|1

其中，这种判断环的问题我已经遇到过两次了

  • 判断 excel单元格公式的循环引用，若循环引用，则公式非法
  • 判断一个对象数组内的对象是否有循环引用

估计这一类的问题，都是从这儿衍生出来的。核心要点：有向图的连通性检测、循环检测

引用计数算法权衡

  1. 响应。内存管理的开销是分布在整个程序中的，相比跟踪搜集器的方法，是要平滑一些，也更响应式。注意处理的开销和最后一个指针的引用图相关(可能造成 memory leak)，不过可能在某些情况下，并不需要关注这个。
  2. 缓存性能。用地址空间来处理内存的方式比追踪回收算法要好一些，追踪回收算法还需要跟踪每个存活对象的整个生命周期，而引用计数相当于是用空间缓存来加快计算对象的存活性。
  3. 即时内存的重复使用。 引用计数算法允许对释放内存的立即重复使用。由于引用计数到0就可以快速释放内存，因此，我们就可以在内存释放后 安全地分配到另外的对象上。当然，这种方式也可以让我们 原地更新对象的性能得到提升
  4. 易于实现。 引用计数算法是目前的一些垃圾回收算法里面最容易实现的。
  5. 空间开销。每个对象都要设置一个引用计数器，很显然，根据2/8法则，如果你的系统内存在很多小对象，那可能整个 引用计数的开销占用的比率就更高，极端情况下就到50%的内存占用。但是，这种空间开销我们要和我们得到的收益进行权衡。比如让我们快速重复使用内存，实际上增加了内存的使用率，而且 引用计数在回收期并不依赖堆上的内存。
  6. 时间开销。我们要计算每个对象引用链路上的所有对象的引用并加以更新，这是一种消耗，另外就是遇到有环状结构的引用路径，需要有对应的方式去处理，极端情况下，会有双向引用的存在，两个对象互相引用，也需要时间去处理他们以决定是否同时删除这两个对象。

标记清除算法

内存管理系统有两个通用的责任：

  1. 给新对象分配内存
  2. 从旧对象回收内存

一个垃圾回收器的单一职责就是从程序执行上下文中回收那些不再被使用的内存。为了实现这个目标，它就必须知道哪些是存活对象(alive object)，哪些是死对象(dead object)。就像我们在第一部分讲的一样，很多垃圾回收算法认为一个能触及的对象就是alive的，而一个无法被引用链寻找到的对象就是dead。

垃圾回收算法的分类

通常我们可以把垃圾回收算法分为这些类型：

  1. 标记清除(mark-sweep collection)
  2. 标记合并(mark-compact collection)
  3. 复制(copying collection)
  4. 引用计数(reference counting)

通常垃圾回收器(GC)的实现是几个算法一起达成的，比如把引用计数和标记清除合并起来构建一个垃圾回收器。

GC如何进行？何时开始？

当运行时发现堆上内存快要耗尽了，并且已经没有足够的内存来响应mutator(应用线程)创建对象内存(堆上)的需求时，就会触发内存回收(GC)。

// 伪代码
function allocator(obj) {
  let ref = allocate(obj);
  // 不足以分配内存
  if (!ref) {
    // 执行回收
    gc();
    // 尝试再次分配
    ref = allocate(obj);
    // 还是失败
    if (!ref) {
      throw new Error('[memory leak] Out of memory')
    }
  }

  return ref
}

标记清除

标记清除有两个阶段

  1. 标记(mark phase)
  2. 清除(sweep phase)

在标记阶段，collector(收集器)遍历所有的顶层对象(roots object)，然后标记每个对象是否被使用，需要一个bit位来处理标记。所谓顶层对象，乃当前执行上下文的最顶层的对象，比如window下挂载的对象或是一个闭包下分配的局部变量，甚至是那些监听器。

在清除阶段。垃圾收集器直接回收那些没有被标记的对象。

// 伪代码

// 执行gc的方式
function gc() {
  // 线程暂停
  stopAllMutators();
  // 标记
  markRoots();
  // 清除
  sweep();
  // 恢复线程
  resumeAllMutators();
}

// 标记顶层对象
function markRoots() {
  candidates = Stack();
  Roots.forEach(obj => {
    // 递归标记后续对象
    if (obj !== undefined && !alreadyMarked(obj)) {
      setMarked(obj);
      candidates.push(obj);
      mark(candidates);
    }
  })
}

// 标记
function mark(candidates) {
  while(candidates.length) {
    ref = candidates.pop();
    // 递归标记后续对象
    pointers(ref).forEach(pointer => {
      if (pointer !== undefined && !alreadyMarked(pointer)) {
        setMarked(pointer);
        candidates.push(pointer);
      }
    })
  }
}

// 清除
function sweep() {
  let scan = startOfHeap();
  let end = endOfHeap();
  while(scan < end) {
    if (alreadyMarked(scan)) {
      unsetMarked(scan);
    } else {
      free(scan);
    }
    scan = nextObject(scan);
  }
}

function nextObject(address) {
  // native code
  // 从堆上取下一个对象的地址
}

标记阶段

  1. 标记阶段不直接确认哪个对象 属于垃圾，它只负责给对象打标(也就是 选择出那些不是垃圾的对象)。
  2. 很显然，标记是一个递归操作。为了确认一个对象是 alive的，会递归寻找对象的子对象。
  3. 标记阶段很像是引用计数，不过我们不需要独立的空间记录每个对象的引用状态，我们只存储每条链路是否存活。
  4. 没有被标记的对象不需要记录，他们(包括整条链路)将在清除阶段被释放。

清除阶段

  1. 从堆上第一个对象开始扫描，逐个查看每个顶层对象所代表的链路是否被标记
  2. 未标记的数据直接释放。

权衡

  • 缓存性能。

  • 速度。

  • 空间占用。

    标记是一个耗费资源的操作，不应该频繁触发标记。

  • 线程操作开销(mutation overhead)。

    在线程走到堆内存分配的时候，标记和清除的接口才被引用到，标记和清除是独立的操作，通过线程的操作来串联。

  • 分配器开销(allocator overhead)。

    分配内存的消耗。标记数据的消耗。

  • 侵入性(invasiveness)

    标记清除是侵入性的。collector在工作时要打断线程工作，这可能是一个短暂的打断(标记、清除时间消耗和空间消耗)，也可能是一个长时间的打断，这完全取决于当前的算法运行情况。

总结

著名的标记清除算法。

  1. Dijkstra's Tri-color Marking。狄杰克斯拉三色标记算法。
    • 白色、灰色、黑色。最开始全白，然后全局变量和上下文对象置为灰色
    • 然后把灰色对象置为黑色，原灰色对象指向的对象置为灰色。依次类推。
    • 当没有对象可以置为灰色时，所有的白色对象都是可清除对象。
  2. Lazy Sweep and Prefetching。懒清除&预加载算法。
    • 某对象一旦未被标记，它永远都不会被 mutator再访问
    • mutator不能修改 bitmap

未完待续...

  • 标记合并
  • 复制收集



推荐阅读

数码宝贝物语 时空异客 学习版 数码宝贝物语 时空异客 学习版
threejs+blender页面滚动伴随着三维动画 threejs+blender页面滚动伴随着三维动画

相关文章