An on-the-fly reference-counting garbage collector for java

ABSTRACT

Reference-counting is traditionally considered unsuitable for multiprocessor systems. According to conventional wisdom, the update of reference slots and reference-counts requires atomic or synchronized operations. In this work we demonstrate this is not the case by presenting a novel reference-counting algorithm suitable for a multiprocessor system that does not require any synchronized operation in its write barrier (not even a compare-and-swap type of synchronization). A second novelty of this algorithm is that it allows eliminating a large fraction of the reference-count updates, thus, drastically reducing the reference-counting traditional overhead. This article includes a full proof of the algorithm showing that it is safe (does not reclaim live objects) and live (eventually reclaims all unreachable objects).We have implemented our algorithm on Sun Microsystems' Java Virtual Machine (JVM) 1.2.2 and ran it on a four-way IBM Netfinity 8500R server with 550-MHz Intel Pentium III Xeon and 2 GB of physical memory. Our results show that the algorithm has an extremely low latency and throughput that is comparable to the stop-the-world mark and sweep algorithm used in the original JVM.

REFERENCES

• 1: Alfred V. Aho , Brian W. Kernighan , Peter J. Weinberger, The AWK programming language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 2: 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
• 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: Azatchi, H. and Petrank, E. 2003. Integrating generations with advanced reference counting garbage collectors. In International Conference on Compiler Construction (CC'2003). Lecture Notes in Computer Science, vol. 2622. Springer, Berlin, Germany, 185--199.
• 5: 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
• 6: David F. Bacon , V. T. Rajan, Concurrent Cycle Collection in Reference Counted Systems, Proceedings of the 15th European Conference on Object-Oriented Programming, p.207-235, June 18-22, 2001
• 7: 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]
• 8: Henry G. Baker, Minimizing reference count updating with deferred and anchored pointers for functional data structures, ACM SIGPLAN Notices, v.29 n.9, p.38-43, Sept. 1994 [doi>10.1145/185009.185016]
• 9: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• 10: Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 11: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
• 12: Chikayama, T. and Kimura, Y. 1987. Multiple reference management in Flat GHC. In 4th International Conference on Logic Programming. MIT Press, Cambridge, MA, 276--293.
• 13: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 14: J. Crammond, A garbage collection algorithm for shared memory parallel processors, International Journal of Parallel Programming, v.17 n.6, p.497-522, Dec. 1989 [doi>10.1007/BF01407816]
• 15: DeTreville, J. 1990. Experience with concurrent garbage collectors for Modula-2+. Tech. rep. 64. DEC Systems Research Center, Palo Alto, CA.
• 16: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 17: 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]
• 18: 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]
• 19: 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]
• 20: Domani, T., Kolodner, E. K., Lewis, E., Salant, E. E., Barabash, K., Lahan, I., Petrank, E., Yanover, I., and Levanoni, Y. 2000. Implementing an on-the-fly garbage collector for Java. See Hosking {2000}, 155--166.
• 21: 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]
• 22: Flood, C., Detlefs, D., Shavit, N., and Zhang, C. 2001. Parallel garbage collection for shared memory multiprocessors. In USENIX Java Virtual Machine Research and Technology Symposium (JVM '01, Monterey, CA). USENIX, Berkeley, CA.
• 23: Paul R. Wilson , Barry Hayes, Garbage collection in object oriented systems, Addendum to the proceedings on Object-oriented programming systems, languages, and applications (Addendum), p.63-71, October 06-11, 1991, Phoenix, Arizona, United States
• 24: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 25: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 26: Herlihy, M. and Moss, J. E. B. 1990. Non-blocking garbage collection for multiprocessors. Tech. rep. CRL 90/9. DEC Cambridge Research Laboratory, Cambridge, MA.
• 27: Antony L. Hosking , J. Eliot B. Moss , Darko Stefanovic, A comparative performance evaluation of write barrier implementation, conference proceedings on Object-oriented programming systems, languages, and applications, p.92-109, October 18-22, 1992, Vancouver, British Columbia, Canada
• 28: Hosking, T., Ed. 2000. ISMM 2000 Proceedings of the Second International Symposium on Memory Management. ACM Press, New York, NY.
• 29: Hudson, R. L. and Moss, J. E. B. 2003. Copying garbage collection without stopping the world. Concurr. Computat.: Pract. Exp. 15, 3--5, 223--261.
• 30: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 31: Kolodner, E. K. and Petrank, E. 2004. Parallel copying garbage collection using delayed allocation. Parall. Process. Lett. 14, 2. To appear.
• 32: 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
• 33: Lins, R. D. and Vasques, M. A. 1991. A comparative study of algorithms for cyclic reference counting. Tech. rep. 92. Computing Laboratory, The University of Kent at Canterbury. Canterbury, U.K.
• 34: J. Harold McBeth, Letters to the editor: on the reference counter method, Communications of the ACM, v.6 n.9, p.575, Sept. 1963 [doi>10.1145/367593.367649]
• 35: James S. Miller , Barbara S. Epstein, Garbage Collection in MultiScheme, Proceedings of the US/Japan Workshop on Parallel Lisp: Languages and Systems, p.138-160, June 05-08, 1989
• 36: OOPSLA. 2003. Proceedings of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM Press, New York, NY.
• 37: 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
• 38: 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
• 39: Young Park , Benjamin Goldberg, Static analysis for optimizing reference counting, Information Processing Letters, v.55 n.4, p.229-234, Aug. 25, 1995 [doi>10.1016/0020-0190(95)00096-U]
• 40: Plakal, M. and Fischer, C. N. 2000. Concurrent garbage collection using program slices on multithreaded processors. See Hosking {2000}, 94--100.
• 41: Printezis, T. and Detlefs, D. 2000. A generational mostly-concurrent garbage collector. See Hosking {2000}, 143--154.
• 42: D. Touitou, Towards a practical snapshot algorithm, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.121, January 04-06, 1995
• 43: David J. Roth , David S. Wise, One-bit counts between unique and sticky, ACM SIGPLAN Notices, v.34 n.3, p.49-56, March 1999
• 44: Patrick Sobalvarro, A Lifetime-based Garbage Collector for LISP Systems on General- Purpose Computers, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 45: SPEC Benchmarks. 2000. Standard Performance Evaluation Corporation. Available online at http://www.spec.org/.
• 46: 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]
• 47: W. R. Stoye , T. J. W. Clarke , A. C. Norman, Some practical methods for rapid combinator reduction, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.159-166, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802032]
• 48: Larry Wall , Randal L. Schwartz, Programming perl, O'Reilly & Associates, Inc., Sebastopol, CA, 1991
• 49: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 50: David S. Wise, Stop-and-copy and one-bit reference counting, Information Processing Letters, v.46 n.5, p.243-249, July 9, 1993 [doi>10.1016/0020-0190(93)90103-G]
• 51: 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]
• 52: Zorn, B. 1990. Barrier methods for garbage collection. Tech. rep. CU-CS-494-90. University of Colorado, Boulder, CO.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management
      D.3.4 Processors
          Subjects: Memory management (garbage collection)
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Algorithms, Languages

Keywords:
Programming languages, garbage collection, memory management, reference-counting