More Web Proxy on the site http://driver.im/

article

Open access

An efficient on-the-fly cycle collection

Authors:

David F. Bacon,

Elliot K. Kolodner,

V. T. RajanAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 29, Issue 4

Pages 20 - es

https://doi.org/10.1145/1255450.1255453

Published: 01 August 2007 Publication History

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]

Alpern, B., Attanasio, C. R., Cocchi, A., Lieber, D., Smith, S., Ngo, T., Barton, J. J., Hummel, S. F., Sheperd, J. C., and Mergen, M. 1999. Implementing Jalapeño in Java. In OOPSLA'99 ACM Conference on Object-Oriented Systems, Languages and Applications. ACM SIGPLAN Notices, vol. 34(10). ACM Press, Denver, CO, 314--324.

[2]

Azatchi, H., Levanoni, Y., Paz, H., and Petrank, E. 2003. An on-the-fly mark and sweep garbage collector based on sliding view. OOPSLA'03 ACM Conference on Object-Oriented Systems, Languages, and Applications. ACM SIGPLAN Notices. ACM Press, Anaheim, CA.

[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]

Bacon, D. F., Attanasio, C. R., Lee, H. B., Rajan, V. T., and Smith, S. 2001. Java without the coffee breaks: A nonintrusive multiprocessor garbage collector. In Proceedings of SIGPLAN 2001 Conference on Programming Languages Design and Implementation. ACM SIGPLAN Notices. ACM Press, Snowbird, Utah.

[5]

Bacon, D. F. and Rajan, V. 2001. Concurrent cycle collection in reference counted systems. In Proceedings of the 15th European Conference on Object-Oriented Programming, ECOOP 2001, J. L. Knudsen, Ed. Lecture Notes in Computer Science, vol. 2072. Springer-Verlag, Budapest.

[6]

Baker, H. G. 1978. List processing in real-time on a serial computer. Comm. ACM 21, 4, 280-- 294.

[7]

Ben-Ari, M. 1982. On-the-fly garbage collection: New algorithms inspired by program proofs. In Automata, Languages and Programming. Ninth Colloquium, M. Nielsen and E. M. Schmidt, Eds. Springer-Verlag, Aarhus, Denmark, 14--22.

[8]

Ben-Ari, M. 1984. Algorithms for on-the-fly garbage collection. ACM Trans. Program. Lang. Syst. 6, 3 (July), 333--344.

[9]

Blackburn, S. M. and McKinley, K. S. 2003. Ulterior reference counting: Fast garbage collection without a long wait. OOPSLA'03 ACM Conference on Object-Oriented Systems, Languages, and Applications. ACM SIGPLAN Notices. ACM Press, Anaheim, CA.

[10]

Bobrow, D. G. 1980. Managing re-entrant structures using reference counts. ACM Trans. Program. Lang. Syst. 2, 3 (July), 269--273.

[11]

Boehm, H.-J., Demers, A. J., and Shenker, S. 1991. Mostly parallel garbage collection. ACM SIGPLAN Notices 26, 6, 157--164.

[12]

Christopher, T. W. 1984. Reference count garbage collection. Software Practice and Experience 14, 6 (June), 503--507.

[13]

Collins, G. E. 1960. A method for overlapping and erasure of lists. Comm. ACM 3, 12 (Dec.), 655--657.

[14]

Demers, A., Weiser, M., Hayes, B., Boehm, H.-J., Bobrow, D. G., and Shenker, S. 1990. Combining generational and conservative garbage collection: Framework and implementations. In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages. ACM SIGPLAN Notices. ACM Press, San Francisco, CA, 261--269.

[15]

Deutsch, L. P. and Bobrow, D. G. 1976. An efficient incremental automatic garbage collector. Comm. ACM 19, 9 (Sept.), 522--526.

[16]

Dijkstra, E. W., Lamport, L., Martin, A. J., Scholten, C. S., and Steffens, E. F. M. 1978. On-the-fly garbage collection: An exercise in cooperation. Comm. ACM 21, 11 (Nov.), 965--975.

