0x00 前言
关于Java的垃圾回收机制，大家都比较清楚了。本文主要是回收效率的角度，探讨为什么Hotspot等主流虚拟机采用了复制算法进行GC。
0x01 回收工作的开展
我们知道，只有没有被引用指向的对象才会被回收。那怎么判断没有被引用指向？可以采用引用计数算法(Reference Counting)和可达性分析算法(Reachability Analysis)，后者是主流，思想是从GC ROOTS的对象作为起点去搜索对象是否不可达（其实就是无向图的遍历），这里就不赘述了。
另外，上面说的回收都是回收堆内存中的对象，方法区(Hotspot VM中的永久代(PermGen))也是可以回收的。但是回收性价比比较低，JVM虚拟机实现规范中不要求方法区实现GC。
方法区的回收条件非常苛刻，只有同时满足以下三个条件才会被回收。简单了解下吧。
- 所有实例被回收
- 加载该类的ClassLoader被回收
- Class对象无法通过任何途径访问(包括反射)
0x02 采取什么策略进行回收
最容易想到的方法，就是用引用计数和可达性分析进行判断后做标记，再统一清除。
GC确实有这种策略。叫做：
1) 标记-清除(Mark-Sweep)算法
分为两个阶段，标记和清除。注意，标记的是需要回收的对象。这种算法的时间复杂度其实并不高，或者说已经是最高的了：既然可达性分析算法是无向图的遍历，那么假设它采用邻接表存储对象的地址，时间复杂度就是O(n + e)，e为无向图中边的数目或有向图中弧的数目。Sweep的过程可以理解为O(1)，因为只要把已经标记的对象直接释放就行了。
但是这种方法的问题在于，产生了内存碎片。所以说，这种算法虽然效率高，但是只适合存活的对象较多的老年代(Old Generation)。
扩展一下，根据Java虚拟机的规范的规定，Java堆可以处在物理不连续的空间，只要逻辑连续就可以，跟磁盘一样。那么，既然可以物理不连续，那标记-清除算法造成内存碎片又有什么关系？我猜想是因为，想要在物理不连续的空间分配内存，还需要特殊的算法来记录前一个slot结束位置和后一个slot开始的位置，复杂度仍很高。
怎么对这种算法进行改进呢？怎么让内存碎片消失？
我自己想了一下，很容易想到的方法就是数组的inplace替换，就是把内存想象成一个大的连续区域，标记完成之后把有用的往前挪到标记的位置上就行了嘛。
事实上确实有这种算法，称作：
2) 标记-整理(Mark-Compact)算法
标记过程仍然与“标记-清除”算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，然后直接清理掉端边界以外的内存。
具体操作起来是怎样的？要记住我们标记的是可达性算法判定的可回收的对象，而不是不可回收的对象。那如果对于可回收对象比较多的新生代，我们需要把对这些可回收的对象的内存地址进行操作（比如内存地址首尾相接，这样才能判定存活的对象是否能够存放在一个连续区域），这个操作的复杂度是O(m)，m是被标记为垃圾的对象的数量。所以同样，这种方法适用于存活对象较多的老年代。
根据调查，在实际应用过程中98%的对象都是朝生夕死的新生代（存放对象实例的Heap区域），每次回收，活下来的对象很少。所以上面的整理算法复杂度会接近O(n + e) + O(n)，整理过程会耗费很多时间。
其实标记整理算法的问题在于，需要整理出一片可用的内存区域出来，让存活的对象移动。那能不能不整理内存呢？于是就有了复制算法。
3) 复制算法
这是Hostspot等商业虚拟机广泛采用的算法。注意这里是遍历存活对象，所以复杂度很低。为了方便理解我们可以想象成，整个堆内存只有一半能用，回收的时候把DFS遍历到的对象复制到另一半，然后把原来的一般整个擦除，最后再交换两边的区域，这样From区域又可以继续分配内存了。非常简单。
缺点是，会需要占用一些空间换时间。
(1)将堆分成From和To两个内存块，当From被占满时GC将From中的存活对象复制到To中，同时将From和To交换。
(2)通过递归遍历GC root(即采用深度优先)复制存活对象，对于已经复制过的标记其COPIED字段。
(3)复制过的对象将在From的对象的forwarding记录To中该对象地址，以便于其余引用了该对象的引用进行修改。
(4)分配对象时将先判断From中连续可用空间是否够用(复制算法不存在碎片)，如果不够则进行一次GC，还不够则分配失败。
但是由于存活的对象少嘛，所以可以把to内存分配得小点。实际应用中，会把Eden、SurvivorFrom和SurviorTo分成8:1:1的比例。
两块Survivor区域(From和To)的原因是，SurvivorFrom区域在每次Minor GC的时候，会跟Eden一起被扫描，存活的放到SurvivorTo区域，同时把这些对象的年龄+1（如果ServicorTo不够位置了就放到老年区）；然后，清空Eden和ServivorFrom中的对象。然后把From和To的区域互换（其实就是清空To区域给下一次使用)。
我又考虑了一下，为什么不能只有单个survivor区域，在GC的时候inplace替换survivor区域的内存？应该是因为单个Survivor区域的话，由于From区域也保存了内容，这个区域的内容会被覆盖。那发散一下，可以先回收单个survivor区域的内存，再回收Eden内存的对象，进行堆顶指针移动就行了，而且这样也不影响对象年龄增加的那一套规则（至于为什么没有这么做，其实也不需要深究了，理解它的原理就行了）。
这种算法当控件存活的对象比较少时，极为高效，如果存活得多就不好了。更关键的是需要一块内存交换空间用于进行对象的移动。
Ref:
[Ref1]
