An efficient on-the-fly cycle collection

ABSTRACT

A reference-counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference-counting collectors either use a backup tracing collector infrequently, or employ a cycle collector to reclaim cyclic structures. We propose a new concurrent cycle collector, one that runs concurrently with the program threads, imposing negligible pauses (of around 1ms) on a multiprocessor.

Our new collector combines a state-of-the-art cycle collector [Bacon and Rajan 2001] with sliding-views collectors [Levanoni and Petrank 2001, 2006; Azatchi et al. 2003]. The use of sliding views for cycle collection yields two advantages. First, it drastically reduces the number of cycle candidates, which in turn drastically reduces the work required to record and trace these candidates. Consequentially, a large improvement in cycle collection efficiency is achieved. Second, it eliminates the theoretical termination problem that appeared in the earlier concurrent cycle collector. There, a rare race may delay the reclamation of an unreachable cyclic structure forever. The sliding-views cycle collector guarantees reclamation of all unreachable cyclic structures.

The proposed collector was implemented on the Jikes RVM and we provide measurements including a comparison between the use of backup tracing and the use of cycle collection with reference counting. To the best of our knowledge, such a comparison has not been reported before.

REFERENCES

• 1: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, ACM SIGPLAN Notices, v.34 n.10, p.314-324, Oct. 1999
• 2: 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
• 3: Azatchi, H. and Petrank, E. 2003. Integrating generations with advanced reference counting garbage collectors. In Proceedings of the Compiler Construction: 12th International Conference on Compiler Construction, CC 2003. Lecture Notes in Computer Science, vol. 2622. Springer-Verlag Heidelberg, Warsaw, Poland, 185--199.
• 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: Mordechai Ben-Ari, On-the-Fly Garbage Collection: New Algorithms Inspired by Program Proofs, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.14-22, July 12-16, 1982
• 8: Mordechai Ben-Ari, Algorithms for on-the-fly garbage collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.333-344, July 1984 [doi>10.1145/579.587]
• 9: 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
• 10: Daniel G. Bobrow, Managing Reentrant Structures Using Reference Counts, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.269-273, July 1980 [doi>10.1145/357103.357104]
• 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: Christopher, T. W. 1984. Reference count garbage collection. Software Practice and Experience 14, 6 (June), 503--507.
• 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: Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 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: 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]
• 17: 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]
• 18: 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]
• 19: Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.274-284, June 18-21, 2000, Vancouver, British Columbia, Canada
• 20: Ellis, J. R., Li, K., and Appel, A. W. 1988. Real-time concurrent collection on stock multiprocessors. Tech. Rep. DEC--SRC--TR--25, DEC Systems Research Center, Palo Alto, CA. Feb.
• 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: Christine H. Flood , David Detlefs , Nir Shavit , Xiaolan Zhang, Parallel garbage collection for shared memory multiprocessors, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.21-21, April 23-24, 2001, Monterey, California
• 23: David Gries, An exercise in proving parallel programs correct, Communications of the ACM, v.20 n.12, p.921-930, Dec. 1977 [doi>10.1145/359897.359903]
• 24: Richard L. Hudson , J. Eliot B. Moss, Sapphire: copying GC without stopping the world, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.48-57, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376810]
• 25: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 26: Haim Kermany , Erez Petrank, The Compressor: concurrent, incremental, and parallel compaction, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 27: Kolodner, E. K. and Petrank, E. 2004. Parallel copying garbage collection using delayed allocation. In Parallel Processing Letters. Vol. 14.
• 28: Kung, H. T. and Song, S. W. 1977. An efficient parallel garbage collection system and its correctness proof. In IEEE Symposium on Foundations of Computer Science. IEEE Press, 120--131.
• 29: Lamport, L. 1976. Garbage collection with multiple processes: an exercise in parallelism. In Proceedings of the 1976 International Conference on Parallel Processing. 50--54.
• 30: Levanoni, Y. and Petrank, E. 1999. A scalable reference counting garbage collector. Tech. Rep. CS--0967, Technion---Israel Institute of Technology, Haifa, Israel. (Nov).
• 31: Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, ACM SIGPLAN Notices, v.36 n.11, p.367-380, 11/01/2001
• 32: Yossi Levanoni , Erez Petrank, An on-the-fly reference-counting garbage collector for java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.1-69, January 2006 [doi>10.1145/1111596.1111597]
• 33: Rafael D. Lins, Cyclic reference counting with lazy mark-scan, Information Processing Letters, v.44 n.4, p.215-220, Dec. 10, 1992 [doi>10.1016/0020-0190(92)90088-D]
• 34: Rafael Dueire Lins, An efficient algorithm for cyclic reference counting, Information Processing Letters, v.83 n.3, p.145-150, 16 August 2002 [doi>10.1016/S0020-0190(01)00328-3]
• 35: A. D. Martínez , R. Wachenchauzer , R. D. Lins, Cyclic reference counting with local mark-scan, Information Processing Letters, v.34 n.1, p.31-35, February 1990 [doi>10.1016/0020-0190(90)90226-N]
• 36: 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]
• 37: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 38: Nilsen, K. D., Mitra, S., and Lee, S. J. 2000. Method for efficient soft real-time execution of portable byte code computer programs. http://www.patentstorm.us/patents/6081665.html.
• 39: Paz, H., Petrank, E., Bacon, D. F., Rajan, V., and Kolodner, E. K. 2005a. An efficient on-the-fly cycle collection. In Proceedings of the 14th International Conference on Compiler Construction. Springer-Verlag, Edinburgh.
• 40: Paz, H., Petrank, E., and Blackburn, S. M. 2003. Age-oriented garbage collection. Tech. Rep. CS-2003-08, Technion, Israel Institute of Technology. Oct. http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?2003/CS/CS-2003-08.
• 41: Paz, H., Petrank, E., and Blackburn, S. M. 2005b. Age-oriented garbage collection. In Proceedings of the 14th International Conference on Compiler Construction. Springer-Verlag, Edinburgh.
• 42: 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
• 43: SPEC Benchmarks. 2000. Standard Performance Evaluation Corporation. http://www.spec.org/.
• 44: 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]
• 45: 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]
• 46: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 47: Paul R. Wilson , Mark S. Johnstone , Michael Neely , David Boles, Dynamic Storage Allocation: A Survey and Critical Review, Proceedings of the International Workshop on Memory Management, p.1-116, September 27-29, 1995

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.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Algorithms, Languages

Keywords:
Programming languages, concurrent cycle collection, garbage collection, memory management, reference counting, runtime systems