GC算法-复制算法

概述

复制算法就是将内存空间二等分, 每次只使用其中一块. 当执行GC时, 将A部分的所有活动对象集体移到B中, 就可以将A全部释放.

画个图就是:

在执行GC前, 内存长这样:

当执行GC后, 内存就变成这样了:

还记得标记清除算法的问题是什么吗? 内存碎片化严重. 现在好了, 碎片化问题解决了, 每次GC执行后, 内存空间都是连续的啦.

实现

想一想GC执行的步骤是什么? 很简单啊, 遍历所有可访问的对象, 将所有对象的复制到另一块内存中. 完毕.

遍历所有根集合的对象, 跳过. 将每个对象都调用一次copy函数, 那么, 这个copy函数如何实现呢?

function copy(obj){
    // 若对象已经被复制过了, 则将其直接返回
    if(obj.isCopy == true){
        // 在原来对象中保存一下新的地址, 方便返回
        return obj.newAddr;
    }
    // 这里假设有一个全局变量 ADDR 指向空闲内存的首地址
    // 这里直接将 obj的size大小复制到ADDR的地方
    copy_data(ADDR, obj, obj.size);
    // 记录复制
    obj.isCopy = true;
    obj.newAddr = ADDR;
    // 更新空闲地址
    ADDR += size;
    // 将所有子对象复制
    for(child in children){
        child = copy(child);
    }
    return obj.newAddr;
}

将所有根集合中的对象依次调用copy函数, 完成复制.

复制算法分配新的对象变简单了, 有没有? 因为地址都是连续的, 所以申请新的地址也不用遍历链表等一堆操作, 直接按着地址划分空间就行了.

分析

很明显, 复制算法解决了标记清除的一个大问题, 内存碎片化严重. 在这里, 根本不存在碎片化问题的好嘛. 其相比标记清除的优势还是有一些的:

1. 内存不会发生碎片化
2. 最大暂停时间更短: 复制算法只需要遍历所有的活动对象, 而不需要遍历堆, 比标记清除要少一个堆的遍历, 故而执行更快.
3. 内存分配高效: 标记清除是怎么分配内存的? 通过一个空闲地址的链表, 然后挨个找. 而复制算法将所有可分配的内存都放到一起了, 直接切割即可.
4. 更好的局部访问: 复制算法复制后将对象与子对象放到一起, 这样缓存在读取的时候就能够一起读取, 防止多次读取数据.

当然, 缺点也很明显. 将堆一分为二, 使用效率急速下滑.

1. 堆的使用效率低, 只有1/2
2. 频繁的递归调用函数. 对栈的压力比较大, 但是我们都知道, 所有用递归能写的都可以换成循环来实现, 所以个人感觉这个并不是问题.

我看到有一种多空间复制算法, 为了提高堆的使用效率. 将堆空间分成N份, 其中的两份使用复制算法, 剩余的使用其他方法执行GC. 我实在是没有明白这么做的好处在哪....