[数据结构与算法]常见垃圾回收的算法

1. GC标记-清除

1.1 描述

简单来说，就是在标记阶段对活动对象打上标记，在清除阶段把没有被标记的对象(即非活动对象)进行回收。

• 标记阶段：从根开始递归地对活动对象进行标记。（对循环引用等情况还需要做判断，避免标记方法重复触发）
• 清除阶段：遍历整个堆
  • 已标记：取消标记，准备下一次GC。
  • 未标记：把当前分块放入一个单向链表$free_list首部 。（ 为了下次空间分配时再利用）
    这里在放入链表前会检查区块是否连续，并把连续区块合并后堆入单向链表。
• > 分配阶段：查找单向链表$free_list，从中找到合适大小的区块，相等返回，比当前所需更大则切割后返回。

1.2 优缺点

• 优点：实现简单， 不改变活动对象相对位置，适合搭配保守式GC算法。

• 缺点：

  1. 清除过程块会被细化，导致碎片化结果，给再分配带来巨大压力。
  2. 在分配时需要遍历空闲链表找到合适分块，速度慢。
  3. 与写时复制技术不兼容。 （存在重写对象和设置标志位行为，会导致很多不应该发生的复制）

2. 引用计数法

2.1 描述

? 对对象引用次数进行统计，当引用次数为0时被视为垃圾进行回收。

2.2 优缺点

• 优点：回收效率高 —— 计数0时就回收
• 缺点：
  1. 计数器运算繁重
  2. 占位较多 —— 为保证计数正确性留有32位供计数。
  3. 循环引用无法被回收。

3. GC复制算法

3.1 描述

? 当From空间被占满时，将From空间的活动对象复制到To空间，然后清除From空间，这样一次空间互换，一次GC就结束了。

3.2 优缺点

• 优点：
  1. 快速完成GC —— 只有搜索并复制活动对象的操作。
  2. 高速分配 —— 不涉及空闲链表$free_list操作。
• 缺点
  1. 堆使用效率低 —— 由于堆被二等分，利用率打对折。
  2. 存在递归 —— 复制行为产生的函数，压力较大

4. GC标记-压缩算法

4.1 描述

? 结合标记-清除 和 复制算法，将堆中的所有活动对象整体向左移, 将对象间的空隙消除。

4.2 优缺点

• 优点：除了复制算法的优点外，最明显的就是提升了堆使用率。
• 缺点：计算成本高 —— 三次堆遍历。

5. 分代垃圾回收

5.1 描述

? 它其实是一个回收策略，由于垃圾很难在一次GC中存活下来，所以会对新生对象的GC比老年对象的GC更频繁。回收过程要结合上文具体方法。

5.2 优缺点

• 优点：GC效率提升。
• 缺点：该策略并不适用所有程序。

6. 增量式垃圾回收

6.1 描述

? 它也是一个回收策略，由于GC期间mutator（mutator：垃圾收集器之外的部分，比如当前的应用程序）是停止运行的，GC时间过长对程序执行会很要命。而增量式的方法其实就是把GC分割后和mutator交替执行。（这里的GC可以为任意上文回收方法）

6.2 优缺点

• 优点：缩短mutator暂停时间。
• 缺点：只是缩短最大暂停时间并没有缩短实际GC时间。