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

ABSTRACT

Reference counting is not naturally suitable for running on multiprocessors. The update of pointers and reference counts requires atomic and synchronized operations. We present a novel reference counting algorithm suitable for a multiprocessor that does not require any synchronized operation in its write barrier (not even a compare-and-swap type of synchronization). The algorithm is efficient and may complete with any tracing algorithm.

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: 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
• 3: 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
• 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 , 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
• 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: 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]
• 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: T. Chikayama and Y. Kimura. Multiple reference management in Flat GHC. ICLP, pages 276-293, 1987.
• 10: 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
• 11: 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]
• 12: 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]
• 13: John DeTreville. Experience with concurrent garbage collectors for Modula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, August 1990.
• 14: John DeTreville. Experience with garbage collection for modula-2+ in the topaz environment. In OOPSLA/ECOOP '90 Workshop on Garbage Collection in Object-Oriented Systems, October 1990.
• 15: 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]
• 16: 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
• 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: 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
• 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: 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.
• 23: Adele Goldberg , David Robson, Smalltalk-80: the language and its implementation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 24: Atsuhiro Goto, Y. Kimura, T. Nakagawa, and T. Chikayama. Lazy reference counting: An incremental garbage collection method for parallel inference machines. ICLP, pages 1241-1256, 1988.
• 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: Maurice Herlihy and J. Eliot B Moss. Non-blocking garbage collection for multiprocessors. Technical Report CRL 90/9, DEC Cambridge Research Laboratory, 1990.
• 27: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 28: Elliot K. Kolodner and Erez Petrank. Parallel copying garbage collection using delayed allocation. Technical Report 88.384, IBM Haifa Research Lab, November 1999. Available at http://www.cs.princeton.edu/ erez/publications.html.
• 29: Yossi Levanoni and Erez Petrank. A scalable reference counting garbage collector. Technical Report CS0967, Technion, Israel Institute of Technology, November 1999. Available at http://www.cs.technion.ac.il/ erez/publications.html.
• 30: J. S. Miller , B. S. Epstein, Garbage collection in MultiScheme, Proceedings of the US/Japan workshop on Parallel Lisp on Parallel Lisp: languages and systems, p.138-160, June 1990, Sendai, Japan
• 31: 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
• 32: 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]
• 33: Manoj Plakal , Charles N. Fischer, Concurrent garbage collection using program slices on multithreaded processors, Proceedings of the 2nd international symposium on Memory management, p.94-100, October 15-16, 2000, Minneapolis, Minnesota, United States
• 34: 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
• 35: David J. Roth , David S. Wise, One-bit counts between unique and sticky, Proceedings of the 1st international symposium on Memory management, p.49-56, October 17-19, 1998, Vancouver, British Columbia, Canada
• 36: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, On effectiveness of GC in Java, Proceedings of the 2nd international symposium on Memory management, p.12-17, October 15-16, 2000, Minneapolis, Minnesota, United States
• 37: 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]
• 38: Standard Performance Evaluation Corporation, http://www.spec.org/
• 39: 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]
• 40: Larry Wall , Randal L. Schwartz, Programming perl, O'Reilly & Associates, Inc., Sebastopol, CA, 1991
• 41: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 42: 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]
• 43: David S. Wise. Stop and one-bit reference counting. Technical Report 360, Indiana University, Computer Science Department, March 1993.
• 44: 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.2 Language Classifications
          Subjects: Applicative (functional) languages

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

General Terms:
Algorithms, Performance