[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Lightweight Cyclic Reference Counting Algorithm

  • Conference paper
Advances in Grid and Pervasive Computing (GPC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3947))

Included in the following conference series:

Abstract

This paper focuses on a major weakness of reference counting technique – the lack of collecting cyclic garbage. Most reference counted systems handle this problem by either invoking a global mark-sweep collector occasionally, or incorporating a local ("partial") tracing collector that considers only the cycle candidates (objects) but needs several traces on them. This paper proposes a "lightweight" cycle detector, which is based on the partial tracing approach but collects garbage cycles in a simpler and more efficient way. Key to the algorithm is the removal of multiple traces on the cycle candidates – It effectively reclaims garbage cycles in only one trace. We have evaluated the algorithm in the Jikes Research Virtual Machine, where a set of benchmark programs from SPECjvm98 were applied. The experiments demonstrate the efficiency and practicability of the lightweight cycle detector, compared to a modern cycle detector that requires multiple traces on objects.

This research was supported by the National Science Council of R.O.C. under contract NSC 92-2213-E-006-045.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alpern, B., et al.: Implementing Jalapeño in Java. In: OOPSLA 1999 Conference Proceedings: Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado (October 1999); SIGPLAN Notices 34(10), 314–324 (1999)

    Google Scholar 

  2. Bacon, D.F., Attanasio, C.R., Lee, H.B., Rajan, V.T., Smith, S.: 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, Snowbird, Utah (June 2001)

    Google Scholar 

  3. Bacon, D.F., Rajan, V.T.: Concurrent cycle collection in reference counted systems. In: Knudsen, J.L. (ed.) ECOOP 2001. LNCS, vol. 2072, pp. 207–235. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  4. Blackburn, S.M., Cheng, P., McKinley, K.S.: Oil and water? High performance garbage collection in Java with MMTk. In: International Conference on Software Engineering (2004)

    Google Scholar 

  5. Blackburn, S.M., McKinley, K.S.: Ulterior reference counting: Fast garbage collection without a long wait. In: ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Anaheim, CA, pp. 244–358 (2003)

    Google Scholar 

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

    Article  Google Scholar 

  7. Collins, G.E.: A method for overlapping and erasure of lists. Commun. ACM 3(12), 655–657 (1960)

    Article  MathSciNet  Google Scholar 

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

    Google Scholar 

  9. Deutsch, L.P., Bobrow, D.G.: An efficient incremental automatic garbage collector. Commun. ACM 19(9), 522–526 (1976)

    Article  MATH  Google Scholar 

  10. Jones, R.E., Lins, R.D.: Cyclic weighted reference counting without delay. In: Bode, A., Reeve, M., Wolf, G. (eds.) PARLE 1993. LNCS, vol. 694, pp. 712–715. Springer, Heidelberg (1993)

    Chapter  Google Scholar 

  11. Jones, R.E., Lins, R.D.: Garbage Collection. John Wiley and Sons, Chichester (1996)

    MATH  Google Scholar 

  12. Levanoni, Y., Petrank, E.: A scalable reference counting garbage collector. Technical Report CS-0967, Technion - Israel Institute of Technology, Haifa, Israel (November 1999)

    Google Scholar 

  13. Levanoni, Y., Petrank, E.: 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 (2001)

    Google Scholar 

  14. Lins, R.D.: An efficient algorithm for cyclic reference counting. Inf. Process. Lett. 83, 145–150 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  15. Lins, R.D.: Cyclic reference counting with lazy mark-scan. Inf. Process. Lett. 44(4), 215–220 (1992)

    Article  MATH  Google Scholar 

  16. Lins, R.D.: Generational cyclic reference counting. Inf. Process. Lett. 46(1), 19–20 (1993)

    Article  MATH  Google Scholar 

  17. Martinez, A.D., Wachenchauzer, R., Lins, R.D.: Cyclic reference counting with local mark-scan. Inf. Process. Lett. 34(1), 31–35 (1990)

    Article  MATH  Google Scholar 

  18. McBeth, J.H.: On the reference counter method. Commun. ACM 6(9), 575 (1963)

    Article  Google Scholar 

  19. McCarthy, J.: Recursive functions of symbolic expressions and their computation by machine. Commun. ACM 3, 184–195 (1960)

    Article  MATH  Google Scholar 

  20. Paz, H., Petrank, E., Bacon, D.F., Rajan, V.T., Kolodner, E.K.: An efficient on-the-fly cycle collection. In: Proceedings of the 14th International Conference on Compiler Construction, Edinburgh. Springer, Heidelberg (2005)

    Google Scholar 

  21. Standard Performance Evaluation Corporation: Specjvm98 documentation (March 1999)

    Google Scholar 

  22. Ye, X., Keane, J.: Collecting cyclic garbage in distributed systems. In: International Symposium on Parallel Architectures, Algorithms and Networks, Taipei, Taiwan (1997)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Engineering Science, National Cheng Kung University, No. 1, Ta-Hsueh Rd., Tainan, 701, Taiwan

    Chin-Yang Lin & Ting-Wei Hou

Authors
  1. Chin-Yang Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ting-Wei Hou
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, National Tsing Hua University, 30013, Hsinchu, Taiwan

    Yeh-Ching Chung

  2. IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USA

    José E. Moreira

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lin, CY., Hou, TW. (2006). A Lightweight Cyclic Reference Counting Algorithm. In: Chung, YC., Moreira, J.E. (eds) Advances in Grid and Pervasive Computing. GPC 2006. Lecture Notes in Computer Science, vol 3947. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11745693_35

Download citation

  • DOI: https://doi.org/10.1007/11745693_35

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-33809-3

  • Online ISBN: 978-3-540-33810-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation