大家好，我是【小松与蘑菇】，即将毕业去深圳的大学生，致力于android，java相关领域，也对AI很感兴趣。正朝着写出通俗易懂而又有深度的文章而努力
前文地址
【GC算法几人知？】一、前置知识积累
【GC算法几人知？】二、标记清除法 全解析
【GC算法几人知？】三、引用计数法，直抵GC本质的方法
【GC算法几人知？】四、GC复制法，java所借鉴的方法
本来想写一篇 jdk8的分代回收的，可惜由于实在太有名，网上的资料汗牛充栋，很多含有动图的就写的不错
所以我决定不再班门弄斧，专心写一些其他同样精彩的算法
目录
- 方法比较
- 压缩算法
- Lisp2算法
- Two-finger算法
- 表格算法
- 总结
方法比较
GC标记-压缩法和标记清除法的区别是什么呢？首先，标记，他们是一样的，区别在于对垃圾的处理方式，
- 标记清除法：遍历堆，没有标记的都清除
- 标记压缩法：将标记对象压缩到一个新地址，原来的对象统统清除
这么看来，这方法和GC复制法其实有点像，GC复制法一开始就划分了From和To，把From的活动对象搬到To，简单粗暴，空间利用率低。但是标记压缩法是通过算法，保证不覆盖对象的情况下，在一个空间中完成对活动对象的重组压缩
关于如何标记，其实和【GC算法几人知？】二、标记清除法 全解析一样，无需赘述，现在我们讨论的是，在已经标记好哪些对象是活动对象(对象头部的mark标记为true)，哪些对象是非活动对象(对象头部的mark标记为false)后，如何将活动对象压缩，并清空非活动对象，就出现了以下三种压缩算法
压缩算法
Lisp2算法
这个方法我相信很多人一下就能自己想到，是这样的
这是标记后的堆，其中B,C,D,F为活动对象
直接将他们挪到最左端
就完成了……就是如此简单！！
有几个问题：
- 如何保证C向左移动的时候不会覆盖到B
- 如何保证根依然指向B和D，而不是原来的老位置
对于第一个问题，我们要设置一个scan点，就是空闲地址的首部，当没有挪动的时候，scan在空间首部，当挪动B的时候，scan向右移动B的size距离，这样就知道下次挪动C的时候该往哪里动了
第二个问题，是在每个对象中设置forwarding指针，和GC复制法一样，保留的是移动后的新地址，就像你搬家后，为了让来找你的人知道你的新地址，就需要在老家把新地址写上一样
但是，在挪动对象后在设置forwarding几乎不可能了，只能在挪动前统一调配
所以Lisp2方法分为3步
- 设置
forwarding指针，遍历堆，查找到每个活动对象即将挪动的新地址，将他们记录在这个指针中
那C的新地址怎么知道呢？
就是通过scan扫描，scan从首地址开始，如果发现活动对象，也即是mak==True，此时的scan代表这个对象，scan的forwarding设置为他的新地址，然后移动scan.size大小，为后面的对象腾空间
set_forwarding_ptr(){
scan = new_address = $heap_start
while(scan < $heap_end)
if(scan.mark == TRUE)
scan.forwarding = new_address
new_address += scan.size
scan += scan.size
}
- 更新指针
再次遍历堆，如果发现对象A指向对象B，将对象A指向对象B中的forwarding指针记录的地址 - 移动对象
第三次遍历堆，将所有活动对象移动到forwarding记录的地址处，一定是从左到右，mark通通设置为false
算法思想很简单，主要是维护对象间的引用关系需要一些操作。但是这一算法有一个最大问题，就是遍历了三次堆
Two-finger算法
我相信，写过【三数之和】算法题的孩子，一定对【双指针】这一算法有所印象，是的，这个方法在快速排序中也起到了至关重要的作用，那就是——减少遍历次数，在这里也是同样的套路
不过，可别急着引用，对象并不是int型，所以要想在垃圾回收中应用双指针，前提是所有对象整理成大小一致
步骤是两步：
- 移动对象
如图，左边指针专找非活动对象，右边指针专找活动对象，当$free遇到非活动对象，就停下，live遇到活动对象就停下
当两个指针同时停下时，就交换二者（这也是为什么要大小一样的原因）
- 更新指针
和Lisp2一样，原来的引用关系怎么办呢？比如根本来指向F，现在F到了A的位置成了F’，那么根如何指向F的新地址呢？
下面是双指针执行完毕的情况，就是$free>live的时候，这个时候我们发现，左边的对象其实不用管，因为被交换出去的都是非活动对象，而原来的活动对象B,C没有变化，所以我们要更新引用关系的是E,F
我们只需要判断，如果一个一个对象（比如根）指向了$free的右边位置，证明这一位置一定被交换到了左边，这一位置的forwarding指针同时记录了新地址，那么根只需要按照这个新地址指向就可以了
伪代码如下
adjust_ptr(){
# 针对根引用的更新
for(r : $roots)
if(*r >= $$free)
*r = (*r).forwarding
scan = $heap_start
# 针对对象相互引用的递归更新
while(scan < $free)
scan.mark = FALSE
for(child : children(scan))
if(*child >= $free)
*child = (*child).forwarding
scan += OBJ_SIZE
}
使用Tow-Finger法，只需要两遍遍历
这一方法的其实已经很完美了，唯一的缺点就是需要对象大小一致，我们可以通过GC标记清除法
中的bibop方法解决这一问题
表格算法
这个思想简单，但是叙述起来非常复杂，这里我跳过一些细节，直接描述总体思想
首先，这个方法和Lisp2有点像，都是直接往左边压缩，区别在于，Lisp2是以对象为单位左移，而这里是以对象群的方式，就是连续的活动对象
如上图，在Lisp2方法中，压缩的对象是B,C,F,G
而在这里，压缩的对象是 BC,FG
然后如何保留对象间的互相引用和根的引用呢? 前两个方法都是用forwarding指针，也就是在老家写新地址，那条路多少号。在这里，是用的表格，也就是在老家写怎么去，比如我家在城西往北一公里
使用表格表示，表格有两个格子，第一个格子表示原来的位置，第二个格子表示向左移动的位置
这里使用三个指针,$free,live,scan，都从左往右遍历，他们的区别是
$free遇到非活动对象停下live遇到活动对象停下scan遇到活动对象群的尾部停下
这样live-$free就是向左移动的size
scan-live就是对象群的大小
这样子，只要遍历列表到间隙表格，比如遍历到了550:300这一表格，就知道让所有指向550的指针，也就是指向F的指针，往左挪动300指向250即可。那指向G的呢？同样向左移动300，这也是为什么要绑定对象群的原因，因为他们是平移的
有一个问题是，你会发现间隙表格100:100的在b中和c中的位置不一样，这是肯定的，遍历完BC后，就在BC后方建立来了一个表，而遇到FG后，如果FG左移，一定会覆盖掉表的，所以还要把表挪到FG后方，这其实比较麻烦
表格算法也是只需要两次遍历，一次移动对象建表，一次按表更新指针，但是表格移动频繁，维护表格代价很高，尤其是移动对象群很多时，表格将会很长
总结
实际上还有一种方法叫做ImmixGC，上面的算法都是上个世纪的产物，这个算法是08年才出的，高深莫测，我也只能浅尝辄止弄懂思路即可，以我对这个的了解，还无法将他表达出来。这个算法要是在面试官问你GC的时候说，那可真吊打他了哈哈哈哈，可以去查查资料
上面的三种算法，本质上都是压缩算法，做了两件事情，
- 移动对象：通过平移，交换
- 保留原来的引用关系：通过
forwarding指针，表格等
其实在接触GC多了之后，发现方法就那么几个，而这些方法的思想，在算法中也有大量运用，多多学习，触类旁通吧
作者简介 ：【小松与蘑菇】，微信公众号同名，喜欢读书和收集书，GC系列文章主要参考自《垃圾回收的算法与实现》，如有需要，可回复【垃圾回收的算法与实现】领取哦
