4 GC复制算法

  Copying GC是Marvin L.Minsky在1963年研究出来的算法。就是指把某个空间里的活动对象复制到其它空间，把原空间里的所有对象都回收掉。在此，将复制活动对象的原空间称为From空间，将粘贴活动对象的新空间称为To空间。

4.1 什么是GC复制算法

  GC复制算法是利用From空间进行分配的。当From空间被完全占满时，GC会将活动对象全部复制到To空间。当复制完成后，该算法会把From空间和To空间互换，GC也就结束了。From空间和To空间大小必须一致。这是为了保证能把From空间中的所有活动对象都收纳到

4.1.1 执行过程

假设目前堆里的配置如下。   

执行GC。首先是从根直接引用的对象B和G，B先被复制到了To空间。

将B被复制后生成的对象称为B’。在From空间中B已经被打上了复制完成标签。但是，这里只把B’复制了过来，它的子对象A还在From空间里，下面把A复制到To空间里。

  

这次才是真正意义上复制了B。因为A没有子对象，所以对A的复制就完成了。

接下来，要和复制B一样从根引用复制G，以及其子对象E。虽然B也是G的子对象，不过因为已经复制完B了，所以只要把从G执行B的指针转换到B’上。

最后，只要把From空间和To空间互换，GC就结束了。

对象C、D、F因为没法从根查找，所以会被回收。这里程序是以B、A、G、E的顺序搜索对象的，使用的是深度优先搜索。

4.2 优点

4.2.1 优秀的吞吐量

GC标记-清除算法消耗的吞吐量是搜索活动对象（标记阶段）所花费的时间和搜索整体堆（清除阶段）所花费的时间之和。

另一方面，因为GC复制算法只搜索并复制活动对象，所以跟一般的GC标记-清除算法相比，它能在短时间内完成GC，也就是说其吞吐量优秀。

尤其是堆越大，差距越明显。GC标记-清除算法在清除阶段所花费的时间会不断增加，但GC复制算法就不会。因为它消耗的时间是与活动对象的数量成比例的。

4.2.2 可实现高速分配

GC复制算法不使用空闲链表，因为分块是一块连续的内存空间。因此，调查这个分块的大小，只要这个分块大小不小于所申请的大小，那么移动指针就可以进行分配了。

比起GC标记-清除算法和引用计数算法等使用空闲链表的分配，GC复制算法明显快得多。使用空闲链表是为了找到满足要求的分块，需要遍历空闲链表，最坏的情况是我们不得不从空闲链表中取出最后一个分块，这样就用了大量时间把所有分块都调查一遍。

4.2.3 不会发生碎片化

基于算法性质，活动对象被集中安排在From空间的开头。像这样把对象重新集中，放在堆中一端的行为叫作压缩。在GC复制算法中，每次运行GC时都会执行压缩。

因此GC算法有个非常优秀的特点，就是不会发生碎片化，也就是说可以安排分块允许范围内大小的对象。

另一方面，在GC标记-清除算法等GC算法中，一旦安排了对象，原则上就不能再移动它了，所以会多多少少产生碎片化。

4.2.4 与缓存兼容

在GC复制算法中有引用关系的对象会被安排在堆里离彼此较近的位置。B’引用A’，G’引用E’的顺序排列。这种情况有一个优点，那就是mutator执行速度极快。很多CPU都通过缓存来来高速读取位置较近的对象。这也是借助压缩来完成的，通过压缩来把有引用关系的对象安排在堆中较近的位置。

4.3 缺点

4.3.1 堆使用率低下

GC复制算法把堆分成二等分，通常只能利用其中一半来安排对象。也就是说只有一半堆能被使用，相比其他能使用整个堆的GC算法而言，这是GC复制算法的一个重大缺陷。

4.3.2 不兼容保守式GC算法

GC标记-清除算法有着跟保守式GC算法相兼容的优点。因为GC标记-清除算法不用移动对象。

另一方面，GC复制算法必须移动对象重写指针，所以有着跟保守式GC算法不相容的性质。虽然有限制条件，GC复制算法和保守式GC算法可以进行组合。