不同的複製算法比較及對程式設計師的啟迪
前面提到整個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種顏色描述對象處理的狀態。
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所示。
使用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。
結論是，深度優先得到的對象存儲序列和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種應用，GC的吞吐量分別提升22.671%、20.864%和2.805%；GC的停頓時間分別減少18.01%、16.074%和3.113%。另外，原文中還給出了測試套跑分的提升，但比較遺憾的是作者並未給出測試套的更多信息，所以本書並未列出。另外，需要注意的是，該優化最終並未合入OpenJ9的主線版本（可能與OpenJ9的技術路線有關）。
最後做一個簡單的總結：從目前的論文研究和測試結果來看，使用深度優先遍歷的回收算法效果最好，層次遍歷次之，寬度優先遍歷最差；深度優先遍歷在實現時有額外的內存空間開銷，而層次遍歷和寬度優先遍歷沒有。
對於程式設計師來說，應了解不同產品中採用的算法以及算法本身的使用場景，在開發應用時結合選擇的回收算法，使用深度優先的方式或者寬度優先的方式來訪問對象，可以獲得額外的收益。
本文給大家講解的內容是JVM垃圾回收器詳解：串行回收，不同的複製算法比較及對程式設計師的啟迪
- 下篇文章給大家講解的內容是JVM垃圾回收器詳解：並發標記清除回收，內存管理
- 感謝大家的支持！