复制收集算法

原理：将从根开始被引用的对象复制到另外的空间，然后将复制的对象所能够引用的对象用递归的方式不断复制下去。

复制完成之后，“死亡”对象就被留在了旧空间中。图中（4）部分中，将旧空间废弃掉，就可以将死亡对象所占用的空间一口气全部释放出来，而没有必要再次扫描每个对象。下次GC的时候，现在的新空间也就变成了将来的旧空间。

递归复制算法

Robert R. Fenichel 和 Jerome C. Yochelson 给出的GC复制算法的实现采用递归的形式，遍历每个 GC Root，并递归复制其子对象。

copying() {
    $free = $to_start
    // 遍历每个GC Root
    for (r: $roots) {
        // 将root指向GC后的新地址
        *r = copy(*r)
    }
    // 交换From和To空间
    swap($from_start, $to_start)
}

copy(obj) {
    if (obj.tag != COPIED) {
        // 这里虽然将obj拷贝到了To空间，但是obj中包含的指针还指向From空间
        copy_data($free, obj, obj.size)
        obj.tag = COPIED
        // forwarding指针指向该对象在To空间的新地址，之后遇到指向From空间的该对象时要将指针更新为forwarding指针
        obj.forwarding = $free
        $free += obj.size

        // 递归复制子对象
        for (child: children(obj.forwarding)) {
            *child = copy(*child)
        }
    }
    return obj.forwarding
}

优点：

• 优秀的吞吐量 - GC 复制算法只搜索并复制活动对象，因此能在较短时间内完成 GC，吞吐量优秀。它消耗的时间与活动对象的数量成正比，而不受堆大小的影响。
• 可实现高速分配 - GC 复制算法不使用空闲链表，分块在一个连续的内存空间，因此在进行分配时只需比较整个空闲分块的大小是否足够就可以了，而不需要链表遍历操作。
• 不会发生碎片化 - 每次进行复制时都会将活动对象重新集中（压缩），避免了碎片化。
• 与缓存兼容 - 在上述递归实现的复制算法中，有引用关系的对象会被安排在堆中离彼此较近的位置，有利于提高高速缓存命中率。（局部性好

缺点

• 堆利用率低 - GC 复制算法将堆空间一分为二，每次只能利用一般用于分配。这一缺点可以通过搭配使用复制算法和标记-清除算法得到改善。
• 递归调用函数 - 每次递归调用都会消耗栈空间，由此带来了不少额外负担，而且还有栈溢出的可能。

Cheney迭代法

copying() {
    // scan是用于搜索复制完成的对象的指针，$free是指向To空间分块开头的指针
    scan = $free = $to_start
    // 首先复制所有的roots
    for (r: $root) {
        *r = copy(*r)
    }

    // 然后从已经复制到To空间的对象开始复制它们引用的子对象
    while (scan != $free) {
        for (child: children(scan)) {
            *child = copy(*child)
        }
        // 向前移动scan指针，指向下一个已经复制到To空间的对象
        scan += scan.size
    }

    // 交换From和To空间
    swap($from_start, $to_start)
}

copy(obj) {
    // 检查obj.forwarding指针是否指向To空间，如果是，说明该对象已经被复制过，直接返回其forwarding指针
    // 否则进行复制
    if (is_not_pointer_to_heap(obj.forwarding, $to_start)) {
        copy_data($free, obj, obj.size)
        obj.forwarding = $free
        $free += obj.size
    }
    return obj.forwarding
}

实质为广度优先，Scan每前进一次，Free可前进零或N次，取决于是否有引用子对象。

优点：

• 迭代算法，消除了递归调用函数的额外负担和栈的消耗。
• 直接将堆空间用作队列，省去了额外内存空间开销。

缺点：

无法将有引用关系的对象复制到相邻位置，使得局部性大大降低。