X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938-2号

《垃圾回收算法与实现》读书笔记(第 1-5 章)


为了进一步了解 Wasm GC 提案,遂找本书来看看。

所有涉及的 GC 算法如下:

Chapter 0:序章

  1. (Page:3)最初的 GC 算法是由 John McCarthy(Lisp 之父)在 1960 年发布的。
  2. (Page:4)三种基本的 GC 算法(其他均为这三种类型的衍生):

Chapter 1:学习 GC 之前

  1. (Page:12)GC 中的对象:即“通过应用程序利用的数据的集合”。对象配置在内存空间里,GC 根据情况将配置好的对象进行移动或销毁,是 GC 的基本单位。一个对象一般由以下两部分组成:

  1. (Page:14)对象和指针:

  1. (Page:17)GC 中的“root)”:是指向对象的指针的“起点”(调用栈寄存器全局变量空间),可以被 mutator 直接引用。mutator 的本质即“应用程序”,其可进行两种操作 —— “生成对象”与“更新指针”。
  2. (Page:19)一些 GC 评判标准:

Chapter 2:“标记-清除”算法

算法由“标记”以及“清除”两个阶段组成。其中,标记阶段负责把所有活动对象都做上标记;而清除阶段则是把那些没有被标记的对象(非活动对象)进行回收。在半个世纪后的今天,该算法依然是各种处理程序常用的 GC 算法。

  1. (Page:26)标记阶段使用“深度优先搜索(DFS)”一般会比“广度优先搜索(BFS)”占用更低的内存使用量。因为 BFS 需要额外的栈来存放待遍历的子树(指针),最多需要存放与最后一层子节点相同个数的子树(指针);相反,DFS 最多只会有与树高度呈正比数量的节点(指针)在内存中
  2. (Page:26)“清除阶段”在整理“空闲链表”时,如果某个对象需要被清理,则可以直接动态在该对象的域中分配一个字段 next(对象原本的内容会被破坏)以存储空闲链表下一个对象的位置(指针)。
  3. (Page:28)“标记-清除”算法的内存再分配(从空闲链表)策略:
  1. (Page:28)“标记-清除” GC 算法的几个阶段:
  1. (Page:29)“标记-清除” GC 算法的特点:
  1. (Page:32)多空闲链表:可用于优化分配内存时空闲链表的查找速度。通常,该方法会为分块大小设定一个上限,分块如果大于等于这个大小,就全部采用单独的一个空闲链表来进行处理(基于 locality)。

  1. (Page:34)BiBOPBig Bag Of Pages):将大小相近的对象整理成固定大小的块进行管理,即把堆分割成固定大小的块,让每个块只能够配置同样大小的对象。该算法需配合“多空闲链表”一起使用。

  1. (Page:35)位图标记Bitmap Marking):收集堆中各个对象的标志位并表格化,不跟对象本身一起管理。在标记时,不在对象头中置位,而是在“位图表格”中单独处理(实现方式:散列表、树形结构、数组等)。其优点在于:与 COW 兼容,且清除操作更加高效。

  1. (Page:38)延迟清除Lazy Sweep):一定程度上可用于减小 GC 的最大暂停时间。其基本原理是只在分配时执行必要的遍历和清理工作。即每次需要分配内存时,直接遍历当前堆对象,查找是否有未被标记且大小合适的块可以返回,若有则返回。同时过程中,将遍历到的块置位。下次再分配时仍从上一次找到分块的右侧分块开始继续遍历,直到遍历完所有堆对象。若没有找到合适的块,则执行标记,然后再重新遍历。若仍未找到分块,则返回错误。

Chapter 3:“引用计数”算法

  1. (Page:43)该方式将内存管理与 mutator 的运行同时进行(而“标记-清除”法只会在没有分块时才将垃圾一并回收)。对计数器进行增减时需要“先增再减”,以避免当 *ptrobj 是同一对象时引发的“空指针引用”情况

  1. (Page:44)“引用计数”算法的特点:
  1. (Page:46)延迟引用计数Deferred Reference Counting):让从根引用的指针(栈上对象)其变化不反映在计数器上(而堆上的引用改变扔会计数)。即使用 ZCTZero Count Table)表结构存储引用计数变为 0 的对象。当 ZCT 无法存放对象时,会进行 root 引用对象的计数变更,然后查找整个 ZCT 中引用计数仍然为 0 的对象,并进行释放操作。最后再将 root 引用对象的计数递减。

Deferred reference counting reduces the cost of maintaining reference counts by avoiding adjustments when the reference is stored on the stack.

On many systems, the majority of stores are made into local variables, which are kept on the stack. Deferred reference counting leaves those out and counts only references stored in heap objects. This requires compiler support, but can lead to substantial performance improvements.

  1. (Page:50)Sticky 引用计数Sticky Reference Counting):用于减少引用计数器的位宽。对于溢出的计数:
  1. (Page:52)1 位引用计数1bit Reference Counting):Sticky 引用计数法的一个极端例子,即引用计数器只有 1 位大小(0 - 表示被引用数为 1,1 - 表示被引用数大于等于 2)。

  1. (Page:55)部分标记-清除Partial Mark & Sweep):只对“可能有循环引用的对象群”使用 GC 标记-清除算法(这里用于查找非活动对象),而对其他对象进行内存管理时使用引用计数法。

Chapter 4:“GC 复制”算法

  1. (Page:67)“GC 复制”算法的大致流程:只把某个空间内的活动对象复制到其他空间,再把原空间里的所有对象都回收掉。原空间一般被称为 “From 空间”,存放活动对象的新空间被称为 “To 空间”。GC 复制算法是利用 From 空间进行分配的,当 From 空间被完全占满时,GC 会将活动对象全部复制到 To 空间。当复制完成后,该算法会把 From 空间和 To 空间互换(即作用对调),GC 就结束了。From 空间和 To 空间大小必须一致。这是为了保证能把 From 空间中的所有活动对象都收纳到 To 空间内。

  1. (Page:74)来自 Cheney 的“迭代进行复制算法“:优化递归的 copy 过程。

  1. (Page:78)近似深度优先搜索方法

  1. (Page:83)多空间复制算法:把堆 N 等分,对其中 2 块空间执行 GC 复制算法(From 和 To),对剩下的 N-2 块空间执行 GC 标记-清除算法。

Chapter 5:“标记-压缩”算法

GC 标记-压缩算法由“标记阶段”和“压缩阶段”构成。其中的“标记”阶段与“标记-清除”算法中的同名阶段完全相同。接下来的压缩阶段将通过数次搜索堆来重新装填活动对象。与 GC 复制算法不同的是,该算法不用牺牲半个堆

  1. (Page:89)LISP2 算法

  1. (Page:95)Two-Finger 算法:需要搜索 2 次堆。

  1. (Page:100)表格算法

  1. (Page:106)ImmixGC 算法:将 GC 标记-清除算法与压缩组合在了一起。该算法被实现到了 JikesRVM 与 MMTk 中。



这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)