X

曜彤.手记

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

吉 ICP 备10004938号

《垃圾回收算法与实现》读书笔记(一)


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

0. 序章

  1. (Page:3)最初的 GC 算法是 John McCarthy(Lisp 之父)在 1960 年发布的。
  2. (Page:4)三种基本的 GC 算法:

1. 学习 GC 之前

  1. (Page:12)GC 中的对象:由以下两部分组成:

  1. (Page:17)GC 中的“”:是指向对象的指针的“起点”,可以被 mutator 直接引用(调用栈、寄存器、全局变量空间)。
  2. (Page:19)GC 的评判标准:

2. “标记-清除”算法

算法由“标记”以及“清除”两个阶段组成。其中,标记阶段负责把所有活动对象都做上标记;而清除阶段则是把那些没有被标记的对象(非活动对象)进行回收。

  1. (Page:26)标记阶段使用“深度优先搜索(DFS)”会比“广度优先搜索(BFS)”占用更低的内存使用量。
  2. (Page:28)GC 内存分配策略:
  1. (Page:28)“标记-清除” GC 算法的几个阶段:标记(活动对象)、清除(非活动对象)、分配(内存)、合并(清除阶段进行);
  2. (Page:29)“标记-清除” GC 算法的优点:
  1. (Page:29)“标记-清除” GC 算法的缺点:
  1. (Page:32)使用“多空闲链表”法优化空闲链表查找速度:

通常,该方法会为分块大小设定一个上限,分块如果大于等于这个大小,就全部采用单独的一个空闲链表来进行处理(locality)。

  1. (Page:34)利用 “BiBOP(Big Bag Of Pages)法”解决 “GC 标记-清除”算法中的“碎片化”问题。算法思想:将大小相近的对象整理成固定大小的块进行管理,即把堆分割成固定大小的块,让每个块只能够配置同样大小的对象。

BiBOP 法原本是为了消除碎片化,提高堆使用效率而采用的方法。但像上面这样,在多个块中分散残留着同样大小的对象,反而会降低堆使用效率。

  1. (Page:35)位图标记法:收集堆中各个对象的标志位并表格化,不跟对象本身一起管理。在标记时,不在对象头中置位,而是在“位图表格”中单独处理(实现方式:散列表、树形结构、数组等)。

优点:

  1. (Page:38)延迟清除法:可用于减小 GC 的最大暂停时间。

3. “引用计数”算法

  1. (Page:43)该方式将内存管理与 mutator 同时运行(GC 标记-清除只会在没有分块的时候才将垃圾一并回收)。
  2. (Page:44)“引用计数”算法的优点:
  1. (Page:45)“引用计数”算法的缺点:
  1. (Page:46)“延迟引用计数”法:使用 ZCT(Zero Count Table)结构存储引用计数变为 0 的对象。只有在 ZCT 无法存放对象时,再查找整个 ZCT 中引用计数为 0 的对象,并进行释放操作。

  1. (Page:50)“Sticky 引用计数”法:减少引用计数器的位宽。对于溢出的计数,可以选择将其作为“永生对象”;或使用
    “GC 标记-清除”进行管理。
  2. (Page:52)“1 位引用计数”法:是 Sticky 引用计数法的一个极端例子,即引用计数器只有 1 位大小(表示被引用次数是 1 次或多次)。

  1. (Page:55)“部分标记-清除”算法:只对一部分对象使用 GC 标记-清除算法(这里用于查找非活动对象)。

在该算法中有四种对象类型:

4. “GC 复制”算法

即:把某个空间内的活动对象复制到其他空间,再把原空间里的所有对象都回收掉。原空间一般被称为 “From 空间”,存放活动对象的新空间被称为 “To 空间”。

  1. (Page:67)“GC 复制”算法的大致流程:

(待更新)



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