《垃圾回收的算法与实现》读书笔记

文章目录
  1. 1. 序章
  2. 2. 算法篇
    1. 2.1. 学习GC之前
    2. 2.2. GC-清除算法
    3. 2.3. 引用计数法
    4. 2.4. GC复制法
    5. 2.5. GC标记-压缩算法
    6. 2.6. 保守GC
    7. 2.7. 分代垃圾回收
    8. 2.8. 增量式垃圾回收
    9. 2.9. RC Immix算法
  3. 3. 实现篇

序章

  1. GC 把程序不用的内存空间视为垃圾, 是管理堆中已分配对象的机制, GC 要做的有两件事

    • 找到内存空间里的垃圾
    • 回收垃圾,让程序员能再次利用这部分空间
  2. 分配到内存空间中的对象中那些能通过mutator 引用的对象称为“活动对象”。反过来,把分配到堆中那些不能通过程序引用的对象称为“非活动对象”。也就是说,不能通过程序引用的对象已经没有人搭理了,所以死掉了。死掉的对象(即非活动对象)我们就称为“垃圾”。

  3. 不使用GC 会导致的问题

    • 忘记释放内存:内存泄漏
    • 忘记初始化指向释放对象的内存空间的指针:野指针/悬垂指针(dangling pointer)
    • 错误释放了使用中的内存空间的情况
    • ……

算法篇

学习GC之前

  1. 在GC 的世界中,对象表示的是“通过应用程序利用的数据的集合”。对象由头(header)和域(field)构成。对象中保存对象本身信息的部分称为“头”。头主要含有:对象的大小和对象的种类;对象使用者在对象中可访问的部分称为“域“。
  2. 根(root)这个词的意思是“根基”“根底”。在GC 的世界里,根是指向对象的指针的“起点”部分。调用栈、寄存器以及全局变量空间都是根。
  3. GC 算法性能
    • 吞吐量:GC管理的堆大小 / GC所花费的时间。
    • 最大暂停时间:因执行GC 而暂停执行mutator 的最长时间。
    • 堆使用效率:,堆使用效率和吞吐量,以及最大暂停时间不可兼得。简单地说就是:可用的堆越大,GC 运行越快;相反,越想有效地利用有限的堆,GC 花费的时间就越长。
    • 访问的局部性:具有引用关系的对象之间通常很可能存在连续访问的情况。这在多数程序中都很常见,称为“访问的局部性”。考虑到访问的局部性,把具有引用关系的对象安排在堆中较近的位置,就能提高在缓存中读取到想利用的数据的概率,令mutator 高速运行。

