Space-and-time efficient garbage collectors for parallel systems

ABSTRACT

As multithreaded server applications and runtime systems prevail, garbage collection is becoming an essential feature to support high performance systems. The fundamental issue of garbage collector (GC) design is to maximize the recycled space with minimal time overhead. This paper proposes two innovative solutions: one to improve space efficiency, and the other to improve time efficiency. To achieve space efficiency, we propose the Space Tuner that utilizes the novel concept of allocation speed to reduce wasted space. Conventional static space partitioning techniques often lead to inefficient space utilization. The Space Tuner adjusts the heap partitioning dynamically such that when a collection is triggered, all space partitions are fully filled. To achieve time efficiency, we propose a novel parallelization method that reduces the compacting GC parallelization problem into a tree traversal parallelization problem. This method can be applied for both normal and large object compaction. Object compaction is hard to parallelize due to strong data dependencies such that the source object can not be moved to its target location until the object originally in the target location has been moved out. Our proposed algorithm overcomes the difficulties by dividing the heap into equal-sized blocks and parallelizing the movement of the independent blocks. It is noteworthy that these proposed algorithms are generic such that they can be utilized in different GC designs.

REFERENCES

• 1: Patrick J. Caudill , Allen Wirfs-Brock, A third generation Smalltalk-80 implementation, Conference proceedings on Object-oriented programming systems, languages and applications, p.119-130, September 29-October 02, 1986, Portland, Oregon, United States
• 2: Michael Hicks , Luke Hornof , Jonathan T. Moore , Scott M. Nettles, A study of large object spaces, Proceedings of the 1st international symposium on Memory management, p.138-145, October 17-19, 1998, Vancouver, British Columbia, Canada
• 3: Sunil Soman , Chandra Krintz , David F. Bacon, Dynamic selection of application-specific garbage collectors, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029880]
• 4: David A. Barrett , Benjamin G. Zorn, Garbage collection using a dynamic threatening boundary, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.301-314, June 18-21, 1995, La Jolla, California, United States
• 5: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 6: Christine H. Flood , David Detlefs , Nir Shavit , Xiaolan Zhang, Parallel garbage collection for shared memory multiprocessors, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.21-21, April 23-24, 2001, Monterey, California
• 7: Diab Abuaiadh , Yoav Ossia , Erez Petrank , Uri Silbershtein, An efficient parallel heap compaction algorithm, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 8: Haim Kermany , Erez Petrank, The Compressor: concurrent, incremental, and parallel compaction, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 9: Michal Wegiel , Chandra Krintz, The mapping collector: virtual memory support for generational, parallel, and concurrent compaction, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 10: Apache Harmony: Open-Source Java SE. http://harmony.apache.org/
• 11: Spec: The Standard Performance Evaluation Corporation. http://www.spec.org/
• 12: Dacapo Project: The DaCapo Benchmark Suite. http://www-ali.cs.umass.edu/dacapo/index.html
• 13: Ming Wu and Xiao-Feng Li, Task-pushing: a Scalable Parallel GC Marking Algorithm without Synchronization Operations. In Proceedings of IEEE International Parallel and Distributed Processing Symposium, Long Beach, California, 2007.
• 14: Common Language Runtime Overview. http://msdn.microsoft.com/en-us/library/ddk909ch(vs.71).aspx
• 15: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 16: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 17: Toshio Endo , Kenjiro Taura , Akinori Yonezawa, A scalable mark-sweep garbage collector on large-scale shared-memory machines, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509641]
• 18: Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174673]
• 19: Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.274-284, June 18-21, 2000, Vancouver, British Columbia, Canada
• 20: Hezi Azatchi , Yossi Levanoni , Harel Paz , Erez Petrank, An on-the-fly mark and sweep garbage collector based on sliding views, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

General Terms:
Algorithms, Management, Performance

Keywords:
garbage collection, java virtual machine