垃圾回收 (Garbage Collection, GC) 為記憶體管理的其中一種機制，能夠自動且正確地回收沒再使用的空間，被廣泛地使用在高階的程式語言之中。其中標記壓縮法 (Mark-Compact Collection, MC) 提供良好的空間使用率和快速的配置object，適合應用在記憶體資源有限的系統。但標記壓縮法會重複地讀取object 增加程式的暫停時間 (pause time)，並且暫停時間會隨著記憶體變大而增加。本論文針對“減少重複讀取object 的次數” 提出Lazy-Compact Collector (LC) 以“合併連續的deadobject” 和“不搬移使用率較高的區塊內的live object” 這兩概念。以SPECjcm98 和DaCapo2006 為測試軟體，從實驗看出使用LC 的程式所需的最小記憶體空間與Jikes RVM 所提供的MC 相比稍略增加約1~2MB；暫停時間較不會受記憶體大小影響；而總暫停時間有明顯的改善，尤其在記憶體較小的條件下有良好的表現。

The mark-compact garbage collection algorithm shifts live objects so that they are next to each other to maximize space utilization efficiency and enable rapid object allocation. However, the algorithm requires multiple passes over a heap of objects, extending the time required for reclaiming unused memory. To shorten the collection time, we propose a lazy-compact garbage collection algorithm that avoids accessing dead objects by merging contiguous dead objects and reduces the number of object relocations. In this paper, we implemented the proposed algorithm in the Jikes RVM, and measured the performance with the SPECjvm98 and DaCapo2006 benchmark suites. The proposed algorithm reduces the pause time of programs by 25% on average.

[1] Ibm® sdk, java™ technology edition, version 7. http://www-01.ibm.com/ support/knowledgecenter/SSYKE2_7.0.0/com.ibm.java.win.70.doc/ diag/understanding/mm_allocation_loa.html.
[2] Jikesrvm. http://jikesrvm.org/.
[3] .net framework 4.5 fundamentals of garbage collection. http://msdn.microsoft. com/en-us/library/ee787088(v=vs.110).aspx.
[4] Standard performance evaluation corporation. specjvm98 documentation. http: //www.spec.org/jvm98/. release 1.03 edition, March, 1999.
[5] D. Abuaiadh, Y. Ossia, E. Petrank, and U. Silbershtein. An efficient parallel heap compaction algorithm. ACM SIGPLAN Notices, 39(10):224–236, 2004.
[6] D. F. Bacon, C. R. Attanasio, H. B. Lee, V. Rajan, and S. Smith. Java without the coffee breaks: A nonintrusive multiprocessor garbage collector. In ACM SIGPLAN Notices, volume 36, pages 92–103. ACM, 2001.
[7] S. M. Blackburn, R. Garner, C. Hoffmann, A. M. Khang, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovic, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The dacapo benchmarks: Java benchmarking development and analysis. In ACM Sigplan Notices, volume 41, pages 169–190. ACM, 2006.
[8] S. M. Blackburn and K. S. McKinley. Ulterior reference counting: Fast garbage collection without a long wait. In ACM SIGPLAN Notices, volume 38, pages 344–358. ACM, 2003.
[9] S. M. Blackburn and K. S. McKinley. Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance. In ACM SIGPLAN Notices, volume 43, pages 22–32. ACM, 2008.
[10] H.-J. Boehm and M. Weiser. Garbage collection in an uncooperative environment. Software: Practice and Experience, 18(9):807–820, 1988.
[11] J. M. Chang, W.-M. Chen, P. A. Griffin, and H.-Y. Cheng. Cyclic reference counting by typed reference fields. Computer Languages, Systems & Structures, 38(1):98–107, 2012.
[12] J. Cohen and A. Nicolau. Comparison of compacting algorithms for garbage collection. ACM Transactions on Programming Languages and Systems (TOPLAS), 5(4): 532–553, 1983.
[13] G. E. Collins. A method for overlapping and erasure of lists. Communications of the ACM, 3(12):655–657, 1960.
[14] A. Demers, M. Weiser, B. Hayes, H. Boehm, D. Bobrow, and S. Shenker. Combining generational and conservative garbage collection: Framework and implementations. In Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 261–269. ACM, 1989.
[15] D. Detlefs, C. Flood, S. Heller, and T. Printezis. Garbage-first garbage collection. In Proceedings of the 4th international symposium on Memory management, pages 37–48. ACM, 2004.
[16] S. Dieckmann and U. Hölzle. A study of the allocation behavior of the specjvm98 java benchmarks. In ECOOP’99—Object-Oriented Programming, pages 92–115. Springer, 1999.
[17] T. Domani, G. Goldshtein, E. K. Kolodner, E. Lewis, E. Petrank, and D. Sheinwald. Thread-local heaps for java. ACM SIGPLAN Notices, 38(2 supplement):76–87, 2003.
[18] R. R. Fenichel and J. C. Yochelson. A lisp garbage-collector for virtual-memory computer systems. Communications of the ACM, 12(11):611–612, 1969.
[19] D. A. Fisher. Bounded workspace garbage collection in an address-order preserving
list processing environment. Information Processing Letters, 3(1):29–32, 1974.
[20] C. H. Flood, D. Detlefs, N. Shavit, and X. Zhang. Parallel garbage collection for shared memory multiprocessors. In Java Virtual Machine Research and Technology Symposium, 2001.
[21] B. K. Haddon and W. M. Waite. A compaction procedure for variable-length storage elements. The Computer Journal, 10(2):162–165, 1967.
[22] M. Hicks, L. Hornof, J. T. Moore, and S. M. Nettles. A study of large object spaces. In ACM SIGPLAN Notices, volume 34, pages 138–145. ACM, 1998.
[23] M. Hirt and M. Lagergren. Oracle JRockit: The Definitive Guide. Packt Publishing Ltd, 2010.
[24] R. Jones and R. D. Lins. Garbage collection: algorithms for automatic dynamic memory management. 1996.
[25] R. D. Lins. Cyclic reference counting with lazy mark-scan. Information Processing Letters, 44(4):215–220, 1992.
[26] J. McCarthy. Recursive functions of symbolic expressions and their computation by machine. Communications of the ACM, 3(4):184–195, 1960.
[27] K. Morikawa, T. Ugawa, and H. Iwasaki. Adaptive scanning reduces sweep time for the lisp2 mark-compact garbage collector. In ACM SIGPLAN Notices, volume 48, pages 15–26. ACM, 2013.
[28] F. L. Morris. A time-and space-efficient garbage compaction algorithm. Communications of the ACM, 21(8):662–665, 1978.
[29] T. Printezis. Hot-swapping between a mark&sweep and a mark&compact garbage collector in a generational environment. In Proceedings of the 2001 Symposium on Java TM Virtual Machine Research and Technology Symposium-Volume 1, pages 20–20. USENIX Association, 2001.
[30] R. Shahriyar, S. M. Blackburn, and K. S. McKinley. Fast conservative garbage collection. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, pages 121–139. ACM, 2014.
[31] L. Tong and F. C. M. Lau. Index-compact garbage collection. In Programming Languages and Systems, pages 271–286. Springer, 2010.
[32] L. Tong and F. C. M. Lau. Skew-space garbage collection. Science of Computer Programming, 78(5):445–457, 2013.
[33] P. R. Wilson. Uniprocessor garbage collection techniques. In Memory Management, pages 1–42. Springer, 1992.
[34] P. R. Wilson, M. S. Johnstone, M. Neely, and D. Boles. Dynamic storage allocation: A survey and critical review. In Memory Management, pages 1–116. Springer, 1995.