本文章是学习《垃圾回收的算法与实现》的笔记。

箭头的样式

本书中：mutator 的实体是“应用程序”，其用于改变 GC 对象之间的引用关系，其实际进行的操作有两种：生成对象、更新指针。

一、GC 评价指标

吞吐量、最大暂停时间、堆使用效率、访问的局部性

访问的局部性

二、垃圾回收算法分类

保守式GC（Conservative GC）

1. 定义：不能识别指针和非指针的 GC。
2. 由于 GC 应该只是对指针操作，不需要操作非指针，因此会检查不明确的根，以“某种程度”的精度来识别指针，比如：
   • 是不是被正确对齐的值？（利用CPU对齐来检查：32位CPU的情况下，指针必定为 4 的倍数；64位CPU，指针必定为 8 的倍数）
   • 是不是指向堆内？（当分配了 GC 专用的堆时，对象会被分配在堆中）
   • 是不是指向对象的开头？（比如利用 “BiBOP” 法时，把对象（在块中）按照固定的大小对齐，核对检查对象的值是否为固定大小的倍数）
3. 总会有被误识别为指针的非指针（false pointer）：貌似指针的非指针。这种情况称为“指针的错误识别”。可以在数据结构定义时，加上指针非指针的标记，只要程序员没有放入类型不同含义的值（比如把指针转换类型放入int的域），就有可能正确识别指针。
4. 优点：语言处理程序和GC解耦，实现简单。缺点：识别指针和非指针需要付出成本；错误识别指针会压迫堆；能够使用的 GC 算法有限（涉及到如 GC 复制算法等需要移动对象的GC算法时，可能重写非指针的值）。
5. 间接引用。通过句柄（handle）来间接引用和操作对象。根对于对象的引用经由句柄进行操作，而对象和对象之间的引用则不需要通过句柄。优点在改写指针时，改掉的是句柄中的值，而不是根中的值，因此有可能实现 GC 复制算法和 GC 标记-压缩算法等。缺点：拉低了访问对象内数据的速度。

准确式GC（Exact GC）

1. 定义：能正确识别指针和非指针的GC。
2. 正确的根（exact roots）：精准识别指针和非指针的“正确的根”来执行GC。创建正确的根的方法很多，有个共通点：依赖于“语言处理程序”实现。
3. 正确识别指针和非指针的方法：
   • 打标签（tag）；比如 32 为CPU下，指针的值肯定是 4 的倍数，即低 2 位为 00。如果非指针的低 2 位均不为 00，则可以进行识别。因此在存储非指针值时，将非指针（int等）先向左移动 1 位（a<<1），然后低 1 位置 1（a|1）。需要注意溢出问题（转换为更大的数据类型），操作非指针类型的时候需要先去除标签，处理完再添加标签。
   • 不把寄存器和栈等当做根。在处理程序里面创建一个根，这个根集合了 mutator 可能到达的指针，以此为基础进行 GC 操作。如 Rubinius 语言处理程序。
4. 优点：可以适配需要移动对象的 GC 算法。不会错误识别指针，GC后堆中只会留下活动对象。缺点：创建语言处理程序时需要顾及 GC，实现麻烦，可能还会影响语言处理程序整体的执行速度。

三、垃圾回收算法总览

适用于保守式GC（Conservative GC）

1. GC 标记-清除算法（Mark Sweep GC）：位图标记法（适配写时复制技术）、延迟清除法。
2. 引用计数法（Reference Counting）：延迟引用计数法、Sticky 引用计数法、1 位引用计数法、部分标记-清除算法。
3. MostlyCopyingGC（保守式GC对于Copying GC 的实现）。
4. 黑名单：改善保守式GC因错误识别指针而压迫堆。
5. 增量式垃圾回收（Incremental GC）：三色标记算法、Steele 的算法、汤浅的算法。

适用于准确式GC（Exact GC）（注：适用于保守式GC的算法也适用于准确式GC）

1. GC 复制算法（Copying GC）：Cheny 的GC复制算法、近似深度优先搜索方法、多空间复制算法。
2. GC 标记-压缩算法（Mark Compact GC）：Lisp2 算法、Two-Finger 算法、表格压缩法、ImmixGC 算法。
3. 分代垃圾回收算法（Generational GC）：多代垃圾回收、列车垃圾回收。
4. RC Immix算法（Reference counting Immix）：合并型引用计数器法、合并型引用计数器法与 Immix 的融合。

四、垃圾回收算法详解

GC 标记-清除算法（Mark Sweep GC）

