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%.
- Adve, S. V. and Gharachorloo, K. 1995. Shared memory consistency models: A tutorial. Res. Rep. 95/7. Western Research Laboratory, Palo Alto, CA, Sept.Google Scholar
- 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.Google ScholarCross Ref
- Azatchi, H., Levanoni, Y., Paz, H., and Petrank, E. 2003. An on-the-fly mark and sweep garbage collector based on sliding view. In Proceedings of the ACM Conference Object-Oriented Systems, Languages and Applications (OOPSLA'03) (Anaheim, CA). ACM, New York. Google ScholarDigital Library
- Bacon, D. F., Attanasio, C. R., Lee, H. B., Rajan, V. T., and Smith, S. 2001. Java without the coffee breaks: A nonintrusive multiprocessor garbage collector. In Proceedings of SIGPLAN 2001 Conference on Programming Languages Design and Implementation (Snowbird, UT). ACM SIGPLAN Notices. ACM, New York. Google ScholarDigital Library
- Bacon, D. F., Konuru, R., Murthy, C., and Serrano, M. 1998. Thin locks: Featherweight synchronization for Java. In Proceedings of SIGPLAN'98 Conference on Programming Languages Design and Implementation. (Montreal, Que., Canada). ACM SIGPLAN Notices. ACM, New York, 258--268. Google ScholarDigital Library
- Baker, H. G. 1978. List processing in real-time on a serial computer. Commun. ACM 21, 4, 280--294. (Also AI Laboratory Working Paper 139, 1977.) Google ScholarDigital Library
- Ben-Yitzhak, O., Goft, I., Kolodner, E., Kuiper, K., and Leikehman, V. 2002. An algorithm for parallel incremental compaction. In Proceedings of the 3rd International Symposium on Memory Management (ISMM'02) (Berlin, Germany), ACM SIGPLAN Notices. D. Detlefs, Ed. ACM, New York, 100--105. Google ScholarDigital Library
- Boehm, H.-J., Demers, A. J., and Shenker, S. 1991. Mostly parallel garbage collection. ACM SIGPLAN Notices 26, 6, 157--164. Google ScholarDigital Library
- Borman, S. 2002. Sensible sanitation - understanding the ibm java garbage collector (Part 1: Object allocation). http://www.ibm.com/developerworks/ibm/library/i-garbage1.Google Scholar
- Cheng, P. and Belloch, G. 2001. A parallel, real-time garbage collector. In Proceedings of the Conference on Programming Languages Design and Implementation (SIGPLAN 2001) (Snowbird, UT). ACM SIGPLAN Notices. ACM, New York, 125--136. Google ScholarDigital Library
- 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.Google Scholar
- DeTreville, J. 1990. Experience with concurrent garbage collectors for Modula-2+. Tech. Rep. 64, DEC Systems Research Center, Palo Alto, CA. Aug.Google Scholar
- 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.Google Scholar
- Dijkstra, E. W., Lamport, L., Martin, A. J., Scholten, C. S., and Steffens, E. F. M. 1978. On-the-fly garbage collection: An exercise in cooperation. Commun. ACM 21, 11 (Nov.), 965--975. Google ScholarDigital Library
- Dimpsey, R., Arora, R., and Kuiper, K. 2000. Java server performance: A case study of building efficient, scalable JVMs. IBM Syst. J. 39, 1, 151--174. Google ScholarDigital Library
- Doligez, D. and Gonthier, G. 1994. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the 21st Annual ACM Symposium on Principles of Programming Languages. ACM SIGPLAN Notices. ACM, New York. Google ScholarDigital Library
- Doligez, D. and Leroy, X. 1993. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Conference Record of the 20th Annual ACM Symposium on Principles of Programming Languages. ACM SIGPLAN Notices. ACM, New York, 113-- 123. Google ScholarDigital Library
- Domani, T., Kolodner, E., and Petrank, E. 2000a. A generational on-the-fly garbage collector for Java. In Proceedings of SIGPLAN 2000 Conference on Programming Languages Design and Implementation (Vancouver, B.C., Canada). ACM SIGPLAN Notices. ACM, New York. Google ScholarDigital Library
- Domani, T., Kolodner, E. K., Lewis, E., Salant, E. E., Barabash, K., Lahan, I., Petrank, E., Yanover, I., and Levanoni, Y. 2000b. Implementing an on-the-fly garbage collector for Java. In Proceedings of the 2nd International Symposium on Memory Management (ISMM 2000) (Minneapolis, MN). ACM SIGPLAN Notices 3b, 1, T. HOSKIN, Ed. ACM, New York. Google ScholarDigital Library
- Endo, T., Taura, K., and Yonezawa, A. 1997. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Proceedings of High Performance Computing and Networking (SC'97). Google ScholarDigital Library
- Endo, T., Taura, K., and Yonezawa, A. 2002. Reducing pause time of conservative collectors. In Proceedings of the 3rd International Symposium on Memory Management (ISMM'02) (Berlin, Germany), ACM SIGPLAN Notices. D. Detlefs, Ed. ACM, New York, 12--24. Google ScholarDigital Library
- 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). Google ScholarDigital Library
- 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.Google Scholar
- Hudson, R. L. and Moss, J. E. B. 1992. Incremental garbage collection for mature objects. In Proceedings of International Workshop on Memory Management, Y. Bekkers and J. Cohen, Eds. Lecture Notes in Computer Science, vol. 637. Springer-Verlag, New York. Google ScholarDigital Library
- Hudson, R. L. and Moss, J. E. B. 2001. Sapphire: Copying GC without stopping the world. In ISCOPE Conference on ACM 2001 Java Grande. (Palo Alto, CA). ACM, New York, 48--57. Google ScholarDigital Library
- IBM 2000. Z/Architecture Principles of Operation (SA22-7832-01). Appendix A. Available at www.ibm.com.Google Scholar
- Intel 1999. IA-64 Application Developer's Architecture Guide. Available at http://developer.intel.com/design/itanium.Google Scholar
- Intel Software Network, Software Products. 2005. Intel Vtune Performance Analyzers. http://www.intel.com/cd/software/products/asmona/eng/vtune/index.htm.Google Scholar
- Jones, R. E. 1996. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, New York. (With a chapter on Distributed Garbage Collection by R. Lins.) Google ScholarDigital Library
- Lang, B., and Dupont, F. 1987. Incremental incrementally compacting garbage collection. In Proceedings of the Symposium on Interpreters and Interpretive Techniques. (SIGPLAN'87) ACM SIGPLAN Notices, 22(7). ACM, New York, 253--263. Google ScholarDigital Library
- Levanoni, Y. and Petrank, E. 2001. An on-the-fly reference counting garbage collector for Java. In Proceedings of the ACM Conference on Object Oriented Systems, Languages and Applications (OOPSLA'01) (Tampa, FL). ACM SIGPLAN Notices 3b, 10, ACM, New York. Google ScholarDigital Library
- Lieberman, H. and Hewitt, C. E. 1983. A real-time garbage collector based on the lifetimes of objects. Commun. ACM 26(6), 419--429. (Also report TM--184, Laboratory for Computer Science, MIT, Cambridge, MA, July 1980 and AI Lab Memo 569, 1981.) Google ScholarDigital Library
- Moon, D. A. 1984. Garbage collection in a large LISP system. In Conference Record of the 1984 ACM Symposium on LISP and Functional Programming (Austin, TX), G. L. Steele, Ed. ACM, New York, 235--245. Google ScholarDigital Library
- Nettles, S. M. and O'Toole, J. W. 1993. Real-time replication-based garbage collection. In Proceedings of SIGPLAN'93 Conference on Programming Languages Design and Implementation. ACM SIGPLAN Notices, 28(6). ACM, New York. Google ScholarDigital Library
- Patterson, D. and Hennessy, J. 1990. Computer architecture: A quantitative approach. Morgan-Kaufman, Reading, MA. Google ScholarDigital Library
- Printezis, T. and Detlefs, D. 2000. A generational mostly-concurrent garbage collector. In Proceedings of the 2nd International Symposium on Memory Management (ISMM 2000) (Minheapolis, MN). ACM SIGPLAN Notices 3b, 1, T. Hosking, Ed. ACM, New York. Google ScholarDigital Library
- Sobalvarro, P. 1988. A lifetime-based garbage collector for LISP systems on general-purpose computers. Tech. Rep. AITR-1417, MIT AI Lab. Feb. Bachelor of Science thesis. Google ScholarDigital Library
- SPECjbb2000 1998. SPECjbb2000 Java Business Benchmark. Standard Performance Evaluation Corporation (SPEC), Fairfax, VA. Available at http://www.spec.org/osg/jbb2000/.Google Scholar
- SPECJVM98 1998. SPECjvm98 Benchmarks. Standard Performance Evaluation Corporation (SPEC), Fairfax, VA. Available at http://www.spec.org/osg/jvm98/.Google Scholar
- Steele, G. L. 1975. Multiprocessing compactifying garbage collection. Commun. ACM 18, 9 (Sept.), 495--508. Google ScholarDigital Library
- Steele, G. L. 1976. Corrigendum: Multiprocessing compactifying garbage collection. Commun. ACM 19, 6 (June), 354. Google ScholarDigital Library
- Suganuma, T., Ogasawara, T., Takeuchi, M., Kawahito, T. Y. M., Ishizaki, K., Komatsu, H., and Nakatani, T. 2000. Overview of the IBM Java just-in-time compiler. IBM Syst. J. 29, 1 (Feb.). Google ScholarDigital Library
- Suganuma, T., Yasue, T., Kawahito, M., Komatsu, H., and Nakatani, T. 2001. A dynamic optimization framework for a Java Just-In-Time compiler. In Proceedings of the ACM Conference on Object Oriented Systems, Languages and Applications (OOPSLA'01) (Tampa, FL). ACM SIGPLAN Notices 3b, 10, ACM, New York. 180--194. Google ScholarDigital Library
- SUN 2003. JSRs: Java Specification Requests. JSR 133: Java Memory Model and Thread Specification Revision. Available at hhttp://jcp.org/jsr/detail/133.jsp.Google Scholar
- 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.Google Scholar
- Ungar, D. M. 1984 Generation scavenging: A non-disruptive high performance storage reclamation algorithm. ACM SIGPLAN Notices 19, 5 (Apr.), 157--167. (Also published as ACM Software Engineering Notes 9, 3 (May 1984)---Proceedings of the ACM/SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, 157--167, April 1984.) Google ScholarDigital Library
- White, D. and Garthwaite, A. 1998. The GC interface in the EVM. Tech. Rep. SML TR--98--67, Sun Microsystems Laboratories. Dec. Google ScholarDigital Library
Index Terms
- A parallel, incremental, mostly concurrent garbage collector for servers
Recommendations
A parallel, incremental and concurrent GC for servers
PLDI '02: Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementationMultithreaded applications with multi-gigabyte 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 multi-gigabyte heap, while minimizing ...
A parallel, incremental and concurrent GC for servers
Multithreaded applications with multi-gigabyte 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 multi-gigabyte heap, while minimizing ...
Mostly concurrent garbage collection revisited
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applicationsThe mostly concurrent garbage collection was presented in the seminal paper of Boehm et al. With the deployment of Java as a portable, secure and concurrent programming language, the mostly concurrent garbage collector turned out to be an excellent ...
Comments