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.
- 1.Alfred V. Aho, Brian W. Kernighan, and Peter J. Weinberger. The AWK Programming Language. Addison-Wesley, 1988.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 6.Henry G. Baker. List processing in real-time on a serial computer. Communications of the ACM, 21(4):280-94, 1978.]] Google ScholarDigital Library
- 7.Henry G. Baker. Minimising reference count updating with deferred and anchored pointers for functional data structures. ACM SIGPLAN Notices, 29(9), September 1994.]] Google ScholarDigital Library
- 8.Hans-Juergen B.ohm, Alan J. Demers, and Scott Shenker. Mostly parallel garbage collection. ACM SIGPLAN Notices, 26(6):157-164, 1991.]] Google ScholarDigital Library
- 9.T. Chikayama and Y. Kimura. Multiple reference management in Flat GHC. ICLP, pages 276-293, 1987.]]Google Scholar
- 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.]] Google ScholarDigital Library
- 11.George E. Collins. A method for overlapping and erasure of lists. Communications of the ACM, 3(12):655-657, December 1960.]] Google ScholarDigital Library
- 12.Jim Crammond. A garbage collection algorithm for shared memory parallel processors. International Journal Of Parallel Programming, 17(6):497-522, 1988.]] Google ScholarDigital Library
- 13.John DeTreville. Experience with concurrent garbage collectors for Modula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, August 1990.]]Google Scholar
- 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.]]Google Scholar
- 15.L. Peter Deutsch and Daniel G. Bobrow. An efficient incremental automatic garbage collector. Communications of the ACM, 19(9):522-526, September 1976.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 18.Damien Doligez and Georges Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In POPL 1994.]] Google ScholarDigital Library
- 19.Damien Doligez and Xavier Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In POPL 1993.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 23.Adele Goldberg and D. Robson. Smalltalk-80: The Language and its Implementation. Addison-Wesley, 1983.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 25.Robert H. Halstead. Multilisp: A language for concurrent symbolic computation. ACM TOPLAS, 7(4):501-538, October 1985.]] Google ScholarDigital Library
- 26.Maurice Herlihy and J. Eliot B Moss. Non-blocking garbage collection for multiprocessors. Technical Report CRL 90/9, DEC Cambridge Research Laboratory, 1990.]]Google Scholar
- 27.Richard E. Jones and Rafael Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, July 1996.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google Scholar
- 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.]] Google ScholarDigital Library
- 31.James W. O'Toole and Scott M. Nettles. Concurrent replicating garbage collection. Also LFP94 and OOPSLA93 Workshop on Memory Management and Garbage Collection.]] Google ScholarDigital Library
- 32.Young G. Park and Benjamin Goldberg. Static analysis for optimising reference counting. IPL, 55(4):229-234, August 1995.]] Google ScholarDigital Library
- 33.Manoj Plakal and Charles N. Fischer. Concurrent Garbage Collection Using Program Slices on Multithreaded Processors. ISMM 2000.]] Google ScholarDigital Library
- 34.Tony Printezis and David Detlefs. A generational mostly-concurrent garbage collector. ISMM 2000.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 37.Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18(9):495-508, September 1975.]] Google ScholarDigital Library
- 38.Standard Performance Evaluation Corporation, http://www.spec.org/]]Google Scholar
- 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.]] Google ScholarDigital Library
- 40.Larry Wall and Randal L. Schwartz. Programming Perl. O'Reilly and Associates, Inc., 1991.]] Google ScholarDigital Library
- 41.J. Weizenbaum. Symmetric list processor. Communications of the ACM, 6(9):524-544, September 1963.]] Google ScholarDigital Library
- 42.David S. Wise. Stop and one-bit reference counting. IPL, 46(5):243-249, July 1993.]] Google ScholarDigital Library
- 43.David S. Wise. Stop and one-bit reference counting. Technical Report 360, Indiana University, Computer Science Department, March 1993.]]Google ScholarDigital Library
- 44.Taichi Yuasa. Real-time garbage collection on general-purpose machines. Journal of Software and Systems, 11(3):181-198, 1990.]] Google ScholarDigital Library
Index Terms
- An on-the-fly reference counting garbage collector for Java
Recommendations
Ulterior reference counting: fast garbage collection without a long wait
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applicationsGeneral purpose garbage collectors have yet to combine short pause times with high throughput. For example, generational collectors can achieve high throughput. They have modest average pause times, but occasionally collect the whole heap and ...
An on-the-fly reference-counting garbage collector for java
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 ...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementationAn on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Comments