[17]

Doligez, D. and Gonthier, G. 1994. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the Twenty-first Annual ACM Symposium on Principles of Programming Languages. ACM SIGPLAN Notices. ACM Press, Portland, OR.

[18]

Doligez, D. and Leroy, X. 1993. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages. ACM SIGPLAN Notices. ACM Press, 113--123.

[19]

Domani, T., Kolodner, E., and Petrank, E. 2000. A generational on-the-fly garbage collector for Java. In Proceedings of SIGPLAN 2000 Conference on Programming Languages Design and Implementation. ACM SIGPLAN Notices. ACM Press, Vancouver.

[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]

Endo, T., Taura, K., and Yonezawa, A. 1997. A scalable mark-sweep garbage collector on large-scale shared-memory machines. In Proceedings of High Performance Computing and Networking (SC'97).

[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.

[23]

Gries, D. 1977. An exercise in proving parallel programs correct. Comm. ACM 20, 12 (Dec.), 921--930.

[24]

Hudson, R. L. and Moss, J. E. B. 2001. Sapphire: Copying GC without stopping the world. In Joint ACM Java Grande---ISCOPE 2001 Conference. Stanford University, CA.

[25]

Jones, R. E. 1996. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, Chichester.

[26]

Kermany, H. and Petrank, E. 2006. The compressor: Concurrent, incremental, and parallel compaction. In Proceedings of SIGPLAN 2006 Conference on Programming Languages Design and Implementation. ACM SIGPLAN Notices. ACM Press, Ottawa, 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]

Levanoni, Y. and Petrank, E. 2001. An on-the-fly reference counting garbage collector for Java. In OOPSLA'01 ACM Conference on Object-Oriented Systems, Languages and Applications. ACM SIGPLAN Notices, vol. 36(10). ACM Press, Tampa, FL.

[32]

Levanoni, Y. and Petrank, E. 2006. An on-the-fly reference-counting garbage collector for Java. ACM Transactions on Programming Languages and Systems 28, 1 (Jan.), 1--69.

[33]

Lins, R. D. 1992. Cyclic reference counting with lazy mark-scan. Information Processing Letters 44, 4, 215--220. Also Computing Laboratory Technical Report 75, University of Kent, July 1990.

[34]

Lins, R. D. 2002. An efficient algorithm for cyclic reference counting. Information Processing Letters 83, 145--150.

[35]

Martinez, A. D., Wachenchauzer, R., and Lins, R. D. 1990. Cyclic reference counting with local mark-scan. Information Processing Letters 34, 31--35.

[36]

McBeth, J. H. 1963. On the reference counter method. Communications of the ACM 6, 9 (Sept.), 575.

[37]

Moon, D. A. 1984. Garbage collection in a large LISP system. In Conference Record of the 1984 ACM Symposium on Lisp and Functional Programming, G. L. Steele, Ed. ACM Press, Austin, TX, 235--245.

[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]

Printezis, T. and Detlefs, D. 2000. A generational mostly-concurrent garbage collector. In ISMM 2000 Proceedings of the Second International Symposium on Memory Management, T. Hosking, Ed. ACM SIGPLAN Notices, vol. 36(1). ACM Press, Minneapolis, MN.

[43]

SPEC Benchmarks. 2000. Standard Performance Evaluation Corporation. http://www.spec.org/.

[44]

Steele, G. L. 1975. Multiprocessing compactifying garbage collection. Comm. ACM 18, 9 (Sept.), 495--508.

[45]

Steele, G. L. 1976. Corrigendum: Multiprocessing compactifying garbage collection. Comm. ACM 19, 6 (June), 354.

[46]

Weizenbaum, J. 1963. Symmetric list processor. Comm. ACM 6, 9 (Sept.), 524--544.

[47]

Wilson, P. R., Johnstone, M. S., Neely, M., and Boles, D. 1995. Dynamic storage allocation: A survey and critical review. In Proceedings of International Workshop on Memory Management, H. Baker, Ed. Lecture Notes in Computer Science, vol. 986. Springer-Verlag, Kinross, Scotland.

Cited By

Veresov A(2022)On a possible embedding of Lisp into the C languageKeldysh Institute Preprints10.20948/prepr-2022-30(1-35)Online publication date: 2022
https://doi.org/10.20948/prepr-2022-30
Choi JShull TTorrellas JEvripidou SStenström PO'Boyle M(2018)Biased reference countingProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243195(1-12)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243195
Bruno RFerreira P(2018)A Study on Garbage Collection Algorithms for Big Data EnvironmentsACM Computing Surveys10.1145/315681851:1(1-35)Online publication date: 10-Jan-2018
https://dl.acm.org/doi/10.1145/3156818
Show More Cited By

Index Terms

An efficient on-the-fly cycle collection
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Dynamic compilers
    2. General programming languages
      1. Language types
        Object oriented languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

An 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 ...
An on-the-fly mark and sweep garbage collector based on sliding views
Special Issue: Proceedings of the OOPSLA '03 conference

With concurrent and garbage collected languages like Java and C# becoming popular, the need for a suitable non-intrusive, efficient, and concurrent multiprocessor garbage collector has become acute. We propose a novel mark and sweep on-the-fly algorithm ...
A generational on-the-fly garbage collector for Java

An 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 29, Issue 4

August 2007

244 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1255450

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2007

Published in TOPLAS Volume 29, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
911
Total Downloads

Downloads (Last 12 months)159
Downloads (Last 6 weeks)21

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Veresov A(2022)On a possible embedding of Lisp into the C languageKeldysh Institute Preprints10.20948/prepr-2022-30(1-35)Online publication date: 2022
https://doi.org/10.20948/prepr-2022-30
Choi JShull TTorrellas JEvripidou SStenström PO'Boyle M(2018)Biased reference countingProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243195(1-12)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243195
Bruno RFerreira P(2018)A Study on Garbage Collection Algorithms for Big Data EnvironmentsACM Computing Surveys10.1145/315681851:1(1-35)Online publication date: 10-Jan-2018
https://dl.acm.org/doi/10.1145/3156818
Brandt SKrishnan HSharma GBusch C(2014)Concurrent, parallel garbage collection in linear timeACM SIGPLAN Notices10.1145/2775049.260299049:11(47-58)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2775049.2602990
Brandt SKrishnan HSharma GBusch CGrove DGuyer S(2014)Concurrent, parallel garbage collection in linear timeProceedings of the 2014 international symposium on Memory management10.1145/2602988.2602990(47-58)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2602988.2602990
Morris Chang JChen WGriffin PCheng H(2012)Cyclic reference counting by typed reference fieldsComputer Languages, Systems and Structures10.1016/j.cl.2011.09.00138:1(98-107)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1016/j.cl.2011.09.001
Peschanski FCarro MReppy J(2011)Parallel computing with the Pi-calculusProceedings of the sixth workshop on Declarative aspects of multicore programming10.1145/1926354.1926363(45-54)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.1145/1926354.1926363
Hesselink WLali M(2010)Simple concurrent garbage collection almost without synchronizationFormal Methods in System Design10.1007/s10703-009-0083-z36:2(148-166)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1007/s10703-009-0083-z
Sockut GIyer B(2009)Online reorganization of databasesACM Computing Surveys10.1145/1541880.154188141:3(1-136)Online publication date: 30-Jul-2009
https://dl.acm.org/doi/10.1145/1541880.1541881
Hou TLin CMa T(2009)A Single-Trace Cycle Collection for Reference Counting SystemsProceedings of the 2009 10th International Symposium on Pervasive Systems, Algorithms, and Networks10.1109/I-SPAN.2009.41(40-45)Online publication date: 14-Dec-2009
https://dl.acm.org/doi/10.1109/I-SPAN.2009.41

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents