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

article

A simple and efficient algorithm for cycle collection

Authors:

Ting-Wei HouAuthors Info & Claims

ACM SIGPLAN Notices, Volume 42, Issue 3

Pages 7 - 13

https://doi.org/10.1145/1273039.1273041

Published: 01 March 2007 Publication History

Abstract

The lack of collecting cyclic garbage is generally considered the major weakness of reference counting. Reference counted systems handle this problem by incorporating either a global tracing collector, or a "partial" tracing collector that considers only the cycle candidates but needs several traces on them. In particular, the latter has become a preferred one as it has better scalability and locality (no need to scan the entire heap). This paper presents a new "lightweight" cyclic reference counting algorithm, which is based on partial tracing and deals with the cycle problem in a simpler and more efficient way. By exploiting the lightweight hypothesis that considers a single sub-graph, instead of individual cycles, as the basic unit of cycle collection, the algorithm can detect garbage cycles in a single trace. In addition, we propose a technique for eliminating redundant scans over garbage objects, thus improving the efficiency of the algorithm. The pseudocode and its correctness proof are also presented. Finally, an implementation based on Jikes Research Virtual Machine is provided to demonstrate the effectiveness of the new algorithm.

References

[1]

B. Alpern, C. R. Attanasio, A. Cocchi, D. Lieber, S. Smith, T. Ngo, J. J. Barton, S. F. Hummel, J. C. Sheperd, and M. Mergen, "Implementing Jalape no in Java," In Proceedings of the 1999 ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado, ACM SIGPLAN Notices, vol. 34(10), pp. 314--324, ACM Press, October, 1999.

Digital Library

[2]

D. F. Bacon, C. R. Attanasio, H. B. Lee, V. T. Rajan, and S. Smith, "Java without the coffee breaks: A nonintrusive multi-processor garbage collector." In Proceedings of the ACM SIGPLAN'01 Conference on Programming Languages Design and Implementation (PLDI). Snowbird, Utah, vol. 36(5), pp. 92--103, June 2001.

Digital Library

[3]

