Tamar Domani
Erez Petrank
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%.
- 1.Henry G. Baker. List processing in real-time on a serial computer. Communications of the A CM, 21(4):280-94, 1978. Google Scholar
Digital Library
- 2.Henry G. Baker. The Treadmill, real-time garbage collection without motion sickness. A CM $IGPLAN Notices, 27(3):66-70, March 1992. Google ScholarDigital Library
- 3.Mordechai Ben-Ari. On-the-fly garbage collection: New algorithms inspired by program proofs. In M. Nielsen and E. M. Schmidt, editors, Automata, languages and programming. Ninth colloquium (Aarhus, Denmark), pages 14-22, New York, July 12-16 1982. Springer-Verlag. Google ScholarDigital Library
- 4.Mordechai Ben-Ari. Algorithms for on-the-fly garbage collection. A CM Transactions on Programming Languages and Systems, 6(3):333-344, July 1984. Google ScholarDigital Library
- 5.Jeff Chan and Nik Shaylor. Multithreaded Ray Tracer. Sun Microsystems, private communications.Google Scholar
- 6.Alan Demers, Mark Weiser, Barry Hayes, Hans Boehm, Daniel G. Bobrow, and Scott Shenker. Combining generational and conservative garbage collection: Framework and implementations. In Conference Record of the Seventeenth Annual A CM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, January 1990. ACM Press, pages 261-269. Google ScholarDigital Library
- 7.J. DeTreville. Experience with Concurrent Garbage Collector for Mudula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, November 1990.Google Scholar
- 8.Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. Onthe-fly garbage collection: An exercise in cooperation. In Lecture Notes in Computer Science, No. 46. Springer-Verlag, New York, 1976. Google ScholarDigital Library
- 9.Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. Onthe-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21(11):965-975, November 1978. Google ScholarDigital Library
- 10.D. Doligez and G. Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the Twenty-first Annual A CM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices. ACM Press, 1994, pages 113-123. Google ScholarDigital Library
- 11.D. Doligez and X. Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Conference Record of the Twentieth Annual A CM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices. ACM Press, January 1993. Google ScholarDigital Library
- 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. WebGoogle Scholar
- 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.Google Scholar
- 14.David Gries. An exercise in proving parallel programs correct. Communications of the A CM, 20(12):921-930, December 1977. Google ScholarDigital Library
- 15.Randy Heisch and Kaivalya Dixit. Jumble: An Anagram Generator. Private communications.Google Scholar
- 16.Antony L. Hosking, J. Eliot B. Moss, Darko Stefanovid. A Comparative Performance Evaluation of Write Barrier Implementations. In Proceedings of the A CM Conference on Object-Oriented Programming Systems, Languages, and Applications, pp 92- 109 (Vancouver, Canada, October 1992). ACM SIG- PLAN Notices 27(10), October 1992. Google ScholarDigital Library
- 17.Paul Hudak and Robert M. Keller. "Garbage Collection and Task Deletion in Distributed Systems. In A CM Symposium on Lisp and Functional Programruing, pp. 168-178, Pittsburgh, PA, August 1982. Google ScholarDigital Library
- 18.R. E. Jones and R. D. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, July 1996. Google ScholarDigital Library
- 19.E. K. Kolodner and E. Lewis. Using a Color Toggle to Reduce Synchronization in the DLG Collector. Private Communcations, 1998.Google Scholar
- 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.Google ScholarDigital Library
- 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.Google Scholar
- 22.L. Huelsbergen and P. Winterbottom. Very Concurrent Mark-Sz-Sweep Garbage Collection without Fine-Grain Synchronization. In Proceedings of the 1998 International Symposium on Memory Management, pages 50-54, 1998. Google ScholarDigital Library
- 23.H. Lieberman and C. E. Hewitt. A Real Time Garbage Collector Based on the Lifetimes of Objects. Communicaitons of the A CM, 26(6), pages 419-429, 1983. Google ScholarDigital Library
- 24.David A. Moon. Garbage collection in a large LISP system. In Guy L. Steele, editor. Conference Record of the 1984 A CM Symposium on Lisp and Functional Programming, Austin, TX, August 1984, ACM Press, pages 235-245. Google ScholarDigital Library
- 25.SPECjvm. Spec - The Standard Performance Evaluation Corporation. Web access http://www.spec.org/osg/jvm98/.Google Scholar
- 26.Patrick Sobalvarro. A lifetime-based garbage collector for Lisp systems on general-purpose computers. Technical Report AITR-1417, MIT, AI Lab, February 1988. Google ScholarDigital Library
- 27.Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the A CM, 18(9):495-508, September 1975. Google ScholarDigital Library
- 28.Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the A CM, 18(9):495-508, September 1975. Google ScholarDigital Library
- 29.D. Ungar. Generation Scavenging: A Nondisruptive High Performance Storage Reclamation Algorithm. Proceedings of the A CM Symposium on Practical Software Development Environments, ACM SIGPLAN Notices Vol. 19, No. 5, May 1984, pp. 157-167. Google ScholarDigital Library
Index Terms
- A generational on-the-fly garbage collector for Java
Recommendations
Implementing an on-the-fly garbage collector for Java
Java uses garbage collection (GC) for the automatic reclamation of computer memory no longer required by a running application. GC implementations for Java Virtual Machines (JVM) are typically designed for single processor machines, and do not ...
A generational on-the-fly garbage collector for Java
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 ...
Implementing an on-the-fly garbage collector for Java
ISMM '00: Proceedings of the 2nd international symposium on Memory managementJava uses garbage collection (GC) for the automatic reclamation of computer memory no longer required by a running application. GC implementations for Java Virtual Machines (JVM) are typically designed for single processor machines, and do not ...
Comments