不同的复制算法比较及对程序员的启迪
前面提到整个JVM中只有串行回收按照Cheney的设计实现新生代回收，其他的垃圾回收器在新生代回收时都对Cheney的复制算法进行了增强。
其中最大的改变就是不使用宽度优先，而是使用深度优先的处理方式。其中Moon在1984年提出了一种近似深度优先遍历的处理方式，称为层次遍历，使用层次遍历大概可以将GC效果提升6%。
研究发现，宽度优先导致的性能问题在于数据局部性，这会导致数据访问缓存命中率下降。
那为什么宽度优先的复制算法会导致垃圾回收后应用运行时存在数据局部性问题呢？根本原因在于应用中对象的访问模型。测试结果表明，大多数应用在访问对象时同时访问父对象和子对象的概率更高，而同时访问两个兄弟对象的概率更低。也就说应用中对象的访问从统计角度更多的是按照深度优先进行，而不是按照宽度优先进行的。
这样的结果导致使用宽度优先复制算法在对象重排以后和应用中对象的访问模型并不一致，更容易导致缓存不命中，从而导致性能下降。
从这个角度出发，如果决定使用串行垃圾回收时，在开发应用的时候对象的访问尽量遵循宽度优先的访问方式；如果决定使用其他垃圾回收器，在开发应用的时候对象尽量采用深度优先的访问方式。这样的做法就能保证应用中对象的访问方式在垃圾回收执行完成之后和对象的组织方式一致，从而取得更好的运行效果。
最后需要指出的是，采用深度优先遍历的实现通常需要一个辅助空间栈（Stack）。但使用辅助栈会带来额外的问题，那就是栈空间应该多大？过大会导致空间浪费，太小则导致标记过程栈溢出。所以需要一种合理的设计，既不浪费空间，又能在栈溢出时正确处理。那么JVM是如何解决这个问题的呢？读者可以先思考一下这个问题。
虽然JVM中并没有采用Moon算法实现分代的复制，但是在另一款开源的JVM产品OpenJ9中，分代回收的复制算法优先使用的就是并行的Moon算法。
这里简单介绍一下Moon的算法，由于Moon算法是Cheney算法的优化，因此我们先回顾一下Cheney的算法思想，再来看看Moon是如何优化的。
Cheney算法可以简单总结为：在往目标空间复制对象的时候，额外引入了两个指针，分别为Scan和Free，Scan和Free直接在内存空间中模拟了队列，队列中存放的是待处理的对象，从Scan开始遍历直到Scan和Free重合，对象就全部处理完成。如图3-38所示，分配空间用浅蓝色表示，To空间中使用3种颜色描述对象处理的状态。
图3-38 Cheney算法示意图
Moon算法的改进主要包含如下几个要点：
1）将目标空间划分为更细粒度的块，如图3-39中的A、B、C、D、E。
2）在标记/复制的时候，总是从最后一个尚未填满的块开始，如图3-39中的块D会被先处理，所以使用了一个PrimaryScan表示扫描先从这里开始。
当PrimaryScan和Free之间的对象标记/复制完成之后（注意，这里仍然采用宽度优先遍历的方式进行处理），如果块D的剩余空间不能满足对象的填充，那么块E会被使用。
3）当块D被填满之后，再按照SecondaryScan指向的位置开始再次进行标记/复制。当再次出现了未填满的块时，则按照上一步中的方法继续优先处理。
从这些描述可以看出，Moon算法最大的一个缺点是有些对象可能需要扫描2次才能完成。例如图中的D填充满了之后，从块B开始扫描，然后再扫描块C（实际上块C的对象在第一次遇到未填满的时候已经进行了一次扫描）。算法的示意图如图3-39所示。
图3-39 Moon算法示意图
使用Moon算法的效果如何？这里采用论文中的示例来演示一下，如图3-40所示。
- 宽度优先算法，得到对象的存储顺序为O1、O2、……、O14、O15。
- 深度优先复制算法，得到对象的存储顺序为O1、O2、O4、O8、O9、
- O5、O10、O11、O3、O6、O12、O13、O7、O14、O15。
使用Moon修正的算法，假设每个块只能保存3个对象，得到对象的存储顺序为O1、O2、O3、O4、O8、O9、O5、O10、O11、O6、O12、O13、O7、O14、O15。
图3-40 Moon算法示例
结论是，深度优先得到的对象存储序列和Moon的修正算法仅仅只有O3的位置有所不同，所以Moon算法也被称为近似的深度优先复制算法。同时也要注意，块大小影响最终的结果。在本例中块大小设置为保存3个对象，最后的结果和深度优先复制算法类似。但是当块大小设置得更大一些，结果就可能与深度优先差别比较大了。
例如块的大小设置为保持5个对象，此时得到对象的存储顺序为：O1、O2、O3、O4、O5、O6、O12、O13、O7、O14、O15、O8、
O9、O10、O11。可以看到，此时对象的存储顺序与宽度优先遍历更为接近（假设以对象在相同位置为标准）。再比如设置块大小为保存15个对象，此时Moon就完全退化为宽度优先复制算法了。从这里可以看出这个算法的关键是为块设置一个合适的大小。
另外，Moon是一个串行的算法，Siegwart在2006年将Moon算法修改成并行算法。OpenJ9中层次遍历就是基于这篇论文实现的。由于并行算法涉及任务切分、任务均衡等细节，本章主要关注串行算法的实现，因此不对OpenJ9中的实现展开介绍。
在这里，我们谈论了宽度优先遍历、层次遍历和深度优先遍历。研究表明，层次遍历的效果比宽度优先遍历好。那么层次遍历和深度优先遍历的效果相比如何？
2018年，OpenJ9社区发起了一个针对层次遍历的优化，为OpenJ9中增加一款基于深度优先遍历的并行实现。
这里仅仅介绍一下优化改进后的效果，其作者针对3种应用分别使用层次遍历和深度优先遍历进行了测试，从测试结果来看在吞吐量和停顿时间上，基于深度优先遍历的回收算法都有明显的优势。测试选择的3种应用是：交易型应用（Transactional）、数据处理型应用（Data Compilation）和数据库应用（Database Processing）。测试中使用OpenJ9的gencon垃圾回收器，该垃圾回收器的新生代既支持宽度优先遍历又支持层次遍历，默认使用层次遍历。作者在测试中指明了测试使用的OS、内存大小等信息，对测试过程感兴趣的读者可以阅读原文。深度优先和层次优先遍历的性能测试对比结果如表3-4所示。
表3-4 深度优先和层次遍历优先性能测试结果
针对3种应用，GC的吞吐量分别提升22.671%、20.864%和2.805%；GC的停顿时间分别减少18.01%、16.074%和3.113%。另外，原文中还给出了测试套跑分的提升，但比较遗憾的是作者并未给出测试套的更多信息，所以本书并未列出。另外，需要注意的是，该优化最终并未合入OpenJ9的主线版本（可能与OpenJ9的技术路线有关）。
最后做一个简单的总结：从目前的论文研究和测试结果来看，使用深度优先遍历的回收算法效果最好，层次遍历次之，宽度优先遍历最差；深度优先遍历在实现时有额外的内存空间开销，而层次遍历和宽度优先遍历没有。
对于程序员来说，应了解不同产品中采用的算法以及算法本身的使用场景，在开发应用时结合选择的回收算法，使用深度优先的方式或者宽度优先的方式来访问对象，可以获得额外的收益。