GC-清除算法

  1. 算法概述: GC 标记- 清除算法由标记阶段和清除阶段构成。标记阶段是把所有活动对象都做上标记的阶段。清除阶段是把那些没有标记的对象,也就是非活动对象回收的阶段。通过这两个阶段,就可以令不能利用的内存空间重新得到利用。

  2. 伪代码实现:

    1
    2
    3
    4
    mark_sweep() {  
    mark_phase()
    sweep_phase()
    }
  3. 标记的两个阶段

    • 标记阶段:标记阶段就是“遍历对象并标记”的处理过程。
    • 清除阶段:在清除阶段中,collector 会遍历整个堆,回收没有打上标记的对象(即垃圾),使其能再次得到利用。回收对象就是把对象作为分块,连接到被称为“空闲链表”的单向链表。在之后进行分配时只要遍历这个空闲链表,就可以找到分块了。在清除阶段,程序会遍历所有堆,进行垃圾回收。也就是说,所花费时间与堆大小成正比。堆越大,清除阶段所花费的时间就会越长。
  4. 搜索对象并进行标记时使用的是深度优先搜索(depth -first search)。这是尽可能从深
    度上搜索树形结构的方法。另一方面,还有广度优先搜索(breadth -first search)方法。这是尽可能从广度上搜索树形结构的方法。

  5. GC 会搜索所有对象。不管使用什么搜索方法,搜索相关的步骤数(调查的对象数量)都不会
    有差别。另一方面,比较一下内存使用量(已存储的对象数量)就可以知道,深度优先搜索比广度优先
    搜索更能压低内存使用量。因此我们在标记阶段经常用到深度优先搜索。

  6. GC 标记- 清除算法

    • 优点: 算法简单,实现容易;与保守式GC 算法兼容。
    • 缺点:碎片化,分配速度,与写时复制技术不兼容。
  7. GC 标记- 清除算法中分块不是连续的,因此每次分配都必须遍历空闲链表,找到足够大的分块。

  8. GC 标记- 清除算法就存在一个问题—与写时复制技术不兼容。即使没重写对象,GC 也会设置所有活动对象的标志位,这样就会频繁发生本不应该发生的复制,压迫到内存空间。

  9. 标记- 清除算法在“清除”阶段并非只是把分块放在1个“空闲链表”中,事实上,会按照分块大小创建不同的“空闲链表”,同时用一个数组来存储指向这些链表的地址。这样一来,只要按照mutator 所申请的分块大小选择空闲链表,就能在短时间内找到符合条件的分块了。P32

  10. BiBOP 法:把堆分割成固定大小的块,让每个块只能配置同样大小的对象。因为每个块中只能配
    置同样大小的对象,所以不可能出现大小不均的分块。

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

  11. 位图标记:只收集各个对象的标志位并表格化,不跟对象一起管理。在标记的时候,不在对象的头里置位,而是在这个表格中的特定场所置位。像这样集合了用于标记的位的表格称为“位图表格”(bitmap table),利用这个表格进行标记的行为称为“位图标记”。位图表格的实现方法有多种,例如散列表和树形结构等。

    位图标记具有与与写时复制技术兼容、清除操作更高效的优点。

引用计数法

  1. 引用计数法中引入了一个概念,那就是“计数器”。计数器表示的是对象的人气指数,
    也就是有多少程序引用了这个对象(被引用数)。
  2. 引用计数法优点:
    • 可即刻回收垃圾:当被引用数的值为0 时,对象马上就会把自己作为空闲空间连接到空闲链表。也就是说,各个对象在变成垃圾的同时就会立刻被回收。
    • 最大暂停时间短:每次通过执行mutator 生成垃圾时这部分垃圾都会被回收,因而大幅度地削减了mutator 的最大暂停时间。
    • 没有必要沿指针查找:没必要由根沿指针查找。
  3. 引用计数法缺点:
    • 计数器值的增减处理繁重。
    • 计数器需要占用很多位。
    • 实现烦琐复杂。
    • 循环引用无法回收。

GC复制法

  1. GC 复制算法是利用From 空间进行分配的。当From 空间被完全占满时,GC 会将活动对象全部复制到To 空间。当复制完成后,该算法会把From 空间和To 空间互换,GC 也就结束了。From 空间和To 空间大小必须一致。这是为了保证能把From 空间中的所有活动对象都收纳到To 空间里。
  2. GC 复制算法优点:
    • 优秀的吞吐量:GC 复制算法消耗的时间是与活动对象的数量成比例的。GC 标记- 清除算法消耗的吞吐量是搜索活动对象(标记阶段)所花费的时间和搜索整体堆(清除阶段)所花费的时间之和;
    • 可实现高速分配:GC 复制算法不使用空闲链表。这是因为分块是一个连续的内存空间。因此,调查这个分块的大小,只要这个分块大小不小于所申请的大小,那么移动$free 指针就可以进行分配了;
    • 不会发生碎片化:复制后把对象重新集中,放在堆的一端;
    • 与缓存兼容:GC 复制算法中有引用关系的对象会被安排在堆里离彼此较近的位置。
  3. GC 复制算法缺点:
    • 堆使用效率低下:只有一半堆能被使用;
    • 不兼容保守式GC 算法:GC 复制算法必须移动对象重写指针跟保守式GC 算法不相容;
    • 递归调用函数:复制某个对象时要递归复制它的子对象,使用了递归。递归效率较低,同时还有栈溢出的风险。Cheney 的GC 复制算法使用了迭代代替了递归调用。
  4. Fenichel 和Yochelson 的GC 复制算法采用的是深度优先搜索,而Cheney 的复制算法采用的则是广度优先搜索。堆兼用作队列,正是Cheney 算法的一大优点。不用特意为队列留出多余的内存空间就能进行搜索。
  5. 多空间复制算法: 把堆N 等分,对其中2 块空间执行GC 复制算法,对剩下的(N-2)块空间执行GC 标记- 清除算法.
  6. 多空间复制法优缺点:
  • 优点:多空间复制算法没有将堆二等分,而是分割成了更多块空间,从而更有效地利用了堆。以往的GC 复制算法只能使用半个堆,而多空间复制算法仅仅需要空出一个分块,不能使用的只有1/N 个堆。
  • 缺点:执行GC 复制算法的只有N 等分中的两块空间,对于剩下的(N-2)块空间执行的是GC标记- 清除算法。因此就出现了GC 标记- 清除算法固有的问题—分配耗费时间、分块碎片化等。

