An on-the-fly mark and sweep garbage collector based on sliding views

ABSTRACT

With concurrent and garbage collected languages like Java and C# becoming popular, the need for a suitable non-intrusive, efficient, and concurrent multiprocessor garbage collector has become acute. We propose a novel mark and sweep on-the-fly algorithm based on the sliding views mechanism of Levanoni and Petrank. We have implemented our collector on the Jikes Java Virtual Machine running on a Netfinity multiprocessor and compared it to the concurrent algorithm and to the stop-the-world collector supplied with Jikes JVM. The maximum pause time that we measured with our benchmarks over all runs was 2ms. In all runs, the pause times were smaller than those of the stop-the-world collector by two orders of magnitude and they were also always shorter than the pauses of the Jikes concurrent collector. Throughput measurements of the new garbage collector show that it outperforms the Jikes concurrent collector by up to 60%. As expected, the stop-the-world does better than the on-the-fly collectors with results showing about 10% difference.On top of being an effective mark and sweep on-the-fly collector standing on its own, our collector may also be used as a backup collector (collecting cyclic data structures) for the Levanoni-Petrank reference counting collector. These two algorithms perfectly fit sharing the same allocator, a similar data structure, and a similar JVM interface.

REFERENCES

• 1: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 2: David F. Bacon , Clement R. Attanasio , Han B. Lee , V. T. Rajan , Stephen Smith, Java without the coffee breaks: a nonintrusive multiprocessor garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.92-103, June 2001, Snowbird, Utah, United States
• 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: J. DeTreville. Experience with Concurrent Garbage Collector for Mudula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, November 1990.
• 6: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.157-164, June 24-28, 1991, Toronto, Ontario, Canada
• 7: Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, Proceedings of the 1st international symposium on Memory management, p.37-48, October 17-19, 1998, Vancouver, British Columbia, Canada
• 8: Sylvia Dieckmann , Urs Hölzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmark, Proceedings of the 13th European Conference on Object-Oriented Programming, p.92-115, June 14-18, 1999
• 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: 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
• 13: Tamar Domani , Elliot K. Kolodner , Ethan Lewis , Eliot E. Salant , Katherine Barabash , Itai Lahan , Yossi Levanoni , Erez Petrank , Igor Yanorer, Implementing an on-the-fly garbage collector for Java, Proceedings of the 2nd international symposium on Memory management, p.155-166, October 15-16, 2000, Minneapolis, Minnesota, United States
• 14: Shinichi Furusou, Satoshi Matsuoka, and Akinori Yonezawa. Parallel conservative garbage collection with fast allocation. In Paul~R. Wilson and Barry Hayes, editors, OOPSLA/ECOOP '91 Workshop on Garbage Collection in Object-Oriented Systems, 1991.
• 15: 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]
• 16: 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]
• 17: Richard L. Hudson , J. Eliot B. Moss, Sapphire: copying GC without stopping the world, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.48-57, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376810]
• 18: 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
• 19: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 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: Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.367-380, October 14-18, 2001, Tampa Bay, FL, USA
• 23: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 24: Yoav Ossia , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Avi Owshanko, A parallel, incremental and concurrent GC for servers, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 25: James O'Toole , Scott Nettles, Concurrent replicating garbage collection, Proceedings of the 1994 ACM conference on LISP and functional programming, p.34-42, June 27-29, 1994, Orlando, Florida, United States
• 26: Tony Printezis , David Detlefs, A generational mostly-concurrent garbage collector, ACM SIGPLAN Notices, v.36 n.1, p.143-154, Jan 2001
• 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. Corrigendum: Multiprocessing compactifying garbage collection. Communications of the ACM, 19(6):354, June 1976.
• 29: Standard Performance Evaluation Corporation, http://www.spec.org/
• 30: Paul R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas, January 1994. Expanded version of the IWMM92 paper.
• 31: T. Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990 [doi>10.1016/0164-1212(90)90084-Y]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Algorithms, Languages

Keywords:
concurrent garbage collection, garbage collection, memory management, on-the-fly garbage collection, runtime systems