A parallel, incremental, mostly concurrent garbage collector for servers

ABSTRACT

Multithreaded applications with multigigabyte heaps running on modern servers provide new challenges for garbage collection (GC). The challenges for “server-oriented” GC include: ensuring short pause times on a multigigabyte heap while minimizing throughput penalty, good scaling on multiprocessor hardware, and keeping the number of expensive multicycle fence instructions required by weak ordering to a minimum.We designed and implemented a collector facing these demands building on the mostly concurrent garbage collector proposed by Boehm et al. [1991]. Our collector incorporates new ideas into the original collector. We make it parallel and incremental; we employ concurrent low-priority background GC threads to take advantage of processor idle time; we propose novel algorithmic improvements to the basic mostly concurrent algorithm improving its efficiency and shortening its pause times; and finally, we use advanced techniques, such as a low-overhead work packet mechanism to enable full parallelism among the incremental and concurrent collecting threads and ensure load balancing.We compared the new collector to the mature, well-optimized, parallel, stop-the-world mark-sweep collector already in the IBM JVM. When allowed to run aggressively, using 72% of the CPU utilization during a short concurrent phase, our collector prototype reduces the maximum pause time from 161 ms to 46 ms while only losing 11.5% throughput when running the SPECjbb2000 benchmark on a 600-MB heap on an 8-way PowerPC 1.1-GHz processors. When the collector is limited to a nonintrusive operation using only 29% of the CPU utilization, the maximum pause time obtained is 79 ms and the loss in throughput is 15.4%.

REFERENCES

• 1: Adve, S. V. and Gharachorloo, K. 1995. Shared memory consistency models: A tutorial. Res. Rep. 95/7. Western Research Laboratory, Palo Alto, CA, Sept.
• 2: Azagury, A., Kolodner, E. K., and Petrank, E. 1999. A note on the implementation of replication-based garbage collection for multithreaded applications and multiprocessor environments. Paral. Proc. Lett.
• 3: 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
• 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 , Ravi Konuru , Chet Murthy , Mauricio Serrano, Thin locks: featherweight synchronization for Java, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.258-268, June 17-19, 1998, Montreal, Quebec, Canada
• 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: Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Kean Kuiper , Victor Leikehman, An algorithm for parallel incremental compaction, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 8: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
• 9: Borman, S. 2002. Sensible sanitation - understanding the ibm java garbage collector (Part 1: Object allocation). http://www.ibm.com/developerworks/ibm/library/i-garbage1.
• 10: 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
• 11: Corella, F., Stone, J., and Barton, C. 1993. Specification of the PowerPC shared memory architecture. Tech. Rep. 18638, IBM Thomas J. Watson Research Center. Jan.
• 12: DeTreville, J. 1990. Experience with concurrent garbage collectors for Modula-2+. Tech. Rep. 64, DEC Systems Research Center, Palo Alto, CA. Aug.
• 13: Dijkstra, E. W., Lamport, L., Martin, A. J., Scholten, C. S., and Steffens, E. F. M. 1976. On-the-fly garbage collection: An exercise in cooperation. In Lecture Notes in Computer Science, vol. 46. Springer-Verlag, New York.
• 14: 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]
• 15: R. Dimpsey , R. Arora , K. Kuiper, Java server performance: a case study of building efficient, scalable Jvms, IBM Systems Journal, v.39 n.1, p.151-174, January 2000
• 16: 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]
• 17: 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]
• 18: 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
• 19: 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
• 20: 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]
• 21: Toshio Endo , Kenjiro Taura, Reducing pause time of conservative collectors, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 22: Flood, C., Detlefs, D., Shavit, N., and Zhang, C. 2001. Parallel garbage collection for shared memory multiprocessors. In Proceedings of the Usenix Java Virtual Machine Research and Technology Symposium (JVM '01) (Monterey, CA).
• 23: Hosking, T., Ed. 2000. ISMM 2000 Proceedings of the Second International Symposium on Memory Management. ACM SIGPLAN Notices, vol. 36(1). ACM Press, Minneapolis, MN.
• 24: 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
• 25: 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]
• 26: IBM 2000. Z/Architecture Principles of Operation (SA22-7832-01). Appendix A. Available at www.ibm.com.
• 27: Intel 1999. IA-64 Application Developer's Architecture Guide. Available at http://developer.intel.com/design/itanium.
• 28: Intel Software Network, Software Products. 2005. Intel Vtune Performance Analyzers. http://www.intel.com/cd/software/products/asmona/eng/vtune/index.htm.
• 29: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 30: B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, Papers of the Symposium on Interpreters and interpretive techniques, p.253-263, June 24-26, 1987, St. Paul, Minnesota, United States
• 31: 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
• 32: 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]
• 33: 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]
• 34: Scott Nettles , James O'Toole, Real-time replication garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.217-226, June 21-25, 1993, Albuquerque, New Mexico, United States
• 35: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 36: 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
• 37: Patrick Sobalvarro, A Lifetime-based Garbage Collector for LISP Systems on General- Purpose Computers, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 38: SPECjbb2000 1998. SPECjbb2000 Java Business Benchmark. Standard Performance Evaluation Corporation (SPEC), Fairfax, VA. Available at http://www.spec.org/osg/jbb2000/.
• 39: SPECJVM98 1998. SPECjvm98 Benchmarks. Standard Performance Evaluation Corporation (SPEC), Fairfax, VA. Available at http://www.spec.org/osg/jvm98/.
• 40: 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]
• 41: 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]
• 42: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 43: Toshio Suganuma , Toshiaki Yasue , Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, A dynamic optimization framework for a Java just-in-time compiler, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.180-195, October 14-18, 2001, Tampa Bay, FL, USA
• 44: SUN 2003. JSRs: Java Specification Requests. JSR 133: Java Memory Model and Thread Specification Revision. Available at hhttp://jcp.org/jsr/detail/133.jsp.
• 45: Thomas, S., Charnell, W., Darnell, S., Dias, B. A. A., Kramskoy, J. G. P., Sexton, J., Wynn, J., Rautenbach, K., and Plummer W. 1998. Lowconnection grey object sets for concurrent, marking garbage collection. United States Patent Application, 20020042807.
• 46: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 47: Alex Garthwaite , Derek White, The GC Interface in the EVM¹, Sun Microsystems, Inc., Mountain View, CA, 1998

INDEX TERMS

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

General Terms:
Algorithms, Languages, Performance

Keywords:
Garbage collection, JVM, concurrent garbage collection