Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Integrating Generations with Advanced Reference Counting Garbage Collectors

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2622))

Included in the following conference series:

  • 1236Accesses

Abstract

We study an incorporation of generations into a modern reference counting collector. We start with the two on-the-fly collectors suggested by Levanoni and Petrank: a reference counting collector and a tracing (mark and sweep) collector. We then propose three designs for combining them so that the reference counting collector collects the young generation or the old generation or both. Our designs maintain the good properties of the Levanoni-Petrank collector. In particular, it is adequate for multithreaded environment and a multiprocessor platform, and it has an effcient write barrier with no synchronization operations. To the best of our knowledge, the use of generations with reference counting has not been tried before.

We have implemented these algorithms with the Jikes JVM and compared them against the concurrent reference counting collector supplied with the Jikes package. As expected, the best combination is the one that lets the tracing collector work on the young generation (where most objects die) and the reference counting work on the old generation (where many objects survive). Matching the expected survival rate with the nature of the collector yields a large improvement in throughput while maintaining the pause times around a couple of milliseconds.

Most of this work was done while the author was at the Computer Science Dept., Technion - Israel Institue of Technology.

This research was supported by the E. AND J. BISHOP RESEARCH FUND and by the FUND FOR PROMOTION OF RESEARCH at the Technion.

Similar content being viewed by others

Keywords

References

  1. Hezi Azatchi and Erez Petrank. Integrating Generations with Advanced Reference Counting Garbage Collectors. Technical Report, Faculty of Computer Science, Technion, Israel Institute of Technology, October 2002. Available athttp://www.cs.technion.ac.il/∼erez/publications.html.

  2. Alan Demers, Mark Weiser, Barry Hayes, Hans Boehm, Daniel G. Bobrow, and Scott Shenker. Combining generational and conservative garbage collection: Framework and implementations. In Conference Record of theSeventeenth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, January 1990. ACM Press, pages 261–269.

    Google Scholar 

  3. D. Bacon, C. Attanasio, H. Lee, V. Rajan, and S. Smith. Java without the coffee breaks: A nonintrusive multiprocessor garbage collector.ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Snowbird, Utah, June 20–22 2001.

    Google Scholar 

  4. D. Bacon and V. Rajan. Concurrent Cycle Collection in Reference Counted Systems.Fifteenth European Conference on Object-Oriented Programming (ECOOP), University Eötvös Lorand, Budapest, Hungary, June 18–22 2001.

    Google Scholar 

  5. Henry G. Baker. List processing in real-time on a serial computer.Communications of the ACM, 21(4):280–94, 1978.

    Article MATH  Google Scholar 

  6. Henry G. Baker. Minimising reference count updating with deferred and anchored pointers for functional data structures.ACM SIGPLAN Notices, 29(9), September 1994.

    Google Scholar 

  7. Hans-Juergen Böhm, Alan J. Demers, and Scott Shenker. Mostly parallel garbage collection. collector.ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI, 1991), ACM SIGPLAN Notices, 26(6):157–164, 1991.

    Article  Google Scholar 

  8. George E. Collins. A method for overlapping and erasure of lists.Communications of the ACM, 3(12):655–657, December 1960.

    Article  Google Scholar 

  9. John DeTreville. Experience with concurrent garbage collectors for Modula-2+. Technical Report 64, DEC Systems Research Center, Palo Alto, CA, August 1990.

    Google Scholar 

  10. L. Peter Deutsch and Daniel G. Bobrow. An efficient incremental automatic garbage collector.Communications of the ACM, 19(9):522–526, September 1976.

    Article MATH  Google Scholar 

  11. Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation.Communications of the ACM, 21(11):965–975, November 1978.

    Article  Google Scholar 

  12. Damien Doligez and Georges Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. InPOPL 1994.

    Google Scholar 

  13. Damien Doligez and Xavier Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. InPOPL 1993.

    Google Scholar 

  14. 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-fly Garbage Collector for Java.ISMM, 2000.

    Google Scholar 

  15. Tamar Domani, Elliot K. Kolodner, and Erez Petrank. Generational On-the-fly Garbage Collector for Java.ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI) 2000.

    Google Scholar 

  16. Shinichi Furusou, Satoshi Matsuoka, and Akinori Yonezawa.Parallel conservative garbage collection with fast allocation. In Paul R. Wilson and Barry Hayes, editors, GC workshop at OOPSLA, October 1991.

    Google Scholar 

  17. Yossi Levanoni and Erez Petrank. An On-the-fly Reference Counting Garbage Collector for Java,proccedings of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA’01). See also the Technical Report CS-0967, Dept. of Computer Science, Technion, Nov. 1999.

    Google Scholar 

  18. H. Lieberman and C. E. Hewitt. A Real Time Garbage Collector Based on the Lifetimes of Objects.Communicaitons of the ACM, 26(6), pages 419–429, 1983.

    Article  Google Scholar 

  19. Young G. Park and Benjamin Goldberg. Static analysis for optimising reference counting.IPL, 55(4):229–234, August 1995.

    Article MATH  Google Scholar 

  20. Manoj Plakal and Charles N. Fischer. Concurrent Garbage Collection Using Program Slices on Multithreaded Processors.

    Google Scholar 

  21. Tony Printezis and David Detlefs. A generational mostly-concurrent garbage collector.ISMM 2000.

    Google Scholar 

  22. 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 Scholar 

  23. D. Ungar. Generation Scavenging: A Non-disruptive High Performance Storage Reclamation Algorithm. ACM SIGPLAN Notices Vol. 19,No. 5, May 1984, pp. 157–167.

    Article MathSciNet  Google Scholar 

  24. J. Weizenbaum. Symmetric list processor.Communications of the ACM, 6(9):524–544, September 1963.

    Article MATH MathSciNet  Google Scholar 

  25. David S. Wise. Stop and one-bit reference counting. Technical Report 360, Indiana University, Computer Science Department, March 1993.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM Haifa Research Labs, Haifa University Campus, Mount Carmel, 31905, Haifa, Israel

    Hezi Azatchi

  2. Dept. of Computer Science, Technion - Israel Institute of Technology, 32000, Haifa, Israel

    Erez Petrank

Authors
  1. Hezi Azatchi

    You can also search for this author inPubMed Google Scholar

  2. Erez Petrank

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Lund University, Box 118, 221 00, Lund, Sweden

    Görel Hedin

Rights and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Azatchi, H., Petrank, E. (2003). Integrating Generations with Advanced Reference Counting Garbage Collectors. In: Hedin, G. (eds) Compiler Construction. CC 2003. Lecture Notes in Computer Science, vol 2622. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36579-6_14

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp