Portable, mostly-concurrent, mostly-copying garbage collection for multi-processors

ABSTRACT

Modern commodity platforms increasingly support thread-level parallelism, which must be exploited by garbage collected applications. We describe the design and implementation of a portable mostly-concurrent mostly-copying garbage collector that exhibits scalable performance on multi-processors. We characterize its performance for heap-intensive workloads on two different multi-processor platforms, showing maximum pause times two orders of magnitude shorter than for fully stop-the-world collection at the cost of some total mutator throughput.

REFERENCES

• 1: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, ACM SIGPLAN Notices, v.23 n.7, p.11-20, July 1988
• 2: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, ACM SIGPLAN Notices, v.26 n.4, p.96-107, Apr. 1991
• 3: Hezi Azatchi , Yossi Levanoni , Harel Paz , Erez Petrank, An on-the-fly mark and sweep garbage collector based on sliding views, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 4: 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
• 5: David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, ACM SIGPLAN Notices, v.38 n.1, p.285-298, January 2003
• 6: 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]
• 7: Katherine Barabash , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Yoav Ossia , Avi Owshanko , Erez Petrank, A parallel, incremental, mostly concurrent garbage collector for servers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1097-1146, November 2005 [doi>10.1145/1108970.1108972]
• 8: BARTLETT, J. F. Compacting garbage collection with ambiguous roots. Research Report 88/2, Western Research Laboratory, Digital Equipment Corporation, Feb. 1988.
• 9: BARTLETT, J. F. Mostly-copying garbage collection picks up generations and C++. Technical Note TN-12, Western Research Laboratory, Digital Equipment Corporation, Oct. 1989.
• 10: Stephen M Blackburn , Kathryn S. McKinley, In or out?: putting write barriers in their place, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
• 11: Stephen M. Blackburn , Antony L. Hosking, Barriers: friend or foe?, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029891]
• 12: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
• 13: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 14: CARDELLI, L., DONAHUE, J., GLASSMAN, L., JORDAN, M., KALSOW, B., AND NELSON, G. Modula-3 language definition. In Systems Programming with Modula-3, G. Nelson, Ed. Prentice Hall, 1991, ch. 2, pp. 11--66.
• 15: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 16: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
• 17: DETLEFS, D. L. Concurrent garbage collection in C++. Tech. Rep. CMU-CS-90-119, Carnegie Mellon University, Mar. 1990.
• 18: DETREVILLE, J. Experience with concurrent garbage collectors for Modula-2+. Tech. Rep. 64, Systems Research Center, Digital Equipment Corporation, Palo Alto, CA, Aug. 1990.
• 19: 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]
• 20: Amer Diwan , Eliot Moss , Richard Hudson, Compiler support for garbage collection in a statically typed language, ACM SIGPLAN Notices, v.27 n.7, p.273-282, July 1992
• 21: 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]
• 22: 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]
• 23: 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
• 24: Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, ACM SIGPLAN Notices, v.35 n.5, p.274-284, May 2000
• 25: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 26: FLOOD, C. H., DETLEFS, D., SHAVIT, N., AND ZHANG, X. Parallel garbage collection for shared memory multiprocessors. In Proceedings of the Java Virtual Machine Research and Technology Symposium (Monterey, California, Apr.). USENIX, 2001.
• 27: Christopher W. Fraser , David R. Hanson , Todd A. Proebsting, Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.213-226, Sept. 1992 [doi>10.1145/151640.151642]
• 28: Antony L. Hosking , J. Eliot B. Moss, Protection traps and alternatives for memory management of an object-oriented language, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.106-119, December 05-08, 1993, Asheville, North Carolina, United States
• 29: 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
• 30: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• 31: HUDSON, R. L., AND MOSS, J. E. B. Sapphire: copying garbage collection without stopping the world. Concurrency and Computation--Practice and Experience 15, 3 (March 2003), 223--261.
• 32: Proceedings of the ACM International Symposium on Memory Management (Minneapolis, Minnesota, Oct., 2000). ACM SIGPLAN Notices 36, 1 (Jan. 2001).
• 33: Proceedings of the ACM International Symposium on Memory Management (Vancouver, Canada, Oct., 1998). ACM SIGPLAN Notices 34, 3 (Mar. 1999).
• 34: Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, ACM SIGPLAN Notices, v.36 n.11, p.367-380, 11/01/2001
• 35: 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]
• 36: 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]
• 37: Scott Nettles , James O'Toole, Real-time replication garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.217-226, June 1993
• 38: Pekka P. Pirinen, Barrier techniques for incremental tracing, Proceedings of the 1st international symposium on Memory management, p.20-25, October 17-19, 1998, Vancouver, British Columbia, Canada
• 39: Proceedings of the ACM Conference on Programming Language Design and Implementation (Snowbird, Utah, June). ACM SIGPLAN Notices 36, 5 (May 2001).
• 40: Tony Printezis , David Detlefs, A generational mostly-concurrent garbage collector, Proceedings of the 2nd international symposium on Memory management, p.143-154, October 15-16, 2000, Minneapolis, Minnesota, United States
• 41: Frederick Smith , Greg Morrisett, Comparing mostly-copying and mark-sweep conservative collection, Proceedings of the 1st international symposium on Memory management, p.68-78, October 17-19, 1998, Vancouver, British Columbia, Canada
• 42: SOBALVARRO, P. G. A lifetime-based garbage collector for LISP systems on general-purpose computers, 1988. B.S. Thesis, Dept. of EECS, Massachusetts Institute of Technology, Cambridge.
• 43: Daniel Spoonhower , Guy Blelloch , Robert Harper, Using page residency to balance tradeoffs in tracing garbage collection, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064989]
• 44: 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]
• 45: 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]
• 46: 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.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments; Compilers; Memory management (garbage collection)

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance

Keywords:
ambiguous-roots, concurrent, conservative, garbage collection, incremental, memory management, mostly-concurrent, mostly-copying, portability