1. McCarthy - 1960；R. John M. Hughes - 1982
2. GC 从根开始。根：调用栈、寄存器以及全局变量空间都是根。整个GC过程分为标记阶段(mark_phase)和清除阶段(sweep_phase)，还涉及到分配操作(new_obj)和合并操作(coalescing，在清除阶段进行)。
3. 从根开始，能够被索引到的对象为活动对象，否则为非活动对象。GC 通过标记对象是否为活动对象，从而将非活动对象的空间放回到空闲分块链表中进行回收，作为之后的堆内存分配的预制资源。
4. 经常采用深度优先搜索：1. 存在访问局部性，将更近的索引的对象尽量放置在更近的内存分块上，从而增加缓存命中率，减少内存读取次数；2. 在循环访问结点时，需要按照队列存储节点，深度优先搜索的内存使用量相较而言更少。
5. 分配时经常采取 First-fit 分配策略。（还有 Best-fit 和 Worst-fit ）
6. 分配需要遍历空闲链表（free-list），分配速度相较 GC 复制算法和 GC 标记-压缩算法慢。后两个算法的分块是作为一个连续的内存空间存在的，没必要遍历空闲链表，还能在堆允许范围内分配很大的对象。（提升分配速度的算法：1. 多个空闲链表（multiple free-list）；2. BiBOP 法（Big Bag Of Pages））
7. 与写时复制技术（copy ）不兼容，故可采用位图标记法（bitmap marking）分离标记和对象。
   注：在多个堆的情况下，一般每个堆对应一个位图表格（因为位图每个对象的标志位是根据其地址求得的，要求连续的堆地址）
8. 延迟清除法（laze sweep）。在给对象分配内存的时候来进行清除，如果得到分块则直接返回，如果得不到，再重新进行标记清除。

引用计数法（Reference Counting）

1. George E. Collins - 1960；L. Peter Deutsch, Daniel G. Bobrow - 1976；Douglas W. Clark, C. Cordell Green - 1977；W. R. Stoye, T. J. W. Clarke, A. C. Norman - 1984
2. 通过“计数器”来维护对象被引用的次数。内存管理和 mutator 同时运行是引用计数法的一大特征：在 mutator 执行过程中没有明确启动 GC 的语句，该方法在 mutator 的处理过程中通过增减计数器的值来进行内存管理。在更新指针的时候，对计数器进行更新（先增再减，回避引用前后的对象相同的bug）；如果引用数降为 0，则该对象的 children 引用均递减，然后 reclaim(obj) 对该对象进行回收（连接到空闲链表 free-list）。
3. 优点：即刻回收垃圾；最大暂停时间短；不需要沿指针查找。缺点：计数器的值增减处理繁重；计数器域占用很多位；实现繁琐复杂；循环引用无法回收。
4. 延迟引用计数法（Deffered Reference Counting）。利用 ZCT(Zero Count Table) 对引用为 0 的对象进行管理。在对象引用递减 dec_ref_cnt 函数中，如果 ZCT 满了就执行 scan_zct 回收垃圾对象；在分配新对象 new_obj 函数中，如果分配第一次失败，则执行 scan_zct 回收垃圾对象，然后二次分配。scan_zct 只需要访问根节点所连接的对象。缺点：延长了最大暂停时间：zct 大小和最大暂停时间正相关，和 scan_zct 调用频率负相关（和吞吐量负相关）。
   
   scan_zct 函数
5. Sticky 引用计数法。降低计数器的位数，计数器值有可能溢出，溢出后不再对计数器进行增减，也不会回收该对象。处理方式：1. 鸵鸟策略，不做处理（依据：a. 溢出情况很少；b. 如果溢出，说明引用量曾经很大，侧面说明对象很重要）；2. 使用 GC 标记-清除算法进行管理（利用计数器作为标记域，回收计数器为 0 的对象，解决了回收计数器溢出的垃圾和循环引用的垃圾；整个过程会对活动对象扫描多次，延长了最大暂停时间，降低了吞吐量）。
6. 1 位引用计数法。Sticky 引用计数法的极端例子。0 表示引用数为 1，1 表示引用数大于等于 2。指针通常默认为 4 字节对齐，没办法利用低 2 位，可以让指针持有计数器，计数器被称为 标签 tag，两种状态称为 UNIQUE 和 MULTIPLE。优点：1. 节省空间；2. 不容易出现高速缓存缺失（不需要操作对象）。缺点：1. 需要处理溢出
   
   1 位引用计数法的状态转移图