GC标记-压缩算法

  1. GC 标记- 压缩算法由标记阶段和压缩阶段构成。标记阶段和GC 标记- 清除算法段完全一样,压缩阶段通过数次搜索堆来重新装填活动对象。压缩阶段并不会改变对象的排列顺序,只是缩小了它们之间的空隙,把它们聚集到了堆的一端。
  2. 优点:可有效利用堆。堆使用效率几乎是GC 复制算法的2 倍,同时也避免了管GC 标记- 清除算法中碎片化的缺点。
  3. 缺点:压缩花费计算成本。Lisp2 算法的压缩中,必须对整个堆进行3 次搜索,Two-Finger算法需要搜索2 次堆。

保守GC

  1. 保守式GC(Conservative GC)指的是“不能识别指针和非指针的GC”。在运行GC 时采
    取的是一种保守的态度,即“把可疑的东西看作指针,稳妥处理”。
  2. 寄存器、调用栈和全局变量空间中的根都是不明确的根。
  3. 保守式GC 在检查不明确的根时所进行的基本项目:
  • 是不是被正确对齐的值?(在32 位CPU 的情况下,为4 的倍数)
  • 是不是指着堆内?
  • 是不是指着对象的开头?
  1. 保守式GC优缺点:
  • 优点:语言处理程序不依赖于GC;
  • 缺点:识别指针和非指针需要付出成本、能够使用的GC 算法有限、错误识别指针会压迫堆。
  1. 准确式GC(Exact GC)和保守式GC 正好相反,它是能正确识别指针和非指针的GC。GC 之后,堆里只会留下活动对象。缺点是当创建准确式GC 时,语言处理程序必须对GC 进行一些支援。
  2. 保守式GC 有个缺点,就是“不能使用GC 复制算法等移动对象的算法”。解决这个问题的方法之一就是“间接引用”,即可经由根和对象之间的句柄(handle)来间接地处理对象。缺点是会拉低访问对象内数据的速度,这会关系到整个语言处理程序的速度。