D. F. Bacon and V. T. Rajan, "Concurrent cycle collection in reference counted systems," In J. L. Knudsen, editor, Proceedings of 15th European Conference on Object-Oriented Programming (ECOOP'01), Budapest, Hungary, Springer-Verlag, LNCS 2072, pp. 207--235, June, 2001.

Digital Library

[4]

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

[5]

G. E. Collins, "A method for overlapping and erasure of lists," Communications of the ACM, vol. 3(12), pp. 655--657, December, 1960.

Digital Library

[6]

J. Detreville, "Experience with concurrent garbage collectors for Modula-2+. Tech. Rep. 64," DEC Systems Research Center, Palo Alto, California, 1990.

[7]

S. Dieckmann and U. Hölzle, "A study of the allocation behavior of the SPECjvm98 Java benchmarks," In Proceedings of ECOOP'99, Springer-Verlag, LNCS 1628, pp. 92--115, 1999.

Digital Library

[8]

R. E. Jones and R. D. Lins, Garbage Collection: Algorithms for Automatic Dynamic Memory Management, Wiley, July, 1996.

Digital Library

[9]

R. E. Jones and R. D. Lins, "Cyclic weighted reference counting without delay," In Proceedings of Parallel Architectures and Languages Europe (PARLE'93), A. Bode, M. Reeve, and G. Wolf, Eds., Springer-Verlag, LNCS 694, pp. 712--715, June 1993.

Digital Library

[10]

Y. Levanoni and E. Petrank, "An on-the-fly reference counting garbage collector for Java," In ACM Conference Proceedings on Object-Oriented Programming Systems, Languages, and Applications, Tampa, FL, pp. 367--380, October, 2001.

Digital Library

[11]

C.-Y. Lin and T.-W. Hou, "A lightweight cyclic reference counting algorithm," In Proceedings of the first International Conference on Grid and Pervasive Computing, Taichung, Taiwan, May 3--5, Springer-Verlag, LNCS 3947, pp. 346--359, 2006.

Digital Library

[12]

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

Digital Library

[13]

R. D. Lins, "Generational cyclic reference counting," Information Processing Letters, vol. 46, pp. 19--20, 1993.

Digital Library

[14]

R. D. Lins, "Cyclic reference counting with lazy mark-scan," Information Processing Letters, vol. 44, pp. 215--220, 1992.

Digital Library

[15]

R. D. Lins and R. E. Jones, "Cyclic weighted reference counting," in: K. Boyanov (Ed.), Proceedings of International Workshop on Parallel and Distributed Processing, NH, pp. 369--382, May, 1993.

[16]

M. Maeda, H. Konaka, Y. Ishikawa, T. Tomokiyo, A. Hori, and J. Nolte, "On-the-fly global garbage collection based on partly mark-sweep," Springer-Verlag, LNCS 986, pp. 283--296, 1995.

Digital Library

[17]

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

Digital Library

[18]

J. H. McBeth, "On the reference counter method," Communications of the ACM, vol. 6(9), pp. 575, September, 1963.

Digital Library

[19]

J. McCarthy, "Recursive functions of symbolic expressions and their computation by machine," Communications of the ACM, vol. 3, pp. 184--195, 1960.

Digital Library

[20]

H. Paz, E. Petrank, D. F. Bacon, V. T. Rajan, and E. K. Kolodner, "Efficient on-the-fly cycle collection," In Proceedings of the 14th International Conference on Compiler Construction, R. Bodik, editor, Springer- Verlag, LNCS 3443, pp. 156--171, April, 2005.

Digital Library

[21]

Standard Performance Evaluation Corporation, "SPECjvm98 Documentation", release 1.03 edition, March, 1999.

[22]

X. Ye and J. Keane, "Collecting cyclic garbage in distributed systems." In International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN'97), Taipei, Taiwan, pp. 227--231, December, 1997.

Digital Library

Cited By

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
Lin CHou TChen F(2010)A Snapshot-Based Evaluation Method for Garbage CollectionProceedings of the 2010 Sixth International Conference on Intelligent Information Hiding and Multimedia Signal Processing10.1109/IIHMSP.2010.107(418-421)Online publication date: 15-Oct-2010
https://dl.acm.org/doi/10.1109/IIHMSP.2010.107
Lin CHou T(2010)An efficient approach to cyclic reference counting based on a coarse-grained searchInformation Processing Letters10.1016/j.ipl.2010.10.004111:1(1-10)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1016/j.ipl.2010.10.004
Show More Cited By

Index Terms

A simple and efficient algorithm for cycle collection
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

An efficient on-the-fly cycle collection

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 ...
A Single-Trace Cycle Collection for Reference Counting Systems
ISPAN '09: Proceedings of the 2009 10th International Symposium on Pervasive Systems, Algorithms, and Networks

The lack of collecting cyclic garbage is generally considered the major weakness of reference counting. Reference counted systems handle this problem by incorporating either a global tracing collector or a partial tracing collector that considers only ...
Flexible reference-counting-based hardware acceleration for garbage collection

Languages featuring automatic memory management (garbage collection) are increasingly used to write all kinds of applications because they provide clear software engineering and security advantages. Unfortunately, garbage collection imposes a toll on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 42, Issue 3

March 2007

21 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1273039

Issue’s Table of Contents

Copyright © 2007 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2007

Published in SIGPLAN Volume 42, Issue 3

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
447
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Lin CHou TChen F(2010)A Snapshot-Based Evaluation Method for Garbage CollectionProceedings of the 2010 Sixth International Conference on Intelligent Information Hiding and Multimedia Signal Processing10.1109/IIHMSP.2010.107(418-421)Online publication date: 15-Oct-2010
https://dl.acm.org/doi/10.1109/IIHMSP.2010.107
Lin CHou T(2010)An efficient approach to cyclic reference counting based on a coarse-grained searchInformation Processing Letters10.1016/j.ipl.2010.10.004111:1(1-10)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1016/j.ipl.2010.10.004
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
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

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents