节点复制

节点复制是另一种追踪式收集，在回收阶段和标记-清除采用了不同的策略，简单地说，标记-清除主动释放垃圾，而节点复制是将可达集拷贝出来，然后统一回收整块内存

前面说过，据统计80%~98%的对象在建立之后很快就会销毁，由此可以预见，在正常情况下，当启动垃圾回收的时候，可达集和垃圾集合是不成比例的，堆空间中很可能只有少部分的内容可达，剩下都是垃圾，标记-清除算法的时间和对象数量相关，而节点复制由于只拷贝可达集，因此时间上只和可达对象占用内存相关，如果大部分情况下可达集比垃圾集合小很多，节点复制的优势很大

这里还有两个细节需要注意： 一、标记-清除时间和对象数量相关，节点复制和可达对象占用内存相关，这就是说，有时候可达对象很少，但都是很大的对象（比如数组），节点复制也可能比较慢，可能还不如标记-清除，不幸的是，很多程序中长期存在（即垃圾回收时候经常可达）的对象都比较大，这个问题的解决方案在后面讨论 二、可达集被拷贝到另外的空间，由于可达集在最坏情况下可能填满堆空间，因此程序正常运行时，需要两块同样大小的空间，任何时候只用其中一个半区，在垃圾收集时将可达集复制到另一半区，然后切换当前使用的堆空间到这个半区，继续执行。另外，为了拷贝完成后在常数时间初始化之前使用的半区，需要自己管理内存的申请和释放，而引用计数和标记-清除则可以直接使用运行环境的接口（比如malloc和free），话虽如此，很多标记-清除算法也是自己管理内存的

节点复制需要将内存划为两个半区，程序只能使用其中一半的容量，这是它的一个缺点，但从另一个角度看，在标记阶段就不用发愁内存的使用问题了，可以利用另一个半区的内存进行标记过程DFS栈空间，或BFS的队列空间

节点复制还会很自然地压缩数据，标记-清除算法在运行一段时间后，内存中可能会出现很多碎片，从而影响局部性，以及有内存浪费的问题，而节点复制在复制可达集的时候，对象都会挨个排在新的半区，而老的半区是全部释放，因此没有碎片问题

除了浪费内存，碎片过多还会影响内存申请的速度，因为空闲内存碎片一般用链表管理，有的时候，为了找到一个合适大小的空间，导致申请内存时间过长，影响效率。节点复制的内存管理机制就非常简单了：

char mem = new char[SIZE]; //当前半区
int used_size = 0;
void malloc(int size)
{
if (size > SIZE - used_size)
{
run_gc(); //当前半区内存不够了，进行收集
if (size > SIZE - used_size)
{
crash("内存不足"); //垃圾收集后内存还是不够，程序退出
}
}
void *p = &mem[used_size];
used_size += size;
return p;
}

其实，这就是一个不断增长的栈而已，申请和整个半区初始化，也就是调整used_size，速度非常快，根据Apple提出的理论，如果每次垃圾回收，可达集合和垃圾集合空间的比例小于1:7，则使用节点复制垃圾收集的效率要比手工控制内存申请释放高，因为可达集小，每次垃圾收集消耗的时间很少，在实践中也可以验证，例如dhrystone这个benchmark会频繁创建和销毁小对象，用C++和java分别实现它，代码等价的情况下，测试的结果C++比java还要慢不少（就这个例子而言，jvm中的节点复制收集机制起主要作用），如果不理解节点复制的内存管理方式，这个结论可能会毁很多人的三观

虽然有很多优点，但如果不想浪费一半的进程内存，或可达集较大的情况下，单纯使用节点复制就可能还不如标记-清除，尤其是它在两个半区直接来回切换，局部性也是一个大问题，事实上，如果可达集很大，标记-清除也会受到很大影响，因为每次可收集的空闲空间少了，会导致更频繁的收集，要想更好的解决问题，就不能简单地使用这两者，需要对算法做进一步改进