分代垃圾回收

  1. 刚生成的对象称为新生代对象,到达一定年龄的对象则称为老年代对象。,经历过一次GC 后活下来的对象年龄为1 岁。

  2. 新生代对象不只会被根和新生代空间引用,也可能被老年代对象引用。

    记录集用来记录从老年代对象到新生代对象的引用。这样在新生代GC 时就可以不搜索老年代空间的所有对象,只通过搜索记录集来发现从老年代对象到新生代对象的引用。新生代GC时将记录集看成根(像根一样的东西),并进行搜索,以发现指向新生代空间的指针。

  3. 在Ungar 的分代垃圾回收中,对象的头部中除了包含对象的种类和大小之外,还有以下
    这3 条信息。

    • 对象的年龄(age)
    • 已经复制完毕的标志(forwarded)
    • 已经向记录集记录完毕的标志(remembered)

    forwarded是用来防止重复复制相同对象的标志;
    remembered 用来防止向记录集中重复记录的标志;
    remembered 只用于老年代对象,age 和forwarded 只用于新生代对象。

  4. 在分代垃圾回收中,为了将老年代对象记录到记录集里,我们利用写入屏障(write barrier)。在mutator 更新对象间的指针的操作中,写入屏障是不可或缺的。

  5. 通常的GC 复制算法把空间二等分为From 空间和To 空间,即使From 空间里的对象都还
    活着,也确保能把它们收纳到To 空间里去。不过在Ungar 的分代垃圾回收里,To 幸存空间必
    须收纳From 幸存空间以及生成空间中的活动对象。From 幸存空间和生存空间的点大小比To 幸存空间大,所以如果活动对象很多,To 幸存空间就无法容纳下它们。
    当发生这种情况时,稳妥起见只能把老年代空间作为复制的目标空间。当然,如果频繁发生
    这种情况,分代垃圾回收的优点就会淡化。

  6. 分代垃圾回收优点:

    正如Ungar所说的那样:“据实验表明,分代垃圾回收花费的时间是GC 复制算法的1/4。”可见分代垃圾回收的导入非常明显地改善了吞吐量

  7. 写入屏障导致的额外负担降低了吞吐量。只有当新生代GC 带来的速度提升效果
    大于写入屏障对速度造成的影响时,分代垃圾回收才能够更好地发挥作用。当这个大小关系
    不成立时,分代垃圾回收就没有什么作用,或者说反而可能会起到反作用。

  8. 多代垃圾回收(Multi-generational GC)中,除了最老的那一代之外,每代都有一个记录集。X 代的记录集只记录来自比X 老的其他代的引用。

    分为2 代或者3 代是最好的。P157

  9. 列车垃圾回收(Train GC):将老年代空间按照一定大小划分,每个划分出来的空间称为车厢,由1个以上的车厢连接成的东西就叫作列车。它是为了在分代垃圾回收中利用老年代GC 而采用的算法,可以控制老年代GC 中暂停时间的增长。

  10. 列车垃圾回收只在记录集中记录了从后面车厢(列车)到前面车厢(列车)的引用,没有记录从前面车厢到后面车厢的引用。

增量式垃圾回收

  1. 增量式垃圾回收(Incremental GC)是一种通过逐渐推进垃圾回收来控制mutator 最大暂停时间的方法
  2. 增量式垃圾回收是将GC 和mutator 一点点交替运行的手法。执行GC时 mutator 完全停止运行的GC 叫作停止型GC。
  3. 增量式垃圾回收的三色标记算法(Tri-color marking):
    • 白色:还未搜索过的对象
    • 灰色:正在搜索的对象
    • 黑色:搜索完成的对象

    搜索过程如下

    • GC 开始运行前所有的对象都是白色。GC 一开始运行,所有从根能到达的对象都会被标
      记,然后被堆到栈里。GC 只是发现了这样的对象,但还没有搜索完它们,所以这些对象就
      成了灰色对象。
    • 灰色对象会被依次从栈中取出,其子对象也会被涂成灰色。当其所有的子对象都被涂成
      灰色时,对象就会被涂成黑色。
    • 当GC 结束时已经不存在灰色对象了,活动对象全部为黑色,垃圾则为白色。
  4. GC 标记- 清除算法增量式运行:在根查找阶段把能直接从根引用的对象涂成灰色。在标记阶段查找灰色对象,将其子对象也涂成灰色,查找结束后将灰色对象涂成黑色。在清除阶段则查找堆,将白色对象连接到空闲链表,将黑色对象变回白色。
  5. 优点:缩短最大暂停时间。增量式垃圾回收适合那些比起提高吞吐量,更重视缩短最大暂停时间的应用程序。
  6. 缺点:降低了吞吐量。主要是因为存在写入屏障。

RC Immix算法

待完善

实现篇

待完善