7. 部分标记-清除算法（Partial Mark&Sweep）。只对“可能有循环引用的对象群”使用GC标记-清除算法，对其他对象进行内存管理时使用引用计数法。区别于之前的GC标记-清除算法，之前的算法执行目的是查找活动对象，而执行部分标记-清除算法的目的是查找非活动对象。缺点：由于搜索队列、三次操作对象，大大增加了内存管理花费的时间，增大了最大暂停时间。
   7.1 需要往对象头中分配 2 位空间，用 00~11 管理颜色：BLACK（肯定不是垃圾，对象初始化的颜色）、WHITE（肯定是垃圾）、GRAY（搜索完毕的对象）、HATCH（可能是循环垃圾的对象）；
   • 在 dec_ref_cnt 将不是 HATCH 颜色的对象改为 HATCH，并放入队列 hatch_queue。在 new_obj 分配失败后，如果队列不为空，则执行 scan_hatch_queue。
   • paint_gray 函数：自身涂为灰色，孩子的引用数减量，并对孩子递归执行 paint_gray。特征：每次执行中要涂色的对象和要进行计数器减量的对象不是同一对象；
   • scan_gray 函数：搜索所有的灰色对象，将计数器为 0 的涂为白色，否则涂为黑色（自身涂为黑色，孩子的引用数增量，恢复引用关系）；
   • collect_white 函数：如果对象是白色，则涂黑，然后递归对孩子调用 collect_white，然后回收该对象。

scan_hatch_queue

GC 复制算法（Copying GC）

1. Marvin L. Minsky - 1963；Fenichel, Yochelson - 1969；C. J. Cheney - 1970；Paul R. Wilson, Michael S. Lam, Thomas G. Moher - 1991
2. 简单说就是把某个空间中的活动对象复制到其他空间，然后回收原空间的所有对象。原空间称为 From 空间，复制目的空间称为 To 空间。当 From 空间占满时，将活动对象全部复制到 To 空间，然后将 From 空间和 To 空间互换。采用深度优先搜索进行复制。
3. 优点：吞吐量优秀（只搜索并复制活动对象）；可以实现高速分配（每次GC完成后，分块是连续的内存空间，不需要搜索空闲链表）；不会发生碎片化；与缓存兼容（具有引用关系的对象会被放在堆中较进的位置）。缺点：堆使用效率低下（只能利用一半，搭配使用GC 复制算法和GC 标记- 清除算法可以改善）；不兼容保守式GC算法（需要移动对象重写指针）；递归调用函数（迭代比递归要更高效）
   3.1 GC中，压缩的概念：把对象重新集中，分配到堆的一端的行为。
4. Cheney 的 GC 复制算法。改良为通过迭代进行复制。先复制根节点直接指向的对象，然后挨个复制子对象，采用的是广度优先搜索。利用 scan 和 free 指针将堆复用为队列，而不需要特意留出多余的内存空间。缺点：不一定能够兼容高速缓存（广度优先搜索，使得具有引用关系的对象不一定在相邻空间）
5. 近似深度优先搜索方法。改良 Cheney 的 GC 复制算法。对块进行分页，利用页面广度优先搜索，页内深度优先搜索的方式进行近似深度优先搜索。（引入四个变量：1. $page 页面数组，元素存的是页面开头地址；2. $local_scan 页内搜索数组，元素存的是当前页内下次搜索的位置指针；3. $major_scan 页面搜索指针，指向搜索尚未完成的页面开头的指针；4. $free 指向分块开头指针，随着分配进行不断后移）
6. 多空间复制算法。堆分成 N 份，其中的两块空间执行 GC 复制算法，其余的 N-2 块空间执行 GC 标记-清除算法。每次复制完成后，To 空间为原来的 From 空间，From 空间为下一个分块，循环进行。兼顾两种组合算法的优点同时具备其缺点，但是弱化了缺点。

multi_space_copying 函数

GC 标记-压缩算法（Mark Compact GC）

1. Donald E. Knuth - 1973；Robert A. Saunders - 1974；B. K. Haddon, W. M. Waite - 1967；Stephen M. Blackburn, Kathryn S. McKinley - 2008
2. GC 标记-压缩算法是将 GC 标记-清除算法和 GC 复制算法相结合的产物。分为标记阶段和压缩阶段。标记阶段同之前讲的 GC 标记-清除算法的标记阶段。下面的 3 4 两个算法都是压缩阶段的算法。
3. Lisp2 算法。步骤：1. 设定 forwarding 指针；2. 更新指针；3. 移动对象。每一个步骤需要扫描一次堆，总共需要扫描三次。优点：有效利用堆。缺点：压缩花费计算成本，需要搜索三次堆。
   • 设定 forwarding 指针：扫描堆，重新分配各个对象应该位于的新位置，但是不执行复制。为了在移动对象前更新指针，不能直接在结构体头部域中设定 forwarding 指针，这样会导致 mutator 所使用的数据会被覆盖掉。因此这个算法需要确保专门的 forwarding 域。
   • 更新指针：更新根指针和所有活动对象的孩子指针为新的位置。
   • 移动对象：依次复制对象，堆中的对象前后顺序不变，因此不会出现对象被覆盖的现象。
