GC复制算法是一个非常大胆的GC算法，简单来说，就是把某个内存空间中的活动对象复制到另一个内存空间中，然后把原空间的所有对象都回收掉。

算法过程

首先我们把堆分为两个空间From和To，当From空间完全占满时，GC将活动对象全部复制到To空间，复制完成后互换两个空间。From空间和To空间大小必须一致，保证能把From空间中的所有活动对象都移动到To空间里。

用代码描述这个过程：

1
2
3
4
5
6
7

func gc_copying() {
    free_prt = to_start
    for (r in roots) {
        *r = copy(*r, free_prt)
    }
    swap(free_start, to_start)
}

对象复制

对象复制由copy函数完成，该函数返回一个指针，指向To空间中的已复制对象，同时原对象的头中也会有一个forwarding字段指向新对象：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func copy(obj, free_ptr) {
    if (obj.tag == COPIED) {
        return obj.forwarding
    }
    copy_data(free_ptr, obj, obj.size)
    obj.tag = COPIED
    obj.forwarding = free_ptr
    free_ptr += obj.size

    for (child in children(obj.forwarding)) {
        *child = copy(*child)
    }
    return obj.forwarding
}

其中，copy_data函数执行的是真正的复制操作，将A对象从From空间复制到To空间的A’对象：

复制完毕后，还需要给A对象打上标记并设置forwarding指针指向A’，移动指向To空间的指针：

然后就递归对复制对象A’的子对象进行同样的copy操作，因为copy函数会返回复制之后的对象指针，所以递归调用后会将A’原本指向From空间子对象的指针都改写为指向To空间的子对象，函数结束后由根指向A的指针也会被改写为指向A’：

对所有根引用的对象执行复制算法后，互换From和To空间，就完成了整个GC过程。

对象分配

GC复制算法的分配操作很简单：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func new_obj(size) {
    if (free_ptr + size > from_start + HEAP_SIZE / 2) {
        gc_copying()
        if (free_ptr + size > from_start + HEAP_SIZE / 2) {
            allocation_fail()
        }
    }
    obj = free_ptr
    obj.size = size
    free_ptr += size
    return obj
}

如果From空间足够大，则直接分配对象。存储空间不足，则首先启动gc，然后分配对象，并将free_ptr移动size大小。

优点

GC复制算法实现简单，同时有以下几个优点：

• 吞吐量优秀

  GC复制算法只搜索并复制活动对象，跟GC标记-清除算法相比，能较短时间内完成GC，GC复制算法消耗的时间是和活动对象数量成正比的。

• 不会有碎片化

  每次执行GC复制之后，活动对象都被重新集中起来，压缩到了堆的一端，因此也不会发生碎片化。

• 缓存友好

  在GC复制算法中有引用关系的对象会被安排在堆里离彼此较近的位置，这样CPU就能通过高速缓存来读取位置较近的数据，所以GC复制算法对缓存非常友好。

缺点

GC复制算法缺点也很明显：

• 堆使用效率低

  GC复制算法把堆二等分，通常只能利用其中的一半来存储对象，这是GC复制算法最主要的缺陷。

• 不是保守GC

  GC复制算法必须移动对象重写指针，与保守GC算法不兼容。

改进

迭代复制GC

普通的GC复制算法使用的是递归形式的调用，某个对象复制时，又会递归的复制其子对象，这就带来了额外的消耗，如果引用层次较多，还会有栈溢出的风险。

因为深度优先的方案对缓存友好，所有一般我们引入一个栈，来实现深度优先的迭代算法。

多空间复制

GC复制算法最大的缺点是只能利用半个堆。我们可以再进一步，组合GC复制算法和GC标记-清除算法，把堆分成N等分，拿出其中的两块作为From和To空间来进行GC复制算法，对剩下的N-2块进行GC标记-清除算法。

每次进行多空间复制的GC时，都会切换From和To空间所属的分块，比如第一次是GC使用的是heap[0]和heap[1],那么第二次GC就是heap[1]和heap[2]。

多空间复制算法更有效地利用了堆，不能使用的内存空间只有1/N个堆。