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. 1 Alfred V. Aho, Brian W. Kernighan, and Peter J. Weinberger. The AWK Programming Language. Addison-Wesley, 1988.]]
2. 2 Y. Riany, N. Shavit, D. Touitou. Towards a Practical Snapshot Algorithm. Proceedings of the Third Israel Symposium on Theory and Computing Systems (ISTCS), Tel Aviv, (1995), 121-129.]]
3. 3 Andrew W. Appel, John R. Ellis, and Kai Li. Real-time concurrent collection on stock multiprocessors. ACM SIGPLAN Notices, 23(7):11-20, 1988.]]
4. 4 D. Bacon, C. Attanasio, H. Lee, V. Rajan, and S. Smith. Java without the coffee breaks: A nonintrusive multiprocessor garbage collector. To appear in the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Snowbird, Utah, June 20-22 2001.]]
5. 5 D. Bacon and V. Rajan. Concurrent Cycle Collection in Reference Counted Systems. To appear in the Fifteenth European Conference on Object-Oriented Programming (ECOOP), University E.otv. os Lorand, Budapest, Hungary, June 18-22 2001.]]
6. 6 Henry G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280-94, 1978.]]
7. 7 Henry G. Baker. Minimising reference count updating with deferred and anchored pointers for functional data structures. ACM SIGPLAN Notices, 29(9), September 1994.]]
8. 8 Hans-Juergen B.ohm, Alan J. Demers, and Scott Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6):157-164, 1991.]]
9. 9 T. Chikayama and Y. Kimura. Multiple reference management in Flat GHC. ICLP, pages 276-293, 1987.]]
10. 10 Trishul M. Chilimbi and James R. Larus. Using generational garbage collection to implement cache-conscious data placement. In Proceedings of the First International Symposium on Memory Management, volume 34(3) of ACM SIGPLAN Notices, October 1998, pages 37-48.]]
11. 11 George E. Collins. A method for overlapping and erasure of lists. Communications of the ACM, 3(12):655-657, December 1960.]]
12. 12 Jim Crammond. A garbage collection algorithm for shared memory parallel processors. International Journal Of Parallel Programming, 17(6):497-522, 1988.]]
13. 13 John DeTreville. Experience with concurrent garbage collectors for Modula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, August 1990.]]
14. 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. 15 L. Peter Deutsch and Daniel G. Bobrow. An efficient incremental automatic garbage collector. Communications of the ACM, 19(9):522-526, September 1976.]]
16. 16 Sylvia Dieckmann and Urs H.olzle. A Study of the Allocation Behavior of the SPECjvm98 Java Benchmarks. Proceedings of the European Conference on Object-Oriented Programming (ECOOP'99), Lecture Notes on Computer Science, Springer Verlag, June 1999.]]
17. 17 Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the- y garbage collection: An exercise in cooperation. Communications of the ACM, 21(11):965-975, November 1978.]]
18. 18 Damien Doligez and Georges Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In POPL 1994.]]
19. 19 Damien Doligez and Xavier Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In POPL 1993.]]
20. 20 Tamar Domani, Elliot K. Kolodner, Ethan Lewis, Elliot E. Salant, Katherine Barabash, Itai Lahan, Yossi Levanoni, Erez Petrank, and Igor Yanover. Implementing an On-the- y Garbage Collector for Java. The 2000 International Symposium on Memory Management, October, 2000.]]
21. 21 Toshio Endo, Kenjiro Taura, and Akinori Yonezawa. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Proceedings of High Performance Computing and Networking (SC'97), 1997.]]
22. 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. 23 Adele Goldberg and D. Robson. Smalltalk-80: The Language and its Implementation. Addison-Wesley, 1983.]]
24. 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. 25 Robert H. Halstead. Multilisp: A language for concurrent symbolic computation. ACM TOPLAS, 7(4):501-538, October 1985.]]
26. 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. 27 Richard E. Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996.]]
28. 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. 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. 30 James S. Miller and B. Epstein. Garbage collection in MultiScheme. In US/Japan Workshop on Parallel Lisp, LNCS 441, pages 138-160, June 1990.]]
31. 31 James W. O'Toole and Scott M. Nettles. Concurrent replicating garbage collection. Also LFP94 and OOPSLA93 Workshop on Memory Management and Garbage Collection.]]
32. 32 Young G. Park and Benjamin Goldberg. Static analysis for optimising reference counting. IPL, 55(4):229-234, August 1995.]]
33. 33 Manoj Plakal and Charles N. Fischer. Concurrent Garbage Collection Using Program Slices on Multithreaded Processors. ISMM 2000.]]
34. 34 Tony Printezis and David Detlefs. A generational mostly-concurrent garbage collector. ISMM 2000.]]
35. 35 David J. Roth and David S. Wise. One-bit counts between unique and sticky. ACM SIGPLAN Notices, pages 49-56, October 1998. ACM Press.]]
36. 36 Ran Shaham, Elliot K. Kolodner, and Mooly Sagiv. On the Effectiveness of GC in Java. The 2000 International Symposium on Memory Management (ISMM '00) 2000.]]
37. 37 Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18(9):495-508, September 1975.]]
38. 38 Standard Performance Evaluation Corporation, http://www.spec.org/]]
39. 39 Will R. Stoye, T. J. W. Clarke, and Arthur C. Norman. Some practical methods for rapid combinator reduction. In LFP, pages 159-166, August 1984.]]
40. 40 Larry Wall and Randal L. Schwartz. Programming Perl. O'Reilly and Associates, Inc., 1991.]]
41. 41 J. Weizenbaum. Symmetric list processor. Communications of the ACM, 6(9):524-544, September 1963.]]
42. 42 David S. Wise. Stop and one-bit reference counting. IPL, 46(5):243-249, July 1993.]]
43. 43 David S. Wise. Stop and one-bit reference counting. Technical Report 360, Indiana University, Computer Science Department, March 1993.]]
44. 44 Taichi Yuasa. Real-time garbage collection on general-purpose machines. Journal of Software and Systems, 11(3):181-198, 1990.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

        • Functional languages

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection