【GC算法几人知？】四、GC复制法，java所借鉴的方法java小松与蘑菇-

大家好，我是【小松与蘑菇】，即将毕业去深圳的大学生，致力于android,java相关领域，也对AI很感兴趣。正朝着写出通俗易懂而又有深度的文章而努力

前文地址

【GC算法几人知？】一、前置知识积累
【GC算法几人知？】二、标记清除法 全解析
【GC算法几人知？】三、引用计数法，直抵GC本质的方法

今天来介绍GC复制算法，两个英语单词 From & To
如果你对这两个词在GC中的角色有印象的话，相信你一定了解过java的GC，因为在jdk中，也是划分了from空间和to空间，然后将里面的对象搬来搬去，这些都源自于Marvin L. Minsky在1963 年研究出来的GC复制算法，现在，让我们来深入了解一下吧

概念

所谓GC复制算法，就是将堆空间分成From和To空间，一边一半，所有新的对象都放在From空间，当From空间满的时候，就将非垃圾的对象搬移到To空间中，然后清空From空间，同时互换From和To的名字，这样又可以继续在From空间中进行新建对象了

思想很简单，但是以上方法有两个需要解决的问题

1. 如何判定哪些是非垃圾对象，并找到

2. 找到这些对象后如何复制他们到To空间

现在就让我们来一个一个解决吧

复制原理

就是一个copy()的事，看伪代码

copying(){  $free=$to_start  for( r: $roots) *r =copy(*r) swap($from_start,$to_start) } 

可以看到，第一行表示标记To空间的首地址为free，然后通过根引用，找到所有被引用到的对象，他们就是非垃圾对象，通过copy()函数将他们复制到To中，最后交换From和To，在看copy()函数之前，我们先看看对象obj的构造

头里面含有两个信息:

• 一个叫做tag，表示是否被复制过，避免重复复制，
• 另一个是forwarding，记录复制后的新地址，为什么要这样呢？是因为可能有别的对象指向这个对象，当这个对象复制到新地址后别的对象却不能同步知道他到哪了

比如说你搬家了，但是那些向你要债的人不知道你搬了，所以你可以在老家留下“我搬去火星”的字条，这样，那些要债的上门后看到字条，就知道要去火星找你了

现在来看看copy()函数是如何复制的

copy(obj){ if (obj.tag!=COPIED) copy_data($free,obj,obj.size)   obj.tag=COPIED   obj.forwarding=$free   $free+=obj.size   for(child:children(obj.forwarding)) *child=copy(*child) return obj.forwarding } 

可以看到，首先判定如果对象obj没有复制过，那么copy_data()将真正的将其复制到新空间，就是把从obj首地址到其size的部分移动到$free处，当然此时$free需要向后移动obj的zie位置，为新的obj复制做准备
如图A’就是复制后的对象

然后forwarding记录$free地址，也就是移动后的新地址的首地址，

看到这我想你已经发现了，copy()代码最后的for循环想必就是解决A所指向的C,D的复制的吧
没错，copying()中已经确保了A是活动对象，那么A的子对象C,D就一定是活动对象了，那么，就递归的调用copy()函数即可，这样，A’,C’,D‘在To空间中还能保证是连续的哦

copying()函数执行完毕

我们只需要堆每一个根在From中指向的对象都进行上述操作，就可以将所有对象和他们的关系都移动到To中，最后回收From空间，再交换To和From即可，所谓的交换，当然不是将双方的内容交换（那岂不是要再复制一遍？？），是将From和To的标志互换即可

优点

到了商业互吹时间，从上面的步骤，我们可以看到他有如下优点

1. 吞吐量高
   所谓吞吐量就是搜索活动对象的时间比上搜索堆时间，越高说明你的有效搜索占比越高，不难看出，我们都是从根开始，搜索的全部是活动对象，并没有浪费时间去搜索垃圾对象。这个优势在堆越大的场景下越明显

2. 分配速度快
   就是我们新建一个对象时，mutator需要申请多久才能完成，比如标记清除法时维护了一个空闲链表，使得找到一个合适的分块需要遍历链表，很花时间。但是在这里，我们都是从From空间中的$free处直接开辟的，标记清除法类似在停车场停车，需要一排一排看有没有合适的车位；而这里就像在大马路上停车，只要从最后一辆那里停就行

3. 没有碎片
   在将活动对象复制到To空间时，他们都是紧挨着的，然后清空From时全部清空，完全没有碎片的可能

4. 兼容缓存（局部性好）
   在To空间中，父对象和子对象也是挨着的，参考上面的A’,C’,D’，所以利于缓存，局部性好

缺点

有一说一，这个算法的1，2，3优点已经注定了他时可以应用甚至是商用了，尽管他有以下缺点

1. 堆利用效率低
   这是最明显的，空间都被劈成两半了，一次永远只能用一半就得搬家
2. 递归调用
   在对子对象进行复制时，使用了递归方法，可能导致栈溢出

总结

然而，这种缺点稍稍思考就可以解决，From和To为什么非要1:1呢？可以是一个合适的比值吧
既然递归会栈溢出，那么为什么不可以迭代呢？

没错，这个方法将这两个缺点改正后再融合分代垃圾回收，将成为jdk8的垃圾回收方法，也是面试最常考点之一 ，将在下文详细解析