4. Two-Finger 算法。改良为只需要搜索两次堆。类似快排的思想，左右两个指针 $free 和 $scan，前者从左往右搜索非活动对象，后者从右往左搜索活动对象，然后复制右面的活动对象至左侧，同时将右面移动前的活动对象的 fowarding 域更新为新地址。完成后，调用 adjust_ptr 函数进行指针更新操作即可。优点：两次扫描即可完成。缺点：要求必须将所有的对象整理成大小一致。
5. 表格压缩法。同 Two-Finger 一样只需要两次搜索。由于表格入口至少两个字，因此要求对象至少为两个字。在移动对象阶段同步构建表格并移动表格，然后在更新指针阶段需要搜索表格。优点：存储表格不需要多于的空间，可以利用非活动对象的空间来存储表格，相应的表格需要在移动对象的同时被移动。缺点：表格入口不是有序的，因此需要遍历搜索表格，如果对表格进行排序，依然不治本。
6. ImmixGC 算法。该方法将堆分为一定大小的块（block），然后将块分为线（line），按照线为单位回收垃圾。块最合适的大小为32K，线最合适的大小为128字节，每个块含256个线。该算法只处理小型对象（对象大小小于线大小）和中型对象（对象大小小于8K），大型对象（对象大小大于8K）由 Jikes 的 MMTk 管理。
   • 域定义（每个block）：
     1. line：线，一个 block 分为若干的 line；
     2. mark_table：每个 line 相对应的标记的位串，值为：FREE（没有对象），MARKED（标记完成），ALLOCATED（有对象），CONSERVATIVE（保守标记，表示小型对象占据了 line[i+1]，mark_table[i+1]可能会包含所分配对象的后半部分，即对象跨line）；
     3. status：表示每个块中的使用情况，值为：FREE（所有线为空），RECYCLABLE（一部分线为空），UNAVAILABLE（没有空的线）；
     4. hole_cnt：记录各个块的孔数（孔：拥有连续的大于等于 1 个空的线）。用来表示碎片化严重程度的指标；
   • 以 GC 标记-清除算法为基础，但是不使用空闲链表，而是使用 $cursor $limit 两个指针，分别指向 RECYCLABLE 块的孔的开头和末尾，由 $cursor 滑动着分配。在分配时，也会相应地设置 block.mark_table 进行标记工作。
   • GC 发生的条件：1. 存在1个或1个以上没有进行分配的 RECYCLABLE 块；2. 在上次 GC 时能够回收的线，其总大小减少了一定的量。GC 过程为：1. 选定备用的 From 块（表示需要进行复制对象操作的块，优先操作碎片化严重的块）；2. 搜索阶段（非From块进行标记工作，From块进行复制工作，如果复制所需的 FREE 线不够了，则放弃复制转而进行标记）；3. 清除阶段（FREE->FREE；MARKED->ALLOCATED；CONSERVATIVE->CONSERVATIVE且前面一个块设置为ALLOCATED）。
   • 优点：可以防止碎片化而进行压缩。缺点：对象不是按照顺序的，因此无法利用缓存的局部性原理；保守标记下，没有活动对象的线有可能无法被回收，因此虽然对吞吐量足够重视，但是无法有效利用堆

MostlyCopyingGC

1. Joel F. Bartlett - 1988；
2. 简单说就是"把那些跟不明确的根指向的对象在同一页的对象都复制的GC算法"。前提条件：1. 根是不明确的根；2. 没有不明确的数据结构；3. 对象大小随意；4. CPU 是 32 位（也可适用于其他位数，本书为了简单理解，只讲 32 位下的情况）。
3. 堆被分为一定大小的页（page）。每个页都有编号，页编号的位数选取前提：所有页编号均唯一，也不会数据溢出。引入 $current_space $next_space 来表示 From 页和 To 页的编号。正在使用的页的标志：OBJECT | CONTINUED（正在使用的页 | 当正在使用的页跨页时，设置在第 2 个页之后）。一般分配对象后，当前页应该为 OBJECT，当 mutator 需要分配大对象时，对象跨多个页，在第 2 个页之后设置 CONTINUED 标志。
4. 特点：不会回收包含有从根指向的对象的页里的垃圾对象，而且也不会回收这个垃圾对象所引用的对象群。如果所有页中均含根指向的对象，那么所有的垃圾都无法被回收。可以通过调整页大小来改善，实验结果表明合适的页大小在 512 字节。CONTINUED 页中的对象不会被复制，因此不能在创建对象的时候将其分配到 CONTINUED 页中。
5. 优点：在保守式GC里面使用的 GC 复制算法，能够直接继承 GC 复制算法的优点。缺点：因为会复制部分垃圾对象（这些对象和根引用的对象位于同一页），拉低了内存使用率。

黑名单

分代垃圾回收

增量式垃圾回收

RC Immix算法（Reference counting Immix）