A generational on-the-fly garbage collector for Java

ABSTRACT

An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications running on multiprocessor servers, where it is important to fully utilize all processors and provide even response time, especially for systems for which stopping the threads is a costly operation. In this work, we report on the incorporation of generations into an on-the-fly garbage collector. The incorporation is non-trivial since an on-the-fly collector avoids explicit synchronization with the program threads. To the best of our knowledge, such an incorporation has not been tried before. We have implemented the collector for a prototype Java Virtual Machine on AIX, and measured its performance on a 4-way multiprocessor. As for other generational collectors, an on-the-fly generational collector has the potential for reducing the overall running time and working set of an application by concentrating collection efforts on the young objects. However, in contrast to other generational collectors, on-the-fly collectors do not move the objects; thus, there is no segregation between the old and the young objects. Furthermore, on-the-fly collectors do not stop the threads, so there is no extra benefit for the short pauses obtained by generational collection. Nevertheless, comparing our on-the-fly collector with and without generations, it turns out that the generational collector performs better for most applications. The best reduction in overall running time for the benchmarks we measured was 25%. However, there were some benchmarks for which it had no effect and one for which the overall running time increased by 4%.

REFERENCES

• 1: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 2: Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992 [doi>10.1145/130854.130862]
• 3: Mordechai Ben-Ari, On-the-Fly Garbage Collection: New Algorithms Inspired by Program Proofs, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.14-22, July 12-16, 1982
• 4: Mordechai Ben-Ari, Algorithms for on-the-fly garbage collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.333-344, July 1984 [doi>10.1145/579.587]
• 5: Jeff Chan and Nik Shaylor. Multithreaded Ray Tracer. Sun Microsystems, private communications.
• 6: Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 7: J. DeTreville. Experience with Concurrent Garbage Collector for Mudula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, November 1990.
• 8: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , Carel S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Language Hierarchies and Interfaces, International Summer School, p.43-56, July 23-August 02, 1975
• 9: 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]
• 10: 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]
• 11: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 12: T. Domani, E. Kolodner, and E. Petrank A Generational On-the-fly Garbage Collector for Java. Technical Report 88.385 IBM Haifa Reesrach Lab. Web
• 13: John R. Ellis, Kai Li, and Andrew W. Appel. Realtime concurrent collection on stock multiprocessors. Technical Report DEC-SRC-TR-25, DEC Systems Research Center, Palo Alto, CA, February 1988.
• 14: David Gries, An exercise in proving parallel programs correct, Communications of the ACM, v.20 n.12, p.921-930, Dec. 1977 [doi>10.1145/359897.359903]
• 15: Randy Heisch and Kaivalya Dixit. Jumble: An Anagram Generator. Private communications.
• 16: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, ACM SIGPLAN Notices, v.27 n.10, p.92-109, Oct. 1992
• 17: Paul Hudak , Robert M. Keller, Garbage collection and task deletion in distributed applicative processing systems, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.168-178, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802147]
• 18: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 19: E. K. Kolodner and E. Lewis. Using a Color Toggle to Reduce Synchronization in the DLG Collector. Private Communcations, 1998.
• 20: H. T. Kung and S. W. Song. An efficient parallel garbage collection system and its correctness proof. In IEEE Symposium on Foundations of Computer Science, pages 120-131. IEEE Press, 1977.
• 21: L. Lamport. Garbage collection with multiple processes: an exercise in parallelism. In Proceedings of the 1976 International Conference on Parallel Processing, pages 50-54, 1976.
• 22: Lorenz Huelsbergen , Phil Winterbottom, Very concurrent mark-&-sweep garbage collection without fine-grain synchronization, Proceedings of the 1st international symposium on Memory management, p.166-175, October 17-19, 1998, Vancouver, British Columbia, Canada
• 23: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 24: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 25: SPECjvm. Spec - The Standard Performance Evaluation Corporation. Web access http://www.spec.org/osg/jvm98/.
• 26: Patrick Sobalvarro, A Lifetime-based Garbage Collector for LISP Systems on General- Purpose Computers, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 27: 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]
• 28: 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]
• 29: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Design, Management

Keywords:
garbage collection, generational garbage collection, memory management